猴子吃桃子2.docVIP

用C语言解决猴子吃桃子问题 C语言 C语言隐藏 窗体顶端 窗体底端 用 C 语言解决猴子吃桃子问题摘 要 本课程设计主要解决猴子吃桃子的问题。一群猴子摘了一堆桃子，他们 每天都吃当前桃子的一半且再多吃一个，到了第 10 天就只余下一个桃子。用多 种方法实现求出原来这群猴子共摘了多少个桃子。在课程设计中，系统开发平台 为 Windows 2000， 程序设计设计语言采用 Visual C++， 数据库采用 MS SQL 2000， 程序运行平台为 Windows 98/2000/XP。在整个程序中分别采用数组数据结构、 链数据结构、递归等结构形式实现此问题的求解。程序通过调试运行，初步实现 了设计目标。 关键词 程序设计；C++；数组；链；递归；猴子吃桃 1 引 言 在日常生活中经常遇到一些与数据计算有关的问题， 许多与猴子吃桃问题类 似的问题要求用计算机程序语言来解决，用这个程序算法可以解决一些类似问 题，以便利于生活实际。 1.1 课程设计背景 猴子吃桃问题涉及一个比较有趣的数组，把猴子吃桃的天数倒过来看的话， 以天数作为数组的下标 i，剩下桃子的个数 a[i] 的递推公式为 a[i]=(a[i-1]+1)*2。 a[i]实际代表了倒数第 i 天剩下的桃子数。所以可以求得此数组的通项公式为 a[i]=3*pow（2，(i-1)）-2 (i=2) 1.2 课程设计目的 在这个程序中我们主要是用 C 语言解决猴子吃桃问题，一群猴子摘了一堆 桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第 10 天就只余下一个 桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 生活中或学术上有很多类似的问题，这个问题看似简单，却可能使很多重大 问题的重要组成部分或者是核心。 解决此问题的目的是以便在生活中解决根本性 问题，是生活变得更加便利。 1.3 课程设计内容 这个程序的内容是以 C 语言为程序语言载体分别用数组数据结构、链数据 结构、递归等结构形式实现此问题的求解。 2 需求分析 这个 课程设计 分为三个 部分， 即分别用 三种不同 的方法解 决猴子 吃桃 子问题。每个部分 都有不同的算法思想。 用数 组结构实 现的算法 ，通过 构造求桃 子数的数 组，然后 输出要 求的 项来实现。 用链 结构实现 的算法， 则是建 立链表， 将每天的 桃子数目 存入链 表， 然后输出第一天的 桃子数。 用递 归结构实 现的算法 ，是通 过函数本 身的特点 ，反复调 用自身 ，最 后找到递归的出口 ，求得算法的解。 3 概要设计 2.1 设计思路 C 是结构式语言。结构式语言的显著 特点是代码及数据的分隔化 ，即程 序的 各个部分 除了必要 的信息 交流外彼 此独立。 这种结构 化方式 可使程序 层次清晰，便于使用、维护以及调试。C 语言是以函数形式 提供给用户的， 这些 函数可方 便的调用 ，并具 有多种循 环、条件 语句控制 程序流 向，从而 使程序完全结构化 。 2.2 设计方案 如果 用数组结 构解决这 个问题 ，把猴子 吃桃的天 数倒过来 看的话 ，以 天数作为数组的 下标 i ， 剩下桃子的个数 a[i] 的递推公式为 a[i]=(a[i- 1]+1)*2 。 a[i] 实际代 表了倒数第 i 天剩下 的桃子数。 所以可以求 得此数组的 通项公式 为 a[i]=3*2e(i- 1)-2 (i=2)。 如果 用链结构 解决这个 问题， 建立一个 链表，根 据每天桃 子数与 后一 天桃子 数的关系 n=2*n+2, 依次将 每天的桃子 数存进链表 中，最后输 出第一 天的桃子数。 如果 用递归结 构解决这 个问题 ，要求利 用他们每 天都吃当 前桃子 的一 半且再多吃一个这 一特点，设计一个递归算法。 4 详细设计 3.1 数组结构 把猴子吃桃的天数 倒过来看的话，以天数作为数组的 下标 i ，剩下桃子 的个 数 a[i] 的递 推公式为 a[i]=(a[i- 1]+1)*2 。a[i] 实际 代表了倒 数第 i 天剩 下 的 桃 子 数 。 所 以 可以 求 得 此 数 组 的 通 项 公 式 为 a[i]=3*pow （2 ， (i- 1) ） -2 (i=2)。数组结构算法的 流程图如图 3-1：开 始 建立一个以天数为下标以 剩下桃子数为元素的数组 规定此数组的通向公式 求第一天的桃子数 结 束 图 3-1 int day,tao[11]; tao[0]=0; tao[1]=1; //定义数组和下标 //tao[0]赋值为 0 // 倒数第一天的桃子数为 1 for(day=2;day=10;day++) tao[day]=3*pow(2,day-1)-2; //给数组的赋值 printf(最初的桃子数为%d\n,tao[10])