结构化程序设计归纳算法设计技术的应用实验报告

1、福建工程学院计算机与信息科学系实验报告20112012 学年第 二 学期 任课老师：实验题目归纳算法设计技术的应用实验时间实验开始日期：2012/5/1报告提交日期：2012/5/5实验目的、要求有些问题看来很复杂，但它们是有一定规律的。只要深入细致地进行分析，找 到这些规律，然后按规律编制相应的程序，问题就迎刃而解了。例有n个硬币(n为偶数)正面朝上排成一排，每次将n-1个硬币翻过来放 在原位置，不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。设计程序 让计算机把翻币的最简过程以及翻币次数输岀(用*表示正面，0表示反面)分析：最后全部硬币翻成反面朝上为止，则每个硬币都是翻转奇数次，n个

2、奇数 之和为偶数次。假定最简单情况下共翻n轮，则n(n-1)为偶数，n为偶数。最简单情况下共翻n次，对于任意的硬币x,应该翻多少次呢？设为n(x)(奇数)次，则除x外其他n-1个硬币要一起翻转n-n(x)次(奇数), n-n(x)=l, 3, 5,，nt考虑n-n(x) =3, 5, , n-1的情况,将nt个硬币翻转 3次或者更多次得到的结果与翻转一次的结果完全相同，且比翻转一次更麻烦，不 是最简单过程，因此，只有n-n(x)=l才满足要求，即n(x)=n-l,又由于x的任意 性，可知，每个硬币的翻转次数都是叶1次，因此总的翻转次数为n*(n-1),根据 n (n-1) =n* (n_l)可

3、得：n*n-n=n*n-n得n二n.即共翻转n次，其中每个硬币翻转次数为n-1。考虑到所有硬币翻转次数相同，因此可以将其看成一个环，从某个位置开始，先翻 转n-1个，再前进一步，翻转n-1个,直到完成翻转n次。二、实验题目1、有n个硕币(n为偶数)止面朝上排成一排，每次将n-1个硬币翻过来放 在原位置，不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。设计程序 让计算机把翻币的最简过程以及翻币次数输出(用*表示正面，0表示反面)2、有n个硬币(n为奇数)正面朝上排成一排，每次将n-2个硬币翻过來放 在原位置，不断地重复上述过程，直到最后全部硬币翻成反而朝上为止。设计程序 让计算机把翻币的最

4、简过程以及翻币次数输出(用*表示正面，0表示反面)三、实验要求1.该实验的课内学吋是4个课吋。加强要求：1)将1、2题集成为一个程序，根据用户输入判断奇数还是偶数，执行相应 的过程。实验设计内容(1)实验殺针的救据移构(i)运用数组存储硬币状态，初始值都为i,表示正面朝上，显示的结果都是* intslloooj;各个函数分析 翻硬币偶数，外循环i标记笫几个保持状态不变的硬币，内循环变量j判断每次翻硬币前都 需要判断是否为保持不变的硬币，若是则不变，若不是则与上次的翻转状态相反。/*翻硬币(偶数)*/int upcoineven(int coins_number) int i, j；for(i

5、= 0; i < coins_number; i+)printf(h第 %d 次翻硬币:n”,i+l);getchar();for(j = 0; j < coins_number; j+)if(j != i)sj = !sj;printf(n%3cn, sj?,*,:,o,);/l 为真,0 为假 翻硬币奇数，外循环i标记第儿个保持状态不变的硬币，内循环变量j判断每次翻硬币前都 需要判断是否为保持不变的硬币，若是则不变，若不是则与上次的翻转状态相反。当翻到最后 一趟的时候，把全部的状态输出为反面。/*翻硬币(奇数)*/int upcoino(kl(int coins_number)

6、int i,j;/i标记第几趟硬币的for(i = 0; i < coins_number; i+)printf(”第 %d 次翻硬币：n”,i+l);getchar();for(j = 0; j < coins_number; j+)if(j 匸 i&& j!=i+l)sj = !sfj；printf(”3c”, sfjl?绰丫0)；)printf(hnh);if(i=coins_number-2)getchar();prinrft第 %d 次翻硬币:n”,i+2); for(j = 0; j < coins_number; j+) printf(“3c”,

7、'0);printf(hnn);break; 实现翻硬币奇数或偶数的判断，调用相应的翻硬币过程 int main()int coins_number; intj;char choice2;while(l)printf(h请输入硬币的个数:n”)；scanf("%d",&coins_number);printf(”初始状态:nh);for(j = 0; j < coins_number; j+)sj = 1;所有硬币初始状态设置，设置正面向上printf(”3c“, printf("nn");if (coins_number%2=0)

8、upcoineven(coins_number)；elseupcoinodd(coins_number);print”是否继续进行翻硬币，若退出请按n或n,否则按任意键继续:“); scanf("%s",choice);if(strcmp(choice,"n',)=0|strcmp(choice,n,')=0)break;开始每次翻转n-1个 硬币t11r返冋卜*/5:x1fq每次翻转n-2个 、硬币，/1输入硬币 个数n/输出每次 /翻转情况 / 和为数调试过程记录 for(i = 0; i < coins_number; i+)print

9、f(”第 %d 次翻硬币：n”,i+l); getchar();for(j = 0; j < coins_number; j+)if(j 匸 i&& j!=i+l) sj = !sj; prmtf(n%3cn, sj?printf(hnu); if(i=coins_number-2) getchar(); printf(”第 %d 次翻硬币:n”,i+2); for(j = 0; j < coins_number; j+) printf(n%3c,0,);printf(hnu);break;当n为奇数时，要进行判断，当正面个数等于n2时，经过最后一次翻转结束。最 后一趟正面朝上分别在头尾，开始想用环来做，可是觉得链表麻烦，最后一趟的时 候做了个判断刚开始没有进行判断，所以出错。实验结果记录以及与预期结果比较以及分析 翻硬币奇数过程翻硬币奇数过程若始状态:第1次翻硬币:* * 0 0第2次翻硬币:0 m 0 m m第3次翻硬币：*00*0第4次翻硬币：第5次翻硬币:是否继续进行翻硬