《猴子吃桃问题数据结构解决.doc》由会员分享，可在线阅读，更多相关《猴子吃桃问题数据结构解决.doc（4页珍藏版）》请在三一文库上搜索。
1、 实习报告 题目:猴子吃桃问题一、需求分析1题目要求 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 1）采用数组数据结构实现上述求解；2）采用链数据结构实现上述求解；3）采用递归 实现上述求解。2 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。2、 概要设计 一个猴子摘了一些桃子,它每天吃了其中的一半然后再多吃了一个, 直到第10天,它发现只有1个桃子了,问它第一天摘了多少个桃子? 猴子分N天吃完了桃子,要想
2、求出第1天的桃子数,就先要求出第2天的桃子数,.因此,有: a1=(a2+1)*2; a2=(a3+1)*2; a3=(a4+1)*2; . a9=(a10+1)*2; a10=1; 3、 详细设计1) 采用数组数据结构实现#include using namespace std;static unsigned short arr10=0,0,0,0,0,0,0,0,0,1;void main() for (int i=9; i0; i-) arri-1=2*(arri+1); cout第i+1天还剩桃子：arriendl; cout第1天还剩桃子：arr0endl;2) 采用链数据结构实现#
3、include using namespace std;struct data unsigned short total; data* next;void main() data* p0; /哨兵结点 data* p1; p0=p1=new data; p0-total=1; /第十天剩1个桃 p0-next=p1; for (int i=9; i=1; i-) p1=new data; p1-total=2*(p0-next)-total+1); p1-next=p0-next; p0-next=p1; p1=p0-next; for (i=1; i=10; i+) cout第i天还剩桃子：totalnext; 3) 采用递归实现#include using namespace std;int eat(int n) if (10=n) return 1; else return 2*(eat(n+1)+1);void main() for (int i=1; i=10; i+) cout第i天还剩桃子：eat(i)endl; 四 测试结果1.数组数据结构实现2 链数据结构实现3.递归实现