折半算法的解决完整文档.docx

折半算法的解决完整文档数据结构其次次上机作业班级：070921姓名:张玲玲学号：07092017报告名称：利用递归进行编程上机时间：2010年9月29日报告时间：2010年10月5日试验目的：深化了解函数的调用与返回：理解递归函数的执行过程；学会利用函数的执行过程。试验方法：利用把迭代公式翻译成代码和确定终止代码的方法，写出递归函数，从而执行程序。试验结果：程序运行胜利，顺当得出结果。题1：八皇后问题【在8*8的棋盘上放置八个皇后，要求这八个皇后相互不能攻击（同行，同列，斜线）】一、问题重述：八皇后问题要求在一个8*8的棋盘上放上8个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击.依据国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子.因此，八皇后问题等于要求八个皇后中的随意两个不能被放在同一行或同一列或同一斜线上。而我的目的也是通过用C语言平台将一个8*8的棋盘上放上8个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个里后所攻击的92种结构予以实现.运用递归方法最终将其问题变得一目了然，更加易懂。二、算法描述：A、 数据初始化。B、 从n列起先摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置（n,m）是否等于O（未被占据）。假如是，摆放第n个皇后，并宣布占据（记得姚横列竖列斜列一起设置），接着进行递归；假如不是，测试下一个位置（n,m+1.）,但是假如当n=8,m=8时，发觉此时已无法摆放时，便要进行回溯。从问题的某一种可能动身，搜寻从这种状况能动身，接着搜寻,这种不断回溯的找寻解的方法，称为回溯法。C、运用数组实现回溯法的思想。D、当n8时，便打印出结果。E、输出函数我运用Prin1.f输出，运行形式为：第m种方法为：*算法流程图：三、结构体变量说明：intiCount=0;!记录解的序号的全局变量。intSiteQUEENS;!记录皇后在各行上的放置位置的全局数组。voidQueendntn）;/!递归求解的函数。voidOutputO;!输出一个解。intIsVa1.icKintn）：!推断第n个皇后放上去之后，是否有>冲突。四、函数说明：解决冲突问题：在这个问题中包括了行，歹J,两条对角线：歹生规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个空后占据后，则同一行上的全部空格都不能再放皇后，要把以I为下标的标记置为被占据状态；对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的全部点（设下标为（i,j）,要么（i+j）是常数，要么（1.j）是常数。因此，当第I个皇后占据了第J列后，要同时把以（i+j）、（i-j）为下标的标记置为被占据状态。对于数据结构的实现，着重于：数组aI：aI表示第I个皇后放置的列：I的范围：1.1. ;对角线数组：bj(主对角线)，cj(从对角线)，依据程序的运行，去确定主从对角线是否放入皇后：五、程序执行结果：六、遇到的问题：当用printf输出时，出现了一些错误,几经调试后，发觉原来是缺少了Stdio.h这样一个头文件,添加了头文件后，还出现了一些问题，逻辑错误导致程序死循环或不循环或循环一小部分,但是编译时却没有错误，就是没有正确的输出答案，一起先我也不知道是怎么回事，通过和同学的沟通，发觉是逻辑错误,经过改正后，程序最终可以运行了.七、附录：程序源代码inc1.udeconio.h4inc1.udemath.h#inc1.udestd1.ib.hinc1.udestdio.hinc1.udeiostream,hSdefineQUEENS8intiCount=0;!记录解的序号的全局变量。intSitetQ1.iEENS;!记录皇后在各行上的放置位置的全局数组。voidQueen(intn);！递归求解的函数。voidOutputO;/!输出一个解。intIsVa1.icKintn)：!推断第n个皇后放上去之后，是否有冲突。voidmain()(system(tit1.e递归算法八皇后问题）；COUt八皇后的解法：COUtend1.;end1.;Queen(O);!从第O行起先递归摸索。getch();!按随意键返回。voidQueen(intn)/*-Queen：递归放置第n个皇后，程序的核心!-*/inti;if(n=QUEENS)!参数n从0到8试出一个解，将它输出并回溯。Output();return;for(i=1;i=QUEENS;Siten=i;！在该行的第i行上放置皇后。if(IsVa1.id(n)!假如放置没有冲突，就起先下一行的摸索。Queen(n+1);intIsVa1.id(intn)/*推断第n个皇后放上去之后，是否合法无冲突。*/inti：for(i=0;in;i+)/!将第11个皇后的位置依次于前面n-1个皇后的位置比较。if(Sitei=Siten)!两个皇后在同一列上，返回Ooreturn0;if(abs(Sitei-Siten)=(n-i)！两个皇后在同一对角线上，返回0。return1:return0:!没有冲突，返回UvoidOutputO/*输出一个解，即一种没有冲突的放置方案。*/inti;printf(No.%-5d,+iCount);!输出序号。for(i=0;iQUEENS：i+)/!依次输出各个行上的皇后的位置，即所在的列数。printf(%t1.,Sitei);printf(11);题2：折半查找【用递归函数实现折半查找算法】一、问题重述：此程序即对于一个有序数列，满意s(1.)s(2).s(n),写出查找关键字为key的数据的折半查找的律法。首先将数列按有序化(递增或递减)排列，查找过程中采纳跳动式方式查找，即先以有序数列的中点位置为比较对象，假如要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。二、律法描述：折半查找的基本思路：先检查中间的数据是否是所需的数据，若不是则推断要查找的数据在中间数据的哪一边，下一次就在这个范围内查找。1、首先确定整个直找区间的中间位置mid=（a+b）/22、用待查关键字值与中间位置的关键字值进行比较：若相等，则查找胜利若大于，则在后（右）半个区域接着进行折半查找若小于，则在前（左）半个区域接着进行折半查找3、对确定的缩小区域再按折半公式，重复上述步骤。4、假如限定的范围中只剩下一个数（即起点、终点相同，a=b）,而这个数等于key,则返回a,否则每查找到返回7表示查找失败。折半查找的存储结构可以用一维数组sn表示这个有序数列，数列的起点、终点分别为a和bo三、结构体变量说明：折半查找递归函数，假如查找胜利，函数返回关键字所在位置，否则返回T定义了一个数组sn为有序数列，a、b分别为查找区间的起点和终点，key为查找关键字四、函数说明：1、定义了函数ha1.f。实现关键字与中间字的比较。2、定义了Sort（）函数把输入的数值按升序排列。3、定义了主函数Yoidmain（）,实现递归调用ha1.f。函数。五、程序执行结果：1、请输入数据的个数（少于100）：5请输入5个整数315263521按升序这5个数是：315212635请输入要查找的关键字：36关键字36没找到2、请输入数据的个数(少于IO0)：6请输入6个整数312724453按升序这5个数走：227314453请输入要查找的关键字：44关键字44已找到，位置是4六、遇到的问题：1、一起先把sort()函数放在了main。函数的后面，提示：toomanyargumentstofunctionvoidsort()'J02、在main函数中错误的再次定义了sort函数。七、附录：#inc1.udestdio.hintha1.f(ints,inta,intb,intkey)intmid;if(a=b)if(key=sa)return（八）;e1.sereturn(-1);e1.semid=(a+b)/2;if(keysmid)return(ha1.f(s,a,mid,key);if(keysmid)return(ha1.f(s,mid+1.,b,key)：if(key=smid)return(mid);voidsort(inta,intn)inti,j,temp,p;for(i=0;in-1;i+)p=i;for(j=i+1.;jn;j+)if(ajap)p=j;temp=ai;ai=ap;ap=temp;mainOinta100,i,n,pos,key：printf(n请输入数据的个数(少于100):);scanf(%d,n);printf(n请输入用d个整数n,n);for(i=0:in;i+)scanf(%d,ai);sort(a,n);printf(n按升序这d个数是：n,n);for(i=0;in：i+)printf(%d,ai);printf(n请输入要查找的关键字：)；scanf(%d,key);pos=ha1.f(a,0,n1.,key);if(posO)printf(n关键字%d没找到！n,key);e1.seprintf(n关键字%d已找到，位置是：%dn,key,pos);)