归纳算法：硬币翻转.doc

福建工程学院计算机与信息科学系
实验报告
2012 – 2013 学年第一学期任课老师: 章静
课程名称
C语言结构化编程
班级
计算机类1105班
座号
3110307518
姓名
裴和平
实验题目
分治算法设计技术的应用
实验时间
实验开始日期:
报告提交日期:
实验目的、要求
1、有N个硬币(N为偶数)正面朝上排成一排,每次将N-1个硬币翻过来放在原位置,不断地重复上述过程,直到最后全部硬币翻成反面朝上为止。设计程序让计算机把翻币的最简过程以及翻币次数输出(用*表示正面,O表示反面)
2、有N个硬币(N为奇数)正面朝上排成一排,每次将N-2个硬币翻过来放在原位置,不断地重复上述过程,直到最后全部硬币翻成反面朝上为止。设计程序让计算机把翻币的最简过程以及翻币次数输出(用*表示正面,O表示反面)
实验步骤与内容
按如下顺序写:
主要设计思想;
对于任意的硬币x,设翻转n(x)(奇数)次,则除x外其他N-1个硬币要一起翻转n-n(x)次(奇数),n-n(x)=1,3,5,…,n--n(x)=3,5,…,n-1的情况,将N-1个硬币翻转3次或者更多次得到的结果与翻转一次的结果完全相同,且比翻转一次更麻烦,不是最简单过程,因此,只有n-n(x)=1才满足要求,即n(x)=n-1,又由于x的任意性,可知,每个硬币的翻转次数都是n-1次,因此总的翻转次数为N*(n-1),根据n(N-1)=N*(n-1)可得: N*n-n=N*n-N得n=,其中每个硬币翻转次数为N-1。考虑到所有硬币翻转次数相同,因此可以将其看成一个环,从某个位置开始,先翻转N-1个,再前进一步,翻转N-1个,直到完成翻转N次。
主要数据结构及其解释
int Turncoin1 (int num,int s[]);//奇数n-2
int Turncoin2 (int num,int s[]);//偶数n-1
模块关系图;
Main主函数
Turncoin1()函数
Turncoin2()函数
流程图
所有函数的简