归纳算法(翻硬币问题).doc

福建工程学院计算机与信息科学系实验报告 2010 2011 学年第 一 学期 任课老师： 实验题目归纳算法设计技术的应用实验时间实验开始日期： 2010/11/26 报告提交日期： 2010/11/26 实验目的、要求一、实验题目1、有N个硬币（N为偶数）正面朝上排成一排，每次将N-1个硬币翻过来放在原位置，不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。设计程序让计算机把翻币的最简过程以及翻币次数输出（用*表示正面，O表示反面）2、有N个硬币（N为奇数）正面朝上排成一排，每次将N-2个硬币翻过来放在原位置，不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。设计程序让计算机把翻币的最简过程以及翻币次数输出（用*表示正面，O表示反面）二、实验要求1该实验的课内学时是4个课时。加强要求：1）将1、2 题集成为一个程序，根据用户输入判断奇数还是偶数，执行相应的过程。实验设计内容（1）实验设计的数据结构(1)数组int s1000;（2）层次图(3) 各个函数分析/*翻硬币过程1（偶数）*/int Upturn_process1 (int coins_Number) int i, j; for(i = 0; i coins_Number; i+) printf(Step %d:n,i+1);/翻转步数 getchar(); for(j = 0; j coins_Number; j+) if(j != i) sj = !sj;/将i后面的硬币全部翻转过来 printf(%3c, sj?*:0);/sj=1时为正面，打印* ,否则打印0 printf(n); /*翻硬币过程2(奇数)*/int Upturn_process2 (int coins_Number) int i, j,count; for(i = 0; i coins_Number; i+) printf(Step %d:n,i+1); /翻转步数 getchar(); count=0; for(j = 0; j coins_Number; j+) if(j != i & j!=i+1) sj = !sj;/ 将i+1后面的硬币全部翻转过来 printf(%3c, sj? *:0); /sj=1时为正面，打印* ,否则打印0 if(sj) count+;/统计正面个数 printf(n); if(count=coins_Number-2) getchar(); printf(Stept %d:n,i+2); for(j = 0; j coins_Number; j+) printf(%3c,0); /当正面个数等于N-2时，进行最后一次翻转 printf(n); break; (5)流程图 调试过程记录 for(i = 0; i coins_Number; i+) printf(Step %d:n,i+1); getchar(); count=0; for(j = 0; j coins_Number; j+) if(j != i & j!=i+1) sj = !sj; printf(%3c, sj? *:0); if(sj) count+; printf(n); if(count=coins_Number-2) getchar(); printf(Stept %d:n,i+2); for(j = 0; j coins_Number; j+) printf(%3c,0); printf(n); break; 当N为奇数时，要进行判断,当正面个数等于N-2时，经过最后一次翻转结束。刚开始没有进行判断，所以出错。实验结果记录以及与预期结果比较以及分析总结以及心得体会有些问题看来很复杂，但它们是有一定规律的。只要深入细致地进行分析，找到这些规律，然后按规律编制相应的程序，问题就迎刃而解了。刚开始接触题目的时候，不知道是什么意思，后来通过直接翻转硬币找到了规律，最终也解决了问题。指导老师评阅意见指导老师： 年 月 日 #include #include #include #include int s1000;/*硬币状态标志，1时硬币是正面，0时硬币是反面*/*翻硬币过程1（偶数）*/int Upturn_process1 (int coins_Number) int i, j; for(i = 0; i coins_Number; i+) printf(Step %d:n,i+1); getchar(); for(j = 0; j coins_Number; j+) if(j != i) sj = !sj; printf(%3c, sj?*:0); printf(n); /*翻硬币过程2(奇数)*/int Upturn_process2 (int coins_Number) int i, j,count; for(i = 0; i coins_Number; i+) printf(Step %d:n,i+1); getchar(); count=0; for(j = 0; j coins_Number; j+) if(j != i & j!=i+1) sj = !sj; printf(%3c, sj? *:0); if(sj) count+; printf(n); if(count=coins_Number-2) getchar(); printf(Stept %d:n,i+2); for(j = 0; j coins_Number; j+) printf(%3c,0); printf(n); break; int main() int coins_Number; int j;printf(请输入硬币的个数:n);scanf(%d,&coins_Number); printf(初始状态：n); for(j = 0; j coins_Number; j+) sj = 1; /所有硬币初始状态设置，设置正面向上 printf(%3c, *); printf(nn);if (coins_Number%2=0) Upturn_process1 (coins_Number);else Upturn_process2 (coins_Number);题目描述： 一摞硬币共有m枚，每一枚都是正面朝上。取下最上面的一枚硬币，将它翻面后放回原处。然后取下最上面的2枚硬币，将他们一起翻面后再放回原处。再取3枚，取4枚直至m枚。然后再从这摞硬币最上面的一枚开始，重复刚才的做法。这样一直做下去，直到这摞硬币中的每一枚又都是正面朝上为止。例如，m为1时，翻两次即可。m为2时，翻3次即可；m为3时，翻9次即可；m为4时，翻11次即可；m为5时，翻24次即可；m为30时，翻899次即可； 输 入： 仅有的一个数字是这摞硬币的枚数m，0m1000。 输 出： 为了使这摞硬币中的每一枚又都是正面朝上所必需翻的次数。 输入样例： 30 输出样例： 899 程 序： program Programl；var m：integer；function solve (m：integer)：integer；vat i，t，d：integer；flag：boolean;beginif (m=1)thenso1ve：= else begind：=2*m+1；t：= 2;i：= 1;flag：=False；repeatif (t=1)thenbe