第一篇：关于c语言编程中八皇后问题的设计报告
关于c语言编程中八皇后问题的设计报告
一、课题的来源及意义
八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。
在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。
到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。
二、面对的问题
1）解决冲突问题：这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；
2）使用数据结构的知识，用递归法解决问题。
三、需求分析
1、涉及到的知识
本次设计中，用到的主要知识有：递归法的运用，for语句的灵活运用，数据结构中树知识的灵活运用、栈及数组的掌握。
2、软硬件的需求
1)系统要求：winxp以上操作系统； 2)语言平台：tc++或vc++6.0；
3、功能需求
当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比较直观 的界面显示。
四、概要设计
我的思想是用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的92种变化表现出来。在这个程序中，我的主要思路以及思想是这样的：
1）解决冲突问题：
这个问题包括了行，列，两条对角线；
列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； 对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。
2）数据结构的实现
而对于数据结构的实现，学生则是着重于: 数组a[I]：a [I]表示第I个皇后放置的列；I的范围：1..8;对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后；
五、详细设计和实现
1、算法描述
A、数据初始化。
B、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置（n，m）是否等于0（未被占领）。如果是，摆放第n个皇后，并宣布占领（记得姚横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当n<=8，m=8时，发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不断“回溯”的寻找解的方法，称为“回溯法”。
C、使用数组实现回溯法的思想。D、当n>8时，便打印出结果。
E、输出函数我使用printf输出，运行形式为：第m种方法为：* * * * * * * *
2、算法流程图
六、代码编写及详细注释
#include
void main()/*----------------------------Main：主函数。----------------------------*/ { system(“title 叶青--递归算法八皇后问题 ”);cout<<“ ”<<“八皇后的解法：”< { Output();return;} for(i = 1;i <= QUEENS;i++)//!n还没到8，在第n行的各个行上依次试探。 { Site[n] = i;//!在该行的第i行上放置皇后。 if(IsValid(n))//!如果放置没有冲突，就开始下一行的试探。 Queen(n + 1);}} int IsValid(int n)/*------IsValid：判断第n个皇后放上去之后，是否合法，即是否无冲突。------*/ { int i;for(i = 0;i < n;i++)//!将第n个皇后的位置依次于前面n－1个皇后的位置比较。 { if(Site[i] == Site[n])//!两个皇后在同一列上，返回0。return 0;if(abs(Site[i]i))//!两个皇后在同一对角线上，返回0。return 0;} return 1;//!没有冲突，返回1。} void Output()/*------------Output：输出一个解，即一种没有冲突的放置方案。------------*/ { int i;printf(“No.%-5d” , ++iCount);//!输出序号。 for(i = 0;i < QUEENS;i++)//!依次输出各个行上的皇后的位置，即所在的列数。printf(“%d ” , Site[i]);printf(“n”);} 七、程序调试 调试过程、步骤及遇到的问题 在完整程序调试时遇到几个小问题，后经细心改正后才把调试工作做完。 例如:当用printf输出时,出现了一些错误,几经调试后,发现原来是缺少了stdio.h这样一个头文件,添加了头文件后, 还出现了一些问题,逻辑错误导致程序死循环或不循环或循环一小部分,但是编译时却没有错误,就是没有正确的输出答案,一开始我也不知道是怎么回事,通过和同学的交流,发现是逻辑错误,经过改正后,程序终于可以运行了.八、运行与测试 运行演示 九、总结 在这次的程序设计，我从中得到了许多的经验以及软件设计的一些新的思路；从这个八皇后问题设计以及分析中，本人从中理解到了数据结构对于计算机软件设计的重要性，它的使用，可以改变一个软件的运行周期，也可以将软件的思路从繁化简，并且都能够通过数据结构的相关引导，将本身以前编程思想进行扩充，发展；这也是在这次课程设计中我所掌握得到的。 但由于我的基本知识还不是那么扎实，也缺乏对软件设计的经验，在这过程中也出现了一些问题，如，八皇后在变成初期由于没真正体会到数据结构中“树”在里面的运用，将程序往大一时c语言的方向发展，不自觉的采用了非递归的算法，结果大大增加了程序的复杂程度。并且也让整个程序的时间复杂度变得更大；在后来学生对数据结构的第六章进行了比较深入的研读，才发现了数据结构树的实际运用的空间是相当的大，并且，通过了重温树的回溯，以及二叉树的遍历，最终将程序进行了一次较大的改造。并且通过思考，再将以前的数组知识加以运用才最终解决了这个问题，整个程序的算法的可看性也有了相当的改进。 以前对数据结构的学习还是具有相当大的意义，它从一个程度上改变了我们的编程思想，如何将一个程序快速而又准备的进行编写，进行编译，都成为了我们思考的重点，也通过这一门课的学习，我们将数据结构的思想带入到了我们以后的编程学习中去。在这个阶段，我也明白了，好的思想，不能提留于字面上的认知，还需要的是平时多练多写一些相关的程序，并且通过修改，加入新的算法去尝试改变自己的一些编程思想。保持更新算法的速度，这才是关键。 我觉得还可以考虑开发N皇后问题,在主界面中添加一个 int型的变量,程序一开始要求输入一个数(确定是几皇后问题),输入后按下 enter 后,输出各种解.主程序与八皇后的求解大体相同.十、参考文献 [1]苏仕华,数据结构课程设计.-北京:机械工业出版社,2005.5 [2]于永彦,赵建洋.课程设计指导书.淮安：江苏淮阴工学院 计算机工程系,2006 [3]刘振安,刘燕君，孙忱.C++语言课程设计.北京：高等教育出版社,2003 [4]陈志泊, 张海燕, 王春玲.Visual C++程序设计.中国铁道出版社 ,2005 [5]吕凤哲,C++语言程序设计（第二版）.北京：电子工业出版社,2005 [6]殷人昆，陶永雷等.数据结构（用面向对象方法与C++）.北京:清华大学出版社，1999 [7]严蔚敏，吴伟民，数据结构．北京：清华大学出版社，1997 [8]李春葆.数据结构—考研指导.北京:清华大学出版社,2002 [9]陈慧南．数据结构—C++语言描述．北京：人民邮电出版社，2005．03 数据结构 实习报告 专业：数字媒体技术 姓名：李义 年级：2013级 学号：201301052015 完成日期：2015.12.31 题目：八皇后问题 一、项目简介 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在88格的国际象棋棋盘上，安放八个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即任意两个皇后都不能处于同一行、同一列或同一条对角线上，求解有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法得出结论，有92种摆法。 二、概要设计 2.1 主要模块： 这个程序主要由4个模块组成，分别是画棋盘模块，画皇后模块，输出皇后摆法模块，和解决如何摆置皇后模块。这4个模块隶属于主函数模块。既主函数通过对这4个模块的合理调用解决“8皇后问题”，同时这4个模块之间也互有调用。 2.2 程序设计的数据结构及其关系： 数据结构的实现：数组a[i]：a [i]表示第i个皇后放置的列；i的范围：1-8;对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后；然后进行数据的初始化。从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于０（未被占领）:如果是，摆放第n个皇后，并宣布占领(切记要横列竖列斜列一起来)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当时，却发现此时已经无法摆放时，便要进行回溯。 三、详细设计 3.1 定义相关的数据类型： 3.1.1 定义的相关数据类型： int A[21],B[21],C[21],Y[8];void *buff1,*buff2 3.1.2 设计思想： 本程序通过对子函数void qu(int i)的调用，将八皇后的问题关键通过数据结构的思想予以了实现。虽然题目以及演算看起来都比较复杂，繁琐，但在实际中，只要当一只皇后放入棋盘后，在横与列、斜线上没有另外一只皇后与其冲突，再对皇后的定位进行相关的判断。即可完成。如果在这个程序中，我们运用的是非递归的思想，那么将大量使用if等语句，并通过不断的判断，去推出答案，而且这种非递归的思想，大大的增加了程序的时间复杂度。如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。这个程序，我运用到了数据结构中的栈、数组，以及树和回溯的方法。特别是在对于树以及二叉树的学习，更是为八皇后的问题提供了科学的解决方案，通过对树的分析，把八皇后的问题看成了树，而在衍生第一个变化后，上面的第一层八个变化就变成了八个结点，而这八个结点再继续的衍生„„，这样比较形象的将八皇后的问题简单化了。然后再通过回溯法进行设计，回溯法是设计递归过程的一个重要的方法。它的求解过程实质上是一个先序遍历一棵“状态树“的过程。在这个程序设计中，它先进行判断，棋盘上是否已经得到一个完整的布局（即棋盘是否已经摆上8个棋子），如果是，则输出布局；如果不是则依次先根遍历满足约束条件的各棵子树，流程即是： 判断该子树根的布局是否合法：如果合法的话，则先根遍历该子树；如果不合法的话，则剪去该子树的分支。 3.2 相关代码及算法 3.2.1 主模块C码算法： void main(void){ Queen Q; int gdriver=DETECT,gmode; initgraph(&gdriver,&gmode,“D://Win-TC”); SetQueen(&Q); setcolor(YELLOW); QueenPic(); cleardevice(); setcolor(LIGHTGREEN); settextstyle(0,0,3); outtextxy(180,10,“Eight Queens”); setcolor(WHITE); settextstyle(0,0,1); outtextxy(250,400,“2009.11.8 3:30pm”); QueenRe(&Q,0); getch(); closegraph();} 3.2.2 棋盘模块C码算法 void Checker(void) /* 画棋盘函数 */ { int i,k; for(k=0;k<8;k++) for(i=0;i<8;i++) if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){ setfillstyle(SOLID_FILL,LIGHTBLUE); setcolor(LIGHTBLUE); rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20); floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else { setfillstyle(SOLID_FILL,WHITE); setcolor(WHITE); rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20); floodfill(i*20+10,20+k*20+10,WHITE);} } 3.2.3 皇后模块C码算法： void QueenPic(void) /* 画皇后图象，然后存储到缓冲区 */ { int size，polypoints1[10]={9,1,11,1,20,20,1,20,9,1}，polypoints2[10]={29,1,31,1,40,20,21,20,29,1}; setfillstyle(SOLID_FILL,LIGHTBLUE); /* 画淡蓝色棋格 */ setcolor(LIGHTBLUE); rectangle(1,1,20,20); floodfill(10,10,LIGHTBLUE); setfillstyle(SOLID_FILL,WHITE); /* 画白色棋格 */ setcolor(WHITE); rectangle(21,1,40,20); floodfill(30,10,WHITE); setfillstyle(SOLID_FILL,DARKGRAY); setcolor(YELLOW); drawpoly(5,polypoints1); drawpoly(5,polypoints2); floodfill(10,10,YELLOW); floodfill(30,10,YELLOW); size=imagesize(1,1,20,20); /* 计算缓冲区大小，然后存储 */ buff1=(void *)malloc(size); buff2=(void *)malloc(size); getimage(1,1,20,20,buff1); getimage(21,1,40,20,buff2); cleardevice();} 3.2.4 八皇后摆放方法模块C码: void QueenRe(Queen *Q, int y) 八皇后的递归算法 {int x; if(y>7) return; for(x=0;x<8;x++) if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])下一棵要遍历的子树由状态数确定 { Q->Y[y]=x;放置皇后 Q->A[x+7]=1;标记下次这里不能放置皇后 Q->B[x+y+7]=1;标记下次这里不能放置皇后 Q->C[x-y+7]=1;标记下次这里不能放置皇后 if(y==7) PrintQueen(Q);调用输出图形函数 QueenRe(Q,y+1);进入下一层递归 Q->A[x+7]=0;如果上次摆法导致后面不能继续摆放则重置标记为0 Q->B[x+y+7]=0; Q->C[x-y+7]=0; } } 3.2.5 初始化模块C码: void SetQueen(Queen *Q) /* 初始化 */ {int i; for(i=0;i<21;i++) {Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;初始化为0，表示可以放置皇后。} for(i=0;i<8;i++) Q->Y[i]=-1;} 3.2.6 图形输出： void PrintQueen(Queen *t) /* 图形输出函数 */ {int k; char str[20]; static total=0; total++; setviewport(240,80,400,260,1); /* 设置窗口 */ sprintf(str,“NO.%d”,total); setcolor(GREEN); settextstyle(0,0,1); outtextxy(0,0,str); Checker(); for(k=0;k<8;k++) if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0) putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);else putimage((t->Y[k])*20,20+k*20,buff2,COPY_PUT); getch(); if(getch()==27)exit(0); clearviewport();} void QueenRe(Queen *Q, int y) /* 八皇后的递归算法 */ {int x; if(y>7) return; for(x=0;x<8;x++) if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍历的子树由状态数确定 */ {Q->Y[y]=x; Q->A[x+7]=1; Q->B[x+y+7]=1; Q->C[x-y+7]=1; if(y==7) PrintQueen(Q); QueenRe(Q,y+1); /* 进入下一层递归 */ Q->A[x+7]=0; Q->B[x+y+7]=0; Q->C[x-y+7]=0;} } } 3.3函数调用图 3.4项目流程图 通过编译连接后，程序基本上把八皇后的92种摆法的都进行了演示； 但程 四、调试分析 序运行中也出现了以下缺点： 因为八皇后的表现方法甚多，输出后虽能全部显示，但未能使屏幕停留，把一个一个的将其显示出来,但是这样便使得操作步骤太多,也会造成不必要的麻烦!所以只画出了第一种和最后一种的输出结果，演示如图所示： 五、设计体会 该程序在调试的过程中出现了不少的问题！如数据溢出等（是自己过于粗心而造成的）。在调试的过程中出现的一个最大的问题就是：在运行的时候出现解的个数大于自己所预计的。经过不断的查看内存变量，操作次数但还是没有找出问题的所在。终于在晚上十二点的时候，决定睡觉！但一关上电脑，躺在床上的时候，突然想到了一个问题：经过读了一些资料，知道八皇后问题有12组实质解，92组全解——这说明在这12组实质解中有其中的一组解是比其它的解要特殊一点的：其它的解经过等价的变换之后都会产生8组等价的解，只有这个特殊的解只有4组等价的解。说不定我的问题就出在这里！我之前也写了一些有关的代码处理这个问题，但我之前以为这个特殊的解是一个完全中心对称的图形（每转90度得到的图形就是它自己本身），所以我的在这里的判断就出现错误了！后来经过相关代码的修改，问题终于解决了，程序正确运行。 本课程设计本人的目的也是通过用WIN-TC程序设计平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．最终将其问题变得一目了然，更加易懂。 六、用户使用说明 6.1 程序的使用平台： 系统要求：windows2000以上操作系统； 语言开发平台：WIN-TC； 6.2 源代码分析： 首先对程序中的函数头文件进行引入，定位；在这个程序中，与其他C++的程序一样，都是引入：#include 七、附录 #include void *buff1,*buff2;typedef struct { int A[21],B[21],C[21],Y[8];} Queen;void SetQueen(Queen *Q) /* 初始化 */ { int i;for(i=0;i<21;i++){ Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;} for(i=0;i<8;i++)Q->Y[i]=-1;} void QueenPic(void) /* 画皇后图象，然后存储到缓冲区 */ { int size, polypoints1[10]={9,1,11,1,20,20,1,20,9,1}, polypoints2[10]={29,1,31,1,40,20,21,20,29,1};setfillstyle(SOLID_FILL,LIGHTBLUE); /* 画淡蓝色棋格 */ setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);setfillstyle(SOLID_FILL,WHITE); /* 画白色棋格 */ setcolor(WHITE);rectangle(21,1,40,20);floodfill(30,10,WHITE);setfillstyle(SOLID_FILL,DARKGRAY);setcolor(YELLOW);drawpoly(5,polypoints1);drawpoly(5,polypoints2);floodfill(10,10,YELLOW);floodfill(30,10,YELLOW);size=imagesize(1,1,20,20); /* 计算缓冲区大小，然后存储 */ buff1=(void *)malloc(size);buff2=(void *)malloc(size);getimage(1,1,20,20,buff1);getimage(21,1,40,20,buff2);cleardevice();} void Checker(void) /* 画棋盘函数 */ { int i,k; for(k=0;k<8;k++)for(i=0;i<8;i++)if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){ setfillstyle(SOLID_FILL,LIGHTBLUE);setcolor(LIGHTBLUE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else { setfillstyle(SOLID_FILL,WHITE);setcolor(WHITE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,WHITE);} } void PrintQueen(Queen *t) /* 图形输出函数 */ {int k;char str[20];static total=0;total++;setviewport(240,80,400,260,1); /* 设置窗口 */ sprintf(str,“NO.%d”,total);setcolor(GREEN);settextstyle(0,0,1);outtextxy(0,0,str);Checker();for(k=0;k<8;k++)if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0)putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍历的子树由状态数确定 */ {Q->Y[y]=x;Q->A[x+7]=1;Q->B[x+y+7]=1;Q->C[x-y+7]=1;if(y==7)PrintQueen(Q);QueenRe(Q,y+1); /* 进入下一层递归 */ Q->A[x+7]=0;Q->B[x+y+7]=0;Q->C[x-y+7]=0;} } void main(void){ Queen Q;int gdriver=DETECT,gmode;initgraph(&gdriver,&gmode,“D://Win-TC”);SetQueen(&Q);setcolor(YELLOW);QueenPic();cleardevice();setcolor(LIGHTGREEN);settextstyle(0,0,3);outtextxy(180,10,“Eight Queens”);setcolor(WHITE);settextstyle(0,0,1);outtextxy(250,400,“2009.11.8 3:30pm”);QueenRe(&Q,0);getch();closegraph();} //回溯法之N皇后问题 当N>10，就有点抽了~~ /*结果前total行每行均为一种放法，表示第i行摆放皇后的列位置，第total+1行，输出total*/ #include int n,stack[100]; //存当前路径 int total; //路径数 void make(int l) //递归搜索以stack[l]为初结点的所有路径 { int i,j; //子结点个数 if(l==n+1) { total=total+1; //路径数+1 for(i=1;i<=n;i++) printf(“%-3d”,stack[i]);//输出第i行皇后的列位置stack[i] printf(“n”); exit; //回溯（若试题仅要求一条路径，则exit改为halt即可） } for(i=1;i<=n;i++) { stack[l]=i;//算符i作用于生成stack[l-1]产生子状态stack[l]; if(!att(l,i)) make(l+1); } //再无算符可用，回溯 } int att(int l,int i){ int k; for(k=1;k if(abs(l-k)==abs(stack[k]-i)||i==stack[k])return 1; return 0;} int main(){ printf(“N=”); scanf(“%d”,&n); total=0;//路径数初始化为0 make(1); //从结点1出发，递归搜索所有的路径 printf(“%dn”,total); system(“pause”); return 0;} 由回溯法的算法流程可以看出，除非边界条件设置不当而导致死循环外，回溯法一般是不会产生内存溢出的。但是，回溯法亦有其致命的弱点——时间效率比数学解析法低。为了改善其时效，我们可以从下述几个方面考虑优化： 1、递归时对尚待搜索的信息进行预处理，减少搜索量； 2、尽可能减少分支（解答树的次数）； 3、增加约束条件，使其在保证出解的前提下尽可能“苛刻”； 4、在约束条件中设置限定搜索层次的槛值。 设计题目及要求设计题目及要求设计题目及要求设计题目及要求 1.综合应用实例——学生成绩管理 编写一个菜单驱动的学生成绩管理程序。实现如下管理功能： （1）能输入并显示 n 个学生的 m 门考试科目的成绩、总分和平均分。 （2）按总分进行排序。 （3）按学号进行排序。 （4）任意输入一个学号，能显示该学生的姓名、各门功课的成绩 （5）将输入的学生成绩数据保存到文件中。 （6）从文件中读出学生成绩数据。 具体要求如下：）先用静态的数据结构（结构体数组）来存储和管理 n 个学生的学号、姓名、成绩等信息，进行编程。）排序函数是一个具有多种排序方式的、通用的、排序程序，即不仅可以实现成绩的升序排序，还可以实现成绩的降序排序。）程序能够进行异常处理，检查用户输入数据的有效性，在用户输入数据有错误（如类型错误）或无效时，不会中断程序的执行，程序具有一定的健壮性。）输出菜单形式如下： 1.输入学生记录 2.浏览学生记录 3.修改学生记录 4.排序 0.退出 请选择（0-4）: 5)排序菜单形式如下： 排序方式：1.按总分升序排序 2.按总分降序排序3.按学号排序 0.返回主菜单 请选择： 二二二二、、、、算法分析及实现步骤算法分析及实现步骤算法分析及实现步骤算法分析及实现步骤 总体算法分析的思路就是用调用函数来实现每个小程序的作用，首先是确定头文件，定义学生成绩结构体类型，用结构体函数实现。然后在函数执行过程中调用主菜单函数，紧接着被调用函数返回一个值给主函数，由返回来的值确定主函数应该执行下面的哪个步骤，再用一个while语句控制下面的几个步骤的循环，里面再嵌套switch语句来控制对每个小菜单程序的执行。例如：当调用函数返回“1”时，经过switch语句的判断之后就会执行相应的程序，最后，又会返回到主菜单程序中。其它的都一样。当调用函数返回的值是“4”时，此时因为排序里面还有一个排序的子菜单，所以此时这里我又用了一个switch语句来实现对排序程序的控制，也就是说在switch语句里面再嵌套switch语句。对排序程序进行的控制。等到跳出排序程序的时候，其它的都和之前的选择那样。其中，浏览每个学生信息的函数先计算出每个学生的平均成绩然后用for语句来实现每个学生信息的循环输入。修改学生信息的函数里面也用到了for语句，先找到相同的学号，然后在修改后循环执行。后来的排序程序都选用冒泡法来执行。当然一切程序都是从主函数开始执行。 三三三三、、、、源程序代码源程序代码源程序代码源程序代码 #include struct student//定义学生成绩结构体类型定义学生成绩结构体类型定义学生成绩结构体类型定义学生成绩结构体类型 { intno;charname[8]; floateng,phy,math,sum,ave;}; int menu(student s[],int n)//主菜单函数主菜单函数主菜单函数主菜单函数 { int k; cout<<“欢迎使用学生成绩管理软件欢迎使用学生成绩管理软件欢迎使用学生成绩管理软件欢迎使用学生成绩管理软件”< cout<<“"< cout<<”学生成绩管理系统菜单学生成绩管理系统菜单学生成绩管理系统菜单学生成绩管理系统菜单“< cout<<”1.输入学生记录输入学生记录输入学生记录输入学生记录“< cout<<”2.浏览学生记录浏览学生记录浏览学生记录浏览学生记录“< cout<<”3.修改学生记录修改学生记录修改学生记录修改学生记录“< cout<<”4.排序排序排序排序“< cout<<”0.退出退出退出退出“< cout<<”请选择请选择请选择请选择(0-4):“; cin>>k; returnk;} void Input(student s[],int n)//输输输输入入入入函数函数函数函数 { int i; cout<<”输入学号输入学号输入学号输入学号:“< for(i=0;i { cout<<”第第第第“< void Ave(student s[],int n)//浏览每个学生浏览每个学生浏览每个学生浏览每个学生信息的信息的信息的信息的函数函数函数函数 { int i;for(i=0;i { s[i].ave=(s[i].eng+s[i].phy+s[i].math)/3;s[i].sum=s[i].eng+s[i].phy+s[i].math; } cout<<”学号学号学号学号“<<'t'<<”姓名姓名姓名姓名“<<'t'<<”英语英语英语英语“<<'t'<<”物理物理物理物理“<<'t'<<”数学数学数学数学“<<'t'<<”总成绩总成绩总成绩总成绩“<<'t'<<”平均成绩平均成绩平均成绩平均成绩“<<'n'; for(i=0;i cout< } int Sort(student s[],int n)//排序的子菜单排序的子菜单排序的子菜单排序的子菜单函数函数函数函数 { int y; cout<<”排序方式排序方式排序方式排序方式:“< cout<<”1.按总分升序排序按总分升序排序按总分升序排序按总分升序排序“< cout<<”0.返回主菜单返回主菜单返回主菜单返回主菜单“< cout<<”请选择请选择请选择请选择:“; cin>>y; returny; } void change(student s[],int n)//修改学生信息的函数修改学生信息的函数修改学生信息的函数修改学生信息的函数 { int i,j; cout<<”请输入要修改的学生的学号请输入要修改的学生的学号请输入要修改的学生的学号请输入要修改的学生的学号:“; cin>>j; for(i=0;i { cout< cout<<”学生的信息学生的信息学生的信息学生的信息:“< cout<<”请输入修改的信息请输入修改的信息请输入修改的信息请输入修改的信息“< }} voidzpxs(student s[],int n)// 按总分升序按总分升序按总分升序按总分升序排序排序排序排序的函数的函数的函数的函数 { int i,j;studenttemp;for(i=0;i { s[i].ave=(s[i].eng+s[i].phy+s[i].math)/3;s[i].sum=s[i].eng+s[i].phy+s[i].math;} for(i=0;i { for(j=0;j { temp=s[j];s[j]=s[j+1];s[j+1]=temp; }} cout<<”学号学号学号学号“<<'t'<<”姓名姓名姓名姓名“<<'t'<<”英语英语英语英语“<<'t'<<”物理物理物理物理“<<'t'<<”数学数学数学数学“<<'t'<<”总成绩总成绩总成绩总成绩“<<'t'<<”平均成绩平均成绩平均成绩平均成绩“<<'n'; for(i=0;i cout< } voidzpxj(student s[],int n)//按总分降序排序按总分降序排序按总分降序排序按总分降序排序的函数的函数的函数的函数 { int i,j;studenttemp;for(i=0;i {s[i].ave=(s[i].eng+s[i].phy+s[i].math)/3;s[i].sum=s[i].eng+s[i].phy+s[i].math;} for(i=0;i { for(j=0;j for(i=0;i cout< voidxhpxs(student s[],int n)//按学号升序排序按学号升序排序按学号升序排序按学号升序排序的函数的函数的函数的函数 {int i,j;studenttemp;for(i=0;i for(i=0;i {for(j=0;j for(i=0;i cout< void main()//主函数主函数主函数主函数 { int i,g;studentstu[3];while(i){i=menu(stu,3);switch(i){case 1:Input(stu,3);cout<<”“< cout<<”“< cout<<”“< cout<<”“< 人工智能课程设计报告 课 程:人工智能课程设计报告 班 级: 姓 名: 学 号: 指导教师:赵曼 2015年11月 人工智能课程设计报告 人工智能课程设计报告 课程背景 人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，可以设想，未来人工智能带来的科技产品，将会是人类智慧的“容器”。 人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能，但能像人那样思考、也可能超过人的智能。 人工智能是一门极富挑战性的科学，从事这项工作的人必须懂得计算机知识，心理学和哲学。人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。 人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。 人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。 人工智能课程设计报告 a[] a[i]=0表示第i行上还没有皇后； b[] b[i]=0表示第i列反斜线/上没有皇后； c[] c[i]=0表示第i列正斜线上没有皇后。 棋盘中同一反斜线/上的方格的行号与列号相同；同一正斜线上的方格的行号与列号之差均相同，这就是判断斜线的依据。 初始时，所有行和斜线上都没有皇后，从第1列的第1行配置第一个皇后开始，在第m列，col[m]行放置了一个合理的皇后，准备考察第m+1列时，在数组a[]，b[]和c[]中为第m列，col[m]行的位置设定有皇后的标志；当从第m列回溯到m-1列时，并准备调整第m-1列的皇后配置时，清除在数组a[],b[]和c[]对应位置的值都为1来确定。 2)遗传算法 遗传算法的基本运算过程如下： a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价：计算群体P(t)中各个个体的适应度。遗传算法 遗传算法 c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。 e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。 f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。 3）csp最小冲突法 （1）初始化N个皇后的一个放置，允许有冲突 （2）考虑某一行的某个皇后，她可能与x个皇后冲突，然后看看将这个皇后移动到这一行的哪个空位能使得与其冲突的皇后个数最少，就移动到那里。（也可以考虑列，是等价的）（3）不断执行（2），直到没有冲突为止 2.数据结构 使用数组结构存储相关数据 一维数组： t + n] == 1||rd[i + t] == 1)continue; //没有冲突 ver[i] = 1;ru[i 人工智能课程设计报告 } } //后退处理 rd[i + t] = 0;ru[i1;i++){ } cout << endl;*/ cout << “row:” << i << “ col:” << this->ChromosomeMatrix[i][0] << endl;g = 1;if(DisplayAllAnsures)this->FillArea(k);this->CostMatrix[k] = this->CostFunc(k);bool DisplayAllAnsures=PrintChessBoard;//是否输出所有棋盘结果 int g = 0, num = 0; //逐个检查第row行的每个位置，看看是否存在冲突数更小的位置 for(int i = 0;i < N;i++){ } if(i == cur_col)continue; int conflict = col[i] + pdiag[GetP(row, i)] + cdiag[GetC(row, i)];if(conflict < min_conflict){ } min_conflict = conflict;optimal_col = i;+ cdiag[GetC(row, optimal_col)] 人工智能课程设计报告 } } col[optimal_col]++;pdiag[GetP(row, optimal_col)]++;cdiag[GetC(row, optimal_col)]++;R[row] = optimal_col;if(col[cur_col] == 1 && col[optimal_col] == 1 } && pdiag[GetP(row, optimal_col)] == 1 && cdiag[GetC(row, optimal_col)] == 1){ return Qualify();//qualify相对更耗时，所以只在满足上面基本条件后才检查 //否则当前点就是最佳点，一切都保持不变 return false;//如果都没变的话，肯定不满足终止条件，否则上一次就应该返回true并终止了 //检查冲突 bool CSP_Queens::Qualify(){ } //最终用户调用函数，numOfQueens为输入皇后数，PrintChessBoard判断是否输出棋盘表示 int CSP_Queens::CSPAlgorithms(bool PrintChessBord){ srand((unsigned)time(NULL));Init();if(Qualify()){//运气很好，初始化后就满足终止条件 } bool end = false;while(!end){ for(int i = 0;i < N;i++){ if(Adjust_row(i)){ end = true;if(PrintChessBord)Print_result();return 0;for(int i = 0;i < N;i++){ } return true;if(col[R[i]]!= 1 || } pdiag[GetP(i, R[i])]!= 1 || cdiag[GetC(i, R[i])]!= 1){ return false; 人工智能课程设计报告 2.遗传算法 3.CSP最小冲突算法 人工智能课程设计报告 总的来说，回溯在n值很小时，效率很高，但其求解范围很小，超过35基本就解不出来，遗传算法求解范围适中。在n值很大(>100)时，前两者都不能再解决，此时，CSP最小冲突法的效率最高，且与n值没有必然的联系。 总结 通过此次课程实习不仅大大加深了我对几种经典搜索算法的理解，而且帮助我很好的复习了队列、堆栈、图、文件读写这几部分的内容，使我对几种基本的数据结构类型的运用更加熟练。在解决这些问题的过程中我不但很好的巩固了数据结构的相关知识，而且提高了编程及程序调试能力，增强了自己编程的信心。 总之，在这次课程实习过程中我是实实在在学到了一些课堂上学不到的东西，同时也提高了实践能力。同时在这个过程中也暴露了自己的不少问题，在今后的学习过程成也会更加有针对性。最后还要感谢老师的悉心指导，解答我编程过程中的疑问、指出我程序中的不足，及提出可行的解决方法，让我的程序的功能更加完善。 CSP算法源代码： //CSPAlgorithms.h #pragma once class CSP_Queens { public: //构造函数，numOfQueens为输入皇后数，CSP_Queens(int numOfQueens);~CSP_Queens(); private: //row[i]表示当前摆放方式下第i行的皇后数，int *row;//col[i]表示当前摆放方式下第i列的皇后冲突数 int *col;int N;//放置N个皇后在N*N棋盘上 //从左上到右下的对角线上row-col值是相同的，但是这个值有可能是负值，最小为 12]，2*N-1条，作为对角线编号 //R[]用来存储皇后放置位置，R[row] = col表示(row,col)处,即“第row行第col列”//cdiag[i]表示编号为i的对角线上的皇后数 int *cdiag;//counter diagonal,副对角线 有个皇后 int *R; public: int swap(int &a, int &b); //给定二维矩阵的一个点坐标，返回其对应的左上到右下的对角线编号 int GetP(int row, int col);//给定二维矩阵的一个点坐标，返回其对应的右上到左下的对角线编号 int GetC(int row, int col);//返回begin, begin + 1,..., endbegin个数中的随机的一个 int My_rand(int begin, int end);//左闭右开[begin, end) 人工智能课程设计报告 N = numOfQueens;row = new int[N];col = new int[N];pdiag=new int[2 * N];cdiag=new int[2 * N];R=new int[N];} CSP_Queens::~CSP_Queens(){ if(NULL!= row)delete[]row;if(NULL!= col)delete[]col;if(NULL!= pdiag)delete[]pdiag;if(NULL!= cdiag)delete[]cdiag;if(NULL!= R)delete[]R;} int CSP_Queens::swap(int &a, int &b){ int t = a;a = b;b = t;return 0;} // int CSP_Queens::GetP(int row, int col){ return row1;} int CSP_Queens::GetC(int row, int col){ return row + col;} //返回begin, begin + 1,..., endbegin个数中的随机的一个 int CSP_Queens::My_rand(int begin, int end)//左闭右开[begin, end){ return rand()%(end 人工智能课程设计报告 { } for(int i = begin;i <= end1;i++){ pdiag[i] = 0;cdiag[i] = 0;} //初始化当前棋局的皇后所在位置的各个冲突数 for(int i = 0;i < N;i++){ col[R[i]]++;pdiag[GetP(i, R[i])]++;cdiag[GetC(i, R[i])]++;} //用最小冲突算法调整第row行的皇后的位置（初始化时每行都有一个皇后，调整后仍然在第 + cdiag[GetC(row, optimal_col)] 人工智能课程设计报告 } } //当前点就是最佳点，一切都保持不变 return false;//如果都没变的话，肯定不满足终止条件，否则上一次就应该返回true并终止了 } //检查冲突 bool CSP_Queens::Qualify(){ for(int i = 0;i < N;i++){ if(col[R[i]]!= 1 || pdiag[GetP(i, R[i])]!= 1 || cdiag[GetC(i, R[i])]!= 1){ return false; } } return true;} void CSP_Queens::Print_result(){ } cout << “-------结果为:” << endl;cout << endl;for(int j = 0;j < N;j++){ for(int k = 0;k < N;k++){ if(R[j] == k) cout << “Q”; else cout << “+”; cout << “ ”;} cout << endl;} //最终用户调用函数，numOfQueens为输入皇后数，PrintChessBoard判断是否输出棋盘表 人工智能课程设计报告 int N;cin >> N;int time1 = clock();CSP_Queens myQueens(N);myQueens.CSPAlgorithms(end);int time2 = clock();cout << “---” << N << “皇后问题耗时：” << time2 读书的好处 1、行万里路，读万卷书。 2、书山有路勤为径，学海无涯苦作舟。 3、读书破万卷，下笔如有神。 4、我所学到的任何有价值的知识都是由自学中得来的。——达尔文 5、少壮不努力，老大徒悲伤。 6、黑发不知勤学早，白首方悔读书迟。——颜真卿 7、宝剑锋从磨砺出，梅花香自苦寒来。 8、读书要三到：心到、眼到、口到 9、玉不琢、不成器，人不学、不知义。 10、一日无书，百事荒废。——陈寿 11、书是人类进步的阶梯。 12、一日不读口生，一日不写手生。 13、我扑在书上，就像饥饿的人扑在面包上。——高尔基 14、书到用时方恨少、事非经过不知难。——陆游 15、读一本好书，就如同和一个高尚的人在交谈——歌德 16、读一切好书，就是和许多高尚的人谈话。——笛卡儿 17、学习永远不晚。——高尔基 18、少而好学，如日出之阳；壮而好学，如日中之光；志而好学，如炳烛之光。——刘向 19、学而不思则惘，思而不学则殆。——孔子 20、读书给人以快乐、给人以光彩、给人以才干。——培根第二篇：数据结构八皇后问题实习报告（写写帮整理）
第三篇：回溯法之N皇后问题(C语言)
第四篇：C语言编程实训报告
第五篇：人工智能课程设计报告-n皇后问题解读
点击咨询 