实用算法与程序设计算法

《实用算法与程序设计算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验一：N皇后：问题提出：在nXn格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。现在请你求在nF的棋盘上摆放n个皇后的方案数。输入格式一行，一个正整数n(nv13)输出格式一行，一个整数，表示所求的方案数使用到的数据结构:数组;//被调用函数程序伪代码：voidTry(inti,intn)for(j=1;j<=n;j++)//循环{if((C0]==1)&&(R[i+j]==1)&&(L[i-j+Normalize]==1))//表示第i行，第j列是安全的{q[i]=j；〃第一件事，占用

2、位置(i,j)C[j]=0;//修改安全标志，包括所在列和两个对角线L[i-j+Normalize]=0;R[i+j]=0;L[i-j+Normalize]=0;if(i

3、0;//方案数清零for(i=0;i<100;i++)//置所有列为安全C[i]=1；for(i=0;i<100;i++)//置所有对角线为安全{L[i]=1；}Try(1,j);printf(”％d皇后有％小中方案”,j,Num);//递归放置8个皇后，从第一个开始放解题过程及算法思想：①考虑用递归解决n皇后问题，首先定义函数Try[inti],用来表示尝试在第i行防止第i个皇后，用一个j的for循环，使q【i】=j,表示将第i行的第i个皇后放置在第j列。之后将对应位置的不安全位置标出②然后判断在此位置是否可行，故定义了三个数组LL100]ZD[1

4、00]XD【100】，分别用来标注在列正对角线斜对角线是否安全。③若通过判断了此位置可行的话，然后再判断此时i是否小于n,若小于，放置下一个皇后，即执行Try【i+1】；若不小于，则表明n皇后已放置完成，故让计数器number++；④考虑回溯问题，即当第i行j列不能放置该皇后时和最后1个皇后放置完了之后，将不安全标志改回安全。实现此步，就是在该for—j循环的判断语句后将所需位置置回安全即可。⑤最后编写主函数，就是把所有的安全标志先置安全后，然后执行函数Try[1]；最后输出计数器的值numbero空间复杂度分析：该算法时间复杂度为0(rfn)。实验结果

5、141皇后有1中方案2皇后有0中方案3呈后有0中方棊4皇后有2中方案5皇后有10中方案6皇后有4中方条7皇后肴40中方案8皇后■有92中方条9皇后有352中方案10皇后有724中方棊11皇后有2680中方案12皇后有14200中方案13皇后有73712中方案14皇后有365596中方案■Processexitedafter7.089secondswith:returnvalue0乐青按任意键继续・・・实验分析和总结：能在较短时间内获得结果的n值为14s。因为递推程序比较占用内存，而且注意到随着n值增加，输出值儿乎成指数倍数增氏,表明计算机所做运算量过大,

6、故16吋输出值已经较大难以输出。皇后的源代码其实和8皇后几乎相同。主要是要注意好回溯问题，即该在什么位置回溯。写的时候需要仔细思考安全标志该在何处置安全还是不安全。实验二：计算COSX的近似值问题的提出：编写一个程序计算Sinx和cosx的近似值，舍去的绝对值应小于「数据结构：无；程序伪代码：intmain(){doubleP=3.141592653,x,z,b=1,c=1,d;inti,f=1;scanf(&x,&z);if(x>2*P)for(i=1;;i++)x=x-2*P;〃将x的值先减小至2P以下if(fabs(x)<2*P)break;do

7、ublea=x,S=x,C=1;for(i=1;;i++){a=a*x*x/(2*i*(2*i+1)*(-1));操作if(fabs(a)

8、数学问题，将初始的x值缩小。实验结果截图：请输人要计算数的个数:•Jo1cosl