八皇后问题课程设计.doc

八皇后问题课程设计1设计背景11课程设计的目的本课程设计的目的在于提高学生对数据结构和C+语言课程的运用能力，并能使学生加深对数据结构和编程工作的理解。书本知识转化成个人能力，最终还是要靠不断地付诸实践，课程设计恰为这种时间提供了一个很好的平台。1.2课程设计任务与要求程序启动后显示一张8*8的棋盘，然后游戏者可以用坐标输入方式在棋盘上布下棋子。如果布下的棋子合法，则增加10分并可以继承布下一个棋子。如果布下的棋子不合法，给出游戏者的得分数。若无错误布下8颗棋子，则给与满分100分。（由于本学期我们尚未学习图形界面的有关类容，所以课程设计中的有关图形界面的内容进行了修改。）游戏规则要求不能在同一行或同一列或同一条对角线上放置二个或二个以上的棋子，但每行都必须放置一个棋子。2 程序的实现过程2.1设计思想、算法及实现要点程序编写都是由简单到复杂的，接到任务以后，就在脑子里有了一个大概的框架。一个while（1）的打循环里嵌套一个界面输入程序，通过用户不断地输入来控制游戏的循环的继续和跳出，并且在设计一个自动跳出的判断语句。这样，玩家就能在循环体里不断布棋，直到玩家想终止游戏或者游戏过关成功。关于下棋系统，首先要处理的就是棋盘，我把棋盘用赋值为0或1的二维数组来模拟国际象棋棋盘。0代表无棋子，1代表已下的棋子。这样就比较方便我以后判断棋盘横竖斜有且只有一个棋子，只需将横竖斜的元素累加，结果等于1即可。 由于没有真正的图形界面，下棋的方法就只能依靠用户输入横竖坐标了，输入坐标后，系统自动将该坐标位置的元素赋值为1。关于打分细则，我的设计是给一个基准分20分，正确下一个棋就加10分，这样，当游戏过关时恰好是100分。具体到实际编程时，又考虑到，游戏程序的可玩性问题，我又在之前的的简单框架上补充了悔棋的功能，并且能一次性悔多步棋子，这样，打分细则又改变了：起评分20分下对一颗棋子奖励10分，若要悔棋，悔棋一步扣除15分。由于栈的特点是先进后出，后进先出，正好符合后下的棋子先悔，先下的棋后悔，于是我就很自然的想到建立一个简单栈来存储每一步玩家所走的棋子。栈的内容很简单，只有压入和弹出的函数，没有过多防范数组越界、溢出等错误的处理。出错问题由程序员负责。剩下的就简单了，用一个int类型的数记录悔棋次数，评分系统就做好了。2.2 程序的函数程序主要有这几个函数构成void display()用来输出模拟的八皇后8*8棋盘； void display(int ,int)这是对上一个函数的重载，这样就允许先将一个特定位置的元素赋值为1，然后在输出；bool deal()对棋盘进行横、竖、斜等方面的处理，将棋盘的横、竖、斜三条线上元素求和，当这些和里面有值大于1时，说明至少有一对换后发生冲突，此时返回false,反之则返回true; void Main()是整个游戏的核心函数，里面设计了一个while（k），k是走棋的个数，所以k>0,该循环通常情况下无法终止，所以提示用户下棋的页面会一直循环出现，知道玩家成功闯关或者玩家提示想终止程序。2.3系统测试系统测试的阶段我主要做的就是进行错误处理的工作，比如：如果玩家输入了不存在的错误坐标，系统会提示：“坐标错误！请您输入18整数。”然后系统会让玩家更改输入坐标，如果输入了如重复的坐标，系统将会提示：“输入坐标重复，请重新输入。”直到玩家输入正确的坐标位置；在悔棋的时候，如果输入的悔棋步数超过当前步数，系统也会提示用户正确输入。并且各种提示信息都伴随一个喇叭发音，引起玩家注意。为了使界面看起来更加简洁，每一次更新棋盘元素并输出棋盘之前，我都用了一个system(“CLS”)；的语句，使得整个游戏过程不会很撩人。3 操作说明整个游戏操作，用户只需用数字键输入棋子的坐标或悔棋的步数，以及用N/Y键判断是否悔棋。输入错误数据都会有系统伴随喇叭发音的提示，N/Y键也对大小写进行了处理。玩家可以很轻松的进行游戏，不必担心错误的输入造成整个游戏系统的崩溃。4 总 结通过这一个星期的编程，觉得自己对于对数据结构和C+的编程运用能力有了很大的提高，不仅对堆栈有了切身的体会，了解了它的方便与麻烦之处，也同时把C+语言重新温习了一遍，巩固了上学期所学的知识。这次课程设计更令我意识到了数据结构这一课程的重要性，一个好的算法可依然程序更加简单明了高效，试想如果是在上个学期然我们来编写相同的程序，估计那程序可以想象会有多么的凌乱无序低效。参考文献1 严蔚敏,吴伟民.数据结构（C语言版）M.北京:清华大学出版社.1997:44-582 H.M.Deitel,P.J.Deitel.C+程序设计教程（第4版）M.北京：清华大学出版社.2004:1-792附录源程序如下：#include <iostream>using namespace std;/建立一个简单的栈/class Stack int mark8; int *top;/ int *base; public: Stack() for(int i(0);i<=7;i+)marki=-1; top=mark; void push(int e)*+top=e;/向栈压入一个元素 int get() int temp; temp=*top; *top-=-1; return temp;/弹出栈的一个元素 ;/将棋盘转换为一个二维数组/int A8=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;/void display();/输出模拟的八皇后棋盘 void display(int ,int);/display函数的重载 void Main();/主体函数 bool deal();/对棋盘进行横、竖、斜等方面的处理/主函数/int main() display(); Main(); system("pause"); return 0;/输出象棋棋盘/void display() cout<<"当前八皇后棋盘：n" for(int i=0;i<=63;+i)/用一维方法处理二维数组 cout<<Ai/8i%8<<' ' if(i%8=7)cout<<endl; /display函数的重载 /void display(int a,int b) cout<<"当前八皇后棋盘：n" Aab=1; for(int i=0;i<=63;+i)/用一维方法处理二维数组 cout<<Ai/8i%8<<' ' if(i%8=7)cout<<endl; /菜单函数/void Main() int k(1);/记录当前的步数 int x,y,judge(0);/横竖坐标及悔棋次数 Stack X,Y;/两个栈分别记录每次的横竖坐标输入 while(k) while(1)/坐标输入及坐标输入的错误处理 cout<<"请输入第"<<k<<"个皇后的坐标" cin>>x>>y; if(x<1|x>8)|(y<1|y>8)cout<<"a坐标错误！请您输入18整数。n" if(Ay-1x-1=1)cout<<"输入坐标重复，请重新输入。n" else break; X.push(x-1); Y.push(y-1);/横纵坐标入栈 system("CLS");/清屏，使界面更加简洁。 display(y-1,x-1); if(!deal() cout<<"游戏结束n"<<"总得分："<<10*k+20-15*judge<<endl <<"是否悔棋(Y/N)? (每步悔棋将扣除15分)n" char j; cin>>j; if(j='y'|j='Y')/输入悔棋步数及错误处理 cout<<"悔棋几步？n" int i; while(i) cin>>i; if(i>k|k<1)cout<<"a请输入1"<<k<<"的悔棋数：n" else break; k=k-i; for(int a(0);a<i;+a)/悔棋的实现，将坐标置零 AY.get()X.get()=0; judge=judge+i; system("CLS"); display(); else break; ; if(k=8) cout<<"恭喜你过关，总得分："<<10*k+20-15*judge; break; k+; /对棋盘进行计算/bool deal() int temp08=0/*横排上元素之和*/,temp18=0/*竖直线上的元素之和*/, temp215=0/*右斜线上的元素之和*/,temp315=0/*左斜线上的元素之和*/; /横排上元素求和的实现 for(int i(0);i<=7;+i) for(int j(0);j<=7;+j) temp0i+=Aij; /竖直线上求和计算的实现 for(int i(0);i<=7;+i) for(int j(0);j<=7;+j) temp1i+=Aji; /斜线上求和计算的实现 for(int i(0);i<=7;+i) for(int j(0);j<=7;+j) /右斜线上求和计算的实现 if(j+i>=8); else temp2i+= Aj+ij; if(j>i|i>6); else temp2i+8+=Aj7-i+j; /左斜线上求和计算的实现 if(i<j); else temp3i+=Ai-jj; if(i+j+1>7); else temp3i+8+=A7-ji+j+1; /如果横、竖、斜排元素和有一个大于1，则当前皇后至少于之前一个皇后有冲突，返回false. for(int i(0);i<=14;+i) if(temp0i/2>1|temp1i/2>1|temp2i>1|temp3i>1) return false; return true;/程序截图：