N皇后及凸多边形C语言设计流程思路及源代码.doc

《N皇后及凸多边形C语言设计流程思路及源代码.doc》由会员分享，可在线阅读，更多相关《N皇后及凸多边形C语言设计流程思路及源代码.doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、成绩管理程序设计报告（凸多边形）一、问题描述输入N个点的坐标，判断这N个点能否构成一个凸多边形。 二、结构图 多边形判断体系数据输入类型判断三角判别结果输出三、数据结构的设计 int polygon(points nps) double var1,var2; int i,j,k; if(nps.pointNum3) return 0; /*如果多边形的顶点数小于3,返回0*/ for(i=0;inps.pointNum;i+) /*用循环判断任三点组成的三角形中有没有其它的点*/ j=(i+2)%nps.pointNum; k=(i+1)%nps.pointNum; var1=(nps.xi-

2、nps.xk)*(nps.yi-nps.yj)-(nps.yi-nps.yk)*(nps.xi-nps.xj); for(j=(j+1)%nps.pointNum;j!=i;j=(j+1)%nps.pointNum) var2=(nps.xi-nps.xk)*(nps.yi-nps.yj)-(nps.yi-nps.yk)*(nps.xi-nps.xj); if(var1*var22不是凸多边形是凸多边形任意三点组成的三角形中有没有其它的点YN 五、源程序#include #include #define N 100 /*定义一个字符常量*/ typedef struct /*定义一个新的数据类

3、型*/ double xN; double yN; int pointNum; points; int polygon(points nps) double var1,var2; int i,j,k; if(nps.pointNum3) return 0; /*如果多边形的顶点数小于3,返回0*/ for(i=0;inps.pointNum;i+) /*用循环判断任三点组成的三角形中有没有其它的点*/ j=(i+2)%nps.pointNum; k=(i+1)%nps.pointNum; var1=(nps.xi-nps.xk)*(nps.yi-nps.yj)-(nps.yi-nps.yk)*

4、(nps.xi-nps.xj); for(j=(j+1)%nps.pointNum;j!=i;j=(j+1)%nps.pointNum) var2=(nps.xi-nps.xk)*(nps.yi-nps.yj)-(nps.yi-nps.yk)*(nps.xi-nps.xj); if(var1*var20) return 0; /*有则返回0,表示不能构成凸多边形*/ if(var2!=0) var1=var2; if(var1=0) return 0; return 1; /*没有则返回1,表示能构成凸多边形*/ main() int i; points nps; printf(请输入顶点的个

5、数:); scanf(%d,&nps.pointNum); printf(请输入这些顶点的坐标，每个点的横坐标和纵坐标用逗号分隔开( 例如12.5,34 )：n); for(i=0;inps.pointNum;i+) /*用循环读入每个点的坐标*/ printf(第%d个顶点：,i+1); scanf(%lf,%lf,&nps.xi,&nps.yi); if(polygon(nps) /*根据子函数的返回值输出结果*/ printf(该多边形是凸多边形。n); else printf(该多边形不是凸多边形!n); 七、程序测试记录： 第一次： 请输入顶点的个数:第二次： 请输入顶点的个数:5

6、请输入这些顶点的坐标，每个点的横坐标和纵坐标用逗号分隔开( 例如12.5,34 )：第1个顶点：1,1第2个顶点：1,4第3个顶点：5,1第4个顶点：5,4第5个顶点：3,3该多边形不是凸多边形! Press any key to contunue第三次： 请输入顶点的个数:3 请输入这些顶点的坐标，每个点的横坐标和纵坐标用逗号分隔开( 例如12.5,34 )：第1个顶点：1,1第2个顶点：3,2第3个顶点：2,1该多边形是凸多边形。 Press any key to contunue第四次： 请输入顶点的个数:2 请输入这些顶点的坐标，每个点的横坐标和纵坐标用逗号分隔开( 例如12.5,34

7、 )：第1个顶点：2,1第2个顶点：5,1该多边形不是凸多边形! Press any key to contunue八、相关运行界面九、调试记录： 1、在开始时中未对顶点数大于3和小于3分开处理。在顶点数小于3时处， 无法构成三角，程序出现混乱。 2、在要求分数输入时，刚开始没注意应控制在输入时只能为数字，结果输入了字符或运算符没错，这与实际不符。 十、软件说明：1、本程序可基本判断是否为凸多边形2、由于数据较少，所以没有针对数据的存储和释放做过多准备（N皇后）一、 问题描述由n2个方块排成n行n列的正方形称为“n元棋盘”。如果两个皇后位于n元棋盘上的同一行或同一列或同一对角线上，则称它们为互

8、相攻击。要求输出使n无棋盘上的n个皇后互不攻击的所有布局。 具体要求如下； (1)n可由键盘输入。 (2)在输入n后，动态建立方法说明中所需要建立的数组空间；程序运行结束时释放该存储空间。 (3)分别用n4，5，6运行你的程序。二、 结构图空间管理N皇后问题数据输入递归分析结果统计屏幕清理 三、数据结构的设计 int SUM=0; /统计有多少种可能int shezhi() /设置为N皇后问题int N;printf(这是一个N皇后问题.n请输入N=);scanf(%d,&N);return N;void Print(int N,int x) /印出結果 int MAX=N; for(int

9、i=0;iMAX;i+) for(int j=0;jMAX;j+) if(j=xi) printf(); else printf(); printf(n); SUM+; /打印一种情况统计一次 printf(n);int Judge(int k,int x) /判断是否在同一直、橫、斜线上有其它棋子 int i;for(i=0;ik;i+)if( abs(k-i)=abs(xi-xk) | xi=xk ) /函数名: abs; 功能: 求整数的绝对值 ;return 0;return 1;void backtrack(int t,int N,int x) / 把棋子放到棋盘上 int MAX=

10、N; int i; for(i=0;iMAX;i+) xt=i; if(Judge(t,x) if(t=MAX-1)Print(MAX,x); / 找到其中一种放法，印出結果 else backtrack(t+1,N,x); 四、处理流程图：递归尝试第i+1行的摆放位置打印所有皇后的摆放位置否是回溯，撤销占据位置(i, j)j+iN-1在(i, j)位置摆放皇后宣布占据(i, j)位置(i, j)位置是否被占据否是是jNj=0循环终止否输入N五、源程序#include #include #include#include /用getch()要调用的头文件#include /要用system函数要

11、调用的头文件 int SUM=0; /统计有多少种可能int shezhi() /设置为N皇后问题int N;printf(这是一个N皇后问题.n请输入N=);scanf(%d,&N);return N;void Print(int N,int x) /印出結果 int MAX=N; for(int i=0;iMAX;i+) for(int j=0;jMAX;j+) if(j=xi) printf(); else printf(); printf(n); SUM+; /打印一种情况统计一次 printf(n);int Judge(int k,int x) /判断是否在同一直、橫、斜线上有其它棋

12、子 int i;for(i=0;ik;i+)if( abs(k-i)=abs(xi-xk) | xi=xk ) /函数名: abs; 功能: 求整数的绝对值 ;return 0;return 1;void backtrack(int t,int N,int x) / 把棋子放到棋盘上 int MAX=N; int i; for(i=0;iMAX;i+) xt=i; if(Judge(t,x)if(t=MAX-1)Print(MAX,x); / 找到其中一种放法，印出結果 else backtrack(t+1,N,x); void Introduce()printf(* * * * * * *

13、* * * * * * * * * * *n);printf(1.设置为N皇后问题。n);printf(2.输出棋局排布结果。n);printf(3.统计棋局排布总数。n);printf(4.清屏。n);printf(nn); void main() int N;int x10; printf(nnn); char flag=1;while(flag)int n;Introduce(); char a;printf(您确定要进行上述操作吗?(Y/N):);a=getchar();while(a=Y|a=y)printf(请选择：);scanf(%d,&n);switch(n)case 1:N=

14、shezhi();break;case 2:backtrack(0,N,x);printf(按任意键返回.); getch(); system(cls); Introduce(); break;case 3: printf(统计结果:%dn,SUM);printf(按任意键返回.); getch(); system(cls); Introduce(); break; case 4: printf(按任意键返回.);getch();system(cls);Introduce();break;default:printf(输入错误.n);printf(按任意键返回.);getch();system

15、(cls);Introduce();break;七、程序测试记录： 第一次 1.设置为N皇后问题。2.输出棋局排布结果。3.统计棋局排布总数。4.清屏。您确定要进行上述操作吗?(Y/N): 第二次 1.设置为N皇后问题。2.输出棋局排布结果。3.统计棋局排布总数。4.清屏。您确定要进行上述操作吗?(Y/N):y请选择：1这是一个N皇后问题.N=4请选择：2 第三次1.设置为N皇后问题。2.输出棋局排布结果。3.统计棋局排布总数。4.清屏。您确定要进行上述操作吗?(Y/N):y请选择：1这是一个N皇后问题.N=5请选择：2 第四次1.设置为N皇后问题。2.输出棋局排布结果。3.统计棋局排布总数。

16、4.清屏。您确定要进行上述操作吗?(Y/N):y请选择：1这是一个N皇后问题.N=6请选择：3统计结果：12 第五次1.设置为N皇后问题。2.输出棋局排布结果。3.统计棋局排布总数。4.清屏。您确定要进行上述操作吗?(Y/N):y请选择：1这是一个N皇后问题.N=6请选择：2等等。八、相关运行界面九、调试记录：函数内对每一个已经放好的皇后的位置进行判断，所以就要有个循环。用递归来解决问题并这个问题分成一个个相同的小问题来实现。建一个可以放好一行的函数backtrack（int t）里面的t表示是第几行，在main函数调用的时候第一次传进来的是0也就是从第一行开始判断。我们就开始写函数体循环里面

17、我们让xt=i也就是从这一行的第一个开始判断。放好后就要去判断是否符合条件。如果符合条件我们就在调用这个函数本身backtrack不过传进去的参数是t+1也就是下一行的意思。在进行判断下一行之前我们要判断一下t是不是等于8也就是已经是最后一行了，如果是最后一行了我们就可以将其进行输出。打印8*8的矩阵（提示在写一个函数）皇后的位置用1表示出来没有的用0表示。十、软件说明：1.解决八皇后问题根本（递归法）2.可上升为解决“N皇后问题”3.以直观形式输出棋局排布4.统计棋子排布方法总数5.清屏函数的调用十一、课程设计总结： 这次的设计课是人生一次真正的自己动手的程序设计！自己发现问题、解决问题，其中不仅对C和C+的操作有了进一步的掌握 ，还了解到了程序设计的书写风格及其注释的格式。本次我做的是“N皇后问题”，这是一个历史经典问题，经过资料查找，我发现关于八皇后问题的算法甚多，比如：回溯法，迭代法，递归法，残卷法等。经过思考，最后我决定使用递归的方法解决该问题。虽然我遇到了很多问题，但是经过资料查找，和网上提问，我们最终解决了问题。总的来说，这个程序虽不是十分复杂但也有许多要思考的地方，不但对一些基本的语法进一步的熟悉掌握了而且还有了新的体会，两个星期的努力还是换来了不少的收获！