《算法设计与分析》实验报告实验二.doc

计算机科学与工程学院武 汉 工 程 大 学计算机科学与工程学院算法设计与分析实验报告专业班级计算机工程01班实验地点计算机大楼403学生学号指导教师张立学生姓名实验时间2014-04-09实验项目基本的算法策略实验类别设计性实验实验目的及要求目的与要求：1) 掌握基本算法策略的设计思想与方法；2) 熟练掌握基本算法策略的选择与应用；3) 熟练掌握基本算法策略的编程实现与优化。实验内容要点：1) 分别用蛮力法和数学建模法求解同余方程组；成 绩 评 定 表类 别评 分 标 准分值得分合 计上机表现积极出勤、遵守纪律主动完成实验设计任务30分实验报告及时递交、填写规范内容完整、体现收获70分说明：评阅教师： 日 期： 年 月 日实 验 内 容（2）猴子吃桃子问题，猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了两个，第二天早上又将剩下的桃子吃掉一半，又多吃了两个，以后每天早上都吃了前一天剩下的一半零两个，到了第10天早上想再吃时，就只剩下两个桃子了，问第一天猴子摘了多少桃子？代码：#includestdio.hvoid main()int a=2,i;for(i=8;i=0;i-)a=(a+2)*2;printf(第一天猴子摘下%d个桃子n,a);测试： （3）54张扑克牌，两个人轮流拿牌，每人每次最少取一张牌最多取4张牌，谁拿最后一张谁输。编写模拟计算机先拿牌且必胜的算法。代码：#includestdio.hvoid main()int a,b,c,d,e,f;for(a=1;a=9;a+)for(b=0;b=9;b+)if(b!=a)for(c=0;c=9;c+)if(c!=ac!=b)for(d=0;d=9;d+)if(d!=a d!=b d!=c)e=a*1000+b*100+c*10+d;f=(a+b+c+d)*(a+b+c+d);if(e%f=0)printf(%d%d%d%dt,a,b,c,d);printf(n);测试： （8）寻找满足下列条件的四位数字：1.无重复数字；2.千位数字非零；3.能整除它的各个位数字和的平方。代码:#includestdio.hvoid main()int i,c;printf(游戏开始，计算机先拿牌!n);c=51;printf(计算机拿3张!还剩%d张n,c);while(c1)printf(请你拿牌，选择拿牌的张数（1-4张）n);scanf(%d,i);c=c-5;printf(计算机拿了%d张，还剩%d张n,5-i,c);printf(你拿最后一张，计算机赢了！n); 测试： #includestdio.hint amount=0, Board100100;void Cover(int tr, int tc, int dr, int dc, int size);void OutputBoard(int size);void main() int size=1,x,y,k,i; printf(输入K值:);scanf(%d,k);for (i=1;i=k;i+) size=size*2; printf(输入残缺个的位置x，y:);scanf(%d%d,x,y);Cover(0, 0, x, y, size);OutputBoard(size);void Cover(int tr, int tc, int dr, int dc, int size) int s,t;if (size2) return;amount= amount+1;t = amount; / 所使用的三格板的数目s=size/2; /子问题棋盘大小if (dr tr + s dc tc + s) /残缺方格位于左上棋盘 Cover(tr, tc, dr, dc, s);Boardtr + s - 1tc + s = t; /覆盖号三格板Boardtr + stc + s - 1 = t; Boardtr + stc + s = t; Cover (tr, tc+s, tr+s-1, tc+s, s); / 覆盖其余部分 Cover(tr+s, tc, tr+s, tc+s-1, s); Cover(tr+s, tc+s, tr+s, tc+s, s); else if(dr tr + s dc = tc + s) /残缺方格位于右上象限Cover(tr, tc+s, dr, dc, s);Boardtr + s - 1tc + s - 1 = t; / 覆盖号三格板 Boardtr + stc + s - 1 = t; Boardtr + stc + s = t; Cover (tr, tc, tr+s-1, tc+s-1, s); /覆盖其余部分 Cover(tr+s, tc, tr+s, tc+s-1, s); Cover(tr+s, tc+s, tr+s, tc+s, s); else if (dr = tr + s dc tc + s) /残缺方格位于覆盖左下 Cover(tr+s, tc, dr, dc, s);Boardtr + s - 1tc + s - 1 = t;/覆盖号三格板 Boardtr + s - 1tc + s = t; Boardtr + stc + s = t; Cover (tr, tc, tr+s-1, tc+s-1, s); /覆盖其余部分 Cover (tr, tc+s, tr+s-1, tc+s, s); Cover(tr+s, tc+s, tr+s, tc+s, s);else if (dr = tr + s dc = tc + s)/ 残缺方格位于右下象限Cover(tr+s, tc+s, dr, dc, s);Boardtr + s - 1tc + s - 1 = t; / 覆盖号三格板 Boardtr + s - 1tc + s = t; Boardtr + stc + s - 1 = t; Cover (tr, tc, tr+s-1, tc+s-1, s); /覆盖其余部分 Cover (tr, tc+s, tr+s-1, tc+s, s); Cover(tr+s, tc, tr+s, tc+s-1, s);void OutputBoard(int size) for (int i = 0; i size; i+)for(int j=0; j size; j+) printf(%-4d,Boardij);printf(n);实 验 总 结 这次的实验和上次的实验难度相差不大，猴子摘桃子的题目用到了倒推法，从最后一天一只推到第一天，即可得出结果。