1、 1 数数数数据据据据结结结结构构构构课课课课程程程程设设设设计计计计 设计题目： 猴子吃桃子问题 专业班级： 学生学号： 学生姓名： 2 目目目目 录录录录 一、一、 问题描述问题描述 . 3 二、二、 程序设计思想程序设计思想. 3 三、三、 软件模块结构图以及模块功能软件模块结构图以及模块功能. 4 四、四、 程序流程图程序流程图 . 8 五、五、 源程序源程序 . 9 六、六、 调试分析调试分析 . 11 七、七、 心得体会心得体会 . 14 3 一一、 问问题题描描述述 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再 多吃一个，到了第 10 天就只余下一个桃子。用多种方法实现
2、求出原 来这群猴子共摘了多少个桃子。 基基本本要要求求 1)采用数组数据结构实现上述求解 2)采用链数据结构实现上述求解 3)采用递归实现上述求解 二二、 程程序序设设计计思思想想 1分析题目。每天吃当前桃子数目的一半再加一个，所 以桃子数目肯定为偶数。用我们所熟悉的函数来表示，即： f(x+1)=f(x)/2-1;其中 x 代表第多少天。 ： 猴子摘桃子的那天也就是 第一天就吃了所摘桃子的一半加一个， 所以桃子总数应该为第一 天加 1 再乘以 2，等效为 f(0)。 2. 实现方法。 最容易想到的也是最简单的就是运用函数的 递归。给出了边界条件与递归函数，直接调用就可以了。用数组 实现，先定
3、义一个一维数组，然后结合循环，也可以求解。如果 用链表的话，相对来说要复杂点。先要构建一个动态链表， 将头 指针赋值给 p,p 赋值给 q， 使 p, q 同时指向链表头,将第十天的桃 子数放在链表第一个数据域中， 然后移动 p,q 使后一个数据域中 4 存放的是前一个加 1 的 2 倍，即倒过来存放数据。 三三、 软软件件模模块块结结构构图图以以及及模模块块功功能能 1. 用数组实现 int shuzu(int n) /*使用数组算法使用数组算法*/ int day11,i; day10=1; for(i=n;i0;i-) dayi-1=2*(dayi+1); printf(“%dt“,i)
4、; 猴子吃桃问题 用 数 组 实 现 用 递 归 实 现 用 链 表 实 现 用 常 规 实 现 5 printf(“%dn“,dayi); return day1; 2. 用常规方法实现 int cangui(int i) /*使用常规算法使用常规算法*/ int pee=1; for(i;i1;i-) pee=(pee+1)*2; return pee; 3. 用递归方法实现 int digui(int n) /*使用递归算法使用递归算法*/ int a; if(n=1) a=1; else a=(digui(n-1)+1)*2; return a; 6 4. 用链表方法实现 typedef int datatype; typedef struct link datatype tao; struct link *next; node; node *head; node *init_link(node *head) head=(node *)malloc(si
