《算法设计与分析》递归算法典型例题
- 格式：docx
- 大小：34.32 KB
- 文档页数：9
下载文档原格式
合集下载
递归算法及经典例题详解
递归算法及经典例题详解
1.什么是递归
递归简单来说就是在运行过程中不断调用自己，直到碰到终止条件，返回结果的过程。
递归可以看作两个过程，分别是递和归。
递就是原问题把要计算的结果传给子问题；归则是子问题求出结果后，把结果层层返回原问题的过程。
下面设一个需要经过三次递归的问题，为大家详细看一下递归的过程：当然，现实中我们遇到递归问题是不会按照图中一样一步一步想下来，主要还是要掌握递归的思想，找到每个问题中的规律。
2.什么时候使用递归
递归算法无外乎就是以下三点：1.大问题可以拆分为若干小问题2.原问题与子问题除数据规模不同，求解思路完全相同3.存在递归终止条件
而在实际面对递归问题时，我们还需要考虑第四点：
当不满足终止条件时，要如何缩小函数值并让其进入
下一层循环中
3.递归的实际运用（阶层计算）
了解了大概的思路，现在就要开始实战了。
下面我们来看一道经典例题：
求N的阶层。
首先按照思路分析是否可以使用递归算法：
1.N！可以拆分为（N-1）！*N
2.（N-1）！与N！只有数字规模不同，求解思路相同
3.当N=1时，结果为1，递归终止
满足条件，可以递归：
publicstaticintFactorial(int num){if(num==1){return num;}return num*Factorial(num-1);}
而最后的return，便是第四步，缩小参数num的值，让递归进入下一层。
一般来说，第四步往往是最难的，需要弄清该如何缩
小范围，如何操作返回的数值，这一步只能通过不断
地练习提高了（当然如果你知道问题的数学规律也是
可以试出来的）。
递归算法典型例题数楼梯
递归算法典型例题数楼梯递归算法是一种常用的算法思想，它通过将问题分解为更小的子问题来解决复杂的计算任务。
在本文中，我们将探讨递归算法的一个典型例题——数楼梯。
问题描述：假设有n级楼梯，每次可以选择爬1级或2级，问有多少种不同的方式可以爬到楼梯的顶部。
解题思路：我们可以使用递归算法来解决这个问题。
假设f(n)表示爬到第n级楼梯的不同方式数目，那么可以得到以下递推关系：f(n) = f(n-1) + f(n-2)其中，f(n-1)表示从第n-1级楼梯爬1级到达第n级楼梯的方式数目，f(n-2)表示从第n-2级楼梯爬2级到达第n级楼梯的方式数目。
因为每次只能选择爬1级或2级，所以到达第n级楼梯的方式数目等于到达第n-1级楼梯的方式数目加上到达第n-2级楼梯的方式数目。
基本情况：当n=1时，只有一种方式可以到达第1级楼梯，即爬1级。
当n=2时，有两种方式可以到达第2级楼梯，即爬1级+1级或者直接爬2级。
递归算法实现：根据上述递推关系和基本情况，我们可以编写递归算法来解决这个问题。
```pythondef climb_stairs(n):if n == 1:return 1elif n == 2:return 2else:return climb_stairs(n-1) + climb_stairs(n-2)```测试与优化：我们可以通过调用climb_stairs函数来测试算法的正确性和效率。
```pythonn = 5result = climb_stairs(n)print("爬到第{}级楼梯的不同方式数目为：{}".format(n, result))```运行结果为：爬到第5级楼梯的不同方式数目为：8从结果可以看出，爬到第5级楼梯的不同方式数目为8，符合预期。
然而，上述递归算法存在一个问题，即重复计算。
在计算f(n)时，需要先计算f(n-1)和f(n-2)，而在计算f(n-1)时，又需要计算f(n-2)。
leetcode递归例题
leetcode递归例题以下是一篇关于LeetCode 递归例题的介绍：递归是算法设计中一种非常常见和有用的技术，它能够将一个复杂的问题分解成更小的子问题，从而简化问题的解决。
在LeetCode 算法题库中，有许多题目都可以使用递归方法解决。
下面我们将介绍几个经典的递归例题，帮助大家更好地理解递归的原理和应用。
1. 斐波那契数列题目描述：给定一个整数n，返回第n 个斐波那契数。
递归解法：```pythondef fibonacci(n):if n <= 1:return nelse:return fibonacci(n-1) + fibonacci(n-2)```在这个解法中，我们首先判断n 是否小于等于1，如果是，直接返回n。
否则，我们递归地调用fibonacci 函数来计算前两个斐波那契数，然后将它们相加得到第n 个斐波那契数。
需要注意的是，这种递归解法的时间复杂度是指数级的，因为它需要计算很多重复的子问题。
在实际应用中，我们需要考虑使用动态规划等其他方法来优化算法。
2. 反转链表题目描述：给定一个链表的头节点head，将其反转并返回新的头节点。
递归解法：```pythonclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverseList(head: ListNode) -> ListNode:if not head or not head.next:return headelse:new_head = reverseList(head.next)head.next.next = headhead.next = Nonereturn new_head```在这个解法中，我们首先判断头节点是否为空或者只有一个节点，如果是，直接返回头节点。
否则，我们递归地调用reverseList 函数来反转链表的剩余部分，然后将当前节点设置为反转后链表的头节点。
递归时间复杂度例题
以下是递归时间复杂度的例子：
1.计算整数x的n次方
暴力算法的时间复杂度为O(n)，空间复杂度为O(1)。
而使用递归算法，每次递归可以将问题规模减半，因此时间复杂度可以降低到O(logn)，但空间复杂度会增加到O(logn)。
2.斐波那契数列
斐波那契数列是一个经典的递归问题，其定义如下：F(0) = 0，F(1) = 1，F(n) = F(n-1) + F(n-2)（n >= 2）。
如果直接使用递归算法来计算斐波那契数列的第n项，时间复杂度会达到O(2^n)，因为会有很多重复的计算。
可以使用动态规划或记忆化搜索来优化算法，将时间复杂度降低到O(n)。
3.归并排序
归并排序是一种使用递归的排序算法，其基本思想是将待排序的数组分成两半，分别递归地对它们进行排序，然后将排好序的两个子数组合并成一个有序的数组。
归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。
4.汉诺塔问题
汉诺塔问题是一个经典的递归问题，其目标是将一堆大小不同的盘子从一个柱子移动到另一个柱子上，并满足以下条件：每次只能移动一个盘子；大盘子不能放在小盘子上面。
可以使用递归算法来解决汉诺塔问题，其基本思想是将问题分解成两个子问题：将上面的n-1个盘子从起始柱子移动到辅助柱子上，再将最大的盘子从起始柱子移动到目标柱子上，最后将n-1个盘子从辅助柱子移动到目标柱子上。
汉诺塔问题的时间复杂度为O(2^n)，空间复杂度为O(n)。
这些例子表明，递归算法的时间复杂度和空间复杂度取决于问题的性质和递归的实现方式。
因此，在设计递归算法时，需要仔细分析问题，选择合适的递归策略，并进行适当的优化。
算法设计与分析习题第二章分治与递归
2010-12-28
12
2.11 编写针对链表的快速排序程序。
需要保存指针信息。下面给出双向链表的快速排序算法 void fast_sort( Sdata *a, Sdata *f, Sdata *t ) { Sdata *i,*j,k,p; i = f; j = t; if ( t->lnext != f ) { k = a->data; //用于比较的基准数值 i = f; j = t; p = -1; while ( j != i )
7
2.7 按2.2.4节的描述，编写从二叉树中删除一个结点 的C语言程序 二叉树节点删除有三种情况： (1)*p是叶子(即它的孩子数为0)：无须连接*p的子树， 只需将*p的双亲*parent中指向*p的指针域置空即可。 (2)*p只有一个孩子*child：只需将*child和*p的双亲直接 连接后，即可删去*p。注意：*p既可能是*parent的左孩 子也可能是其右孩子，而*child可能是*p的左孩子或右孩 子，故共有4种状态。 (3)*p有两个孩子：先令q=p，将被删结点的地址保存在q 中；然后找*q的中序后继*p，并在查找过程中仍用parent 记住*p的双亲位置。*q的中序后继*p一定是 *q的右子树 中最左下的结点，它无左子树。因此，可以将删去*q的 操作转换为删去的*p的操作，即在释放结点*p之前将其 数据复制到*q中，就相当于删去了*q.
算法设计与分析习题
第二章 分治与递归
2010-12-28
1
2.1 对于顺序查找算法，分析目标值存在于数组中的 概率p趋于0的含义，这种情况下平均查找次数有什么 样的变化？当p趋于1时呢？ 见教材P12。平均比较次数为 n - p(n-1)/2。 p趋于0，平均次数趋于n；p趋于1时，平均次数趋于 （n+1）/2。（求极限）
算法分析与设计PPT03-递归与分治 - 7 选择问题
13946
4
算法3.9 采用分治策略 找出第K小元素的算法
i=1
do…while语句：
j=3
当条件为true时继续循
31496
环的处理过程
≥
i=2 j=1 j=1 left=0 3
输入样例
52 39416
输出样例 3
left
right
39416
pivot i
j
left
right
39416
5
pivot i j
再用同样的方法，继续解决这些子问题，直到每个子集只有一个 数据，就完成了全部数据的排序工作。
3
3.2.6 选择问题
利用快速排序算法的思想，来解决选择问题。
记一趟快速排序后，分解出左子集中元素个数为 nleft,则选 择问题可能是以下几种情况之一：
① nleft ＝k﹣1，则分界数据就是选择问题的答案。 ② nleft ＞k﹣1，则选择问题的答案继续在左子集中找，
问题规模变小了。 ③ nleft ＜k﹣1，则选择问题的答案继续在右子集中找，
问题变为选择第k-nleft-1 小的数，问题的规模变小了。
输入样例
52 39416
输出样例 3
此算法在最坏情况时间复杂度为 O(n2) ，
此时nleft总是为0，左子集为空，即第k
小元素总是位于right子集中。 平均时间复杂度为 O(n )。
3.2.6 选择问题
对于给定的n个元素的数组a[0：n—1]，要求从中找出第k 小的元素。
输入
输入有多组测试例。
对每一个测试例有2行，第一行是整数n和k（1≤k＜n≤1000），第 二行是n个整数。
输出
第k小的元素。
《算法设计与分析》递归算法典型例题
算法递归典型例题实验一：递归策略运用练习三、实验项目1．运用递归策略设计算法实现下述题目的求解过程。
题目列表如下：（1）运动会开了N天，一共发出金牌M枚。
第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。
到了第N天刚好还有金牌N枚，到此金牌全部发完。
编程求N和M。
（2）国王分财产。
某国王临终前给儿子们分财产。
他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。
每个儿子都窃窃自喜。
以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。
请用程序回答，老国王共有几个儿子？财产共分成了多少份？源程序：（3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。
问这鱼缸里原有多少条金鱼？（4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？（5）猴子吃桃。
有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？（6）小华读书。
第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？（7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。
《算法设计与分析》递归算法典型例题
算法递归典型例题实验一：递归策略运用练习三、实验项目1．运用递归策略设计算法实现下述题目的求解过程。
题目列表如下：（1）运动会开了N天，一共发出金牌M枚。
第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。
到了第N天刚好还有金牌N枚，到此金牌全部发完。
编程求N和M。
（2）国王分财产。
某国王临终前给儿子们分财产。
他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i个儿子i份，再加上剩余财产的1/10。
每个儿子都窃窃自喜。
以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。
请用程序回答，老国王共有几个儿子？财产共分成了多少份？源程序：（3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。
问这鱼缸里原有多少条金鱼？（4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？（5）猴子吃桃。
有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？（6）小华读书。
第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？（7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。
【分析】算法分析与设计作业参考答案
【关键字】分析《算法分析与设计》作业参考答案作业一一、名词解释：1.递归算法：直接或间接地调用自身的算法称为递归算法。
2.程序：程序是算法用某种程序设计语言的具体实现。
2、简答题：1.算法需要满足哪些性质？简述之。
算法是若干指令的有穷序列，满足性质：1）输入：有零个或多个外部量作为算法的输入。
2）输出：算法产生至少一个量作为输出。
3）确定性：组成算法的每条指令清晰、无歧义。
4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。
2.简要分析分治法能解决的问题具有的特征。
分析分治法能解决的问题主要具有如下特征：1）该问题的规模缩小到一定的程度就可以容易地解决；2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3）利用该问题分解出的子问题的解可以合并为该问题的解；4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。
将递归算法转化为非递归算法的方法主要有：1）采用一个用户定义的栈来模拟系统的递归调用工作栈。
该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。
2）用递推来实现递归函数。
3）通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善，但其适用范围有限。
三、算法编写及算法应用分析题：1.冒泡排序算法的基本运算如下：for i ←1 to n-1 dofor j ←1 to n-i doif a[j]<a[j+1] then交换a[j]、a[j+1]；分析该算法的时间复杂性。
解答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n的关系。
1）设比较一次花时间1；2）内循环次数为：n-i次,（i=1,…n），花时间为：3）外循环次数为：n-1，花时间为：2.设计一个分治算法计算一棵二叉树的高度。
递归算法的例子
递归算法的例子
1. 计算阶乘不就是个很好的例子嘛！比如计算 5 的阶乘，5! 不就是
5×4×3×2×1 嘛，这就是通过不断用较小的数的阶乘来计算呀，这多有意思啊！
2. 斐波那契数列呀！就像兔子繁殖一样神奇，前两个数相加得到下一个数，是不是很特别？这就是典型的递归算法呀！
3. 走迷宫的时候，你可以用递归算法来试着找路呀！哎呀，要是不这样试试，怎么能找到出口呢？
4. 汉诺塔问题啊，把那些盘子移来移去，不就是递归在发挥作用嘛，神奇吧！
5. 二叉树的遍历，就像是在森林里探索一样，一层一层地深入，这不是递归算法在帮忙嘛！
6. 画分形图形的时候，你看那美丽又复杂的图案，都是递归算法创造出来的呀，哇塞！
7. 分解一个大问题成小问题，再解决小问题，这不就是递归嘛，就像拆礼物一样，一层一层去发现惊喜！
8. 你想想，电脑下棋的时候，不也是用递归算法来分析各种走法吗，真的超厉害的！
总之，递归算法在好多地方都大显身手呢，它让很多复杂的事情变得简单又有趣，能创造出很多神奇的效果呀！。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
算法递归典型例题实验一：递归策略运用练习三、实验项目1运用递归策略设计算法实现下述题目的求解过程。
题目列表如下：(1)运动会开了N天，一共发岀金牌M枚。
第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。
到了第N天刚好还有金牌N枚，到此金牌全部发完。
编程求(2)国王分财产。
某国王临终前给儿子们分财产。
他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10;给第二个儿子两份，再加上剩余财产的1/10 ;……；给第i个儿子i份，再加上剩余财产的1/10。
每个儿子都窃窃自喜。
以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。
请用程序回答，老国王共有几个儿子？财产共分成了多少份？源程序：(3)岀售金鱼问题：第一次卖岀全部金鱼的一半加二分之一条金鱼；第二次卖岀乘余金鱼的三分之一加三分之一条金鱼；第三次卖岀剩余金鱼的四分之一加四分之一条金鱼；第四次卖岀剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在岀售金鱼时不能把金鱼切开或者有任何破损的。
问这鱼缸里原有多少条金鱼？(4)某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？(5)猴子吃桃。
有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只(即第二天吃剩下的一半加一只，以此类推) ，第九天正好吃完，问猴子们摘来了多少桃子？(6)小华读书。
第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？(7)日本著名数学游戏专家中村义作教授提岀这样一个问题：父亲将2520个桔子分给六个儿子。
分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7 给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。
结果大家手中的桔子正好一样多。
问六兄弟原来手中各有多少桔子？四、实验过程(一) 题目一：……1.题目分析由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一天的金牌剩余数，且每天的金牌数应为6的倍数。
2.算法构造设运动会举行了N天，lf(i==N)Gold[i]=N;Else gold[i]=gold[i+1]*7/6+i;using n ames pace std; void mai nO {int i=0,cou nt=O; int gold[100]; dogold[cou nt]=cou nt; for (i=cou nt-1; i>=1; i--) {if (gold[i+1]%6!=0 )break; //跳岀for 循环 elsegold[i]=gold[i+1]*7/6+i;//计算第i 天剩余的金牌数题目二:题目分析由已知可得，最后一个儿子得到的遗产份数即为王子数目，由此可得到每个儿子得到的 遗产份数，在对遗产数目进行合理性判断可得到符合要求的结果。
算法构造设皇帝有count 个王子，prop erty[cou nt]=cou nt; for (i=cou nt-1; i>=1; i--) {if (prop erty[i+1]%9!=0 )break;〃数目不符跳岀for 循环else3.算法实现#in elude <iostream>//预编译命令{cou nt=cou nt+6;//运动会天数加六//主函数 //cou nt 表示运动会举办的天数//定义储存数组4.}} while( i>=1 );//cout <<"运动会开了 "<<count<<"天"<< endl; cout<<"总共发了 "<<gold[1]<<"枚金牌"<<endl; }运行结果i>=1继续做do 循环//返回天数 //返回金牌数1.2.}3.算法实现P ro perty[i]=prop erty[i+1]*10/9+i;〃计算到第i 个王子时剩余份数#in elude <iostream> //预编译命令using n ames pace std; void mai nO {//主函数int i=0,cou nt=0; int prop erty[100]; do //count 表示国王的儿子数〃定义储存数组,表示分配到每个王子时剩余份数 {cou nt=cou nt+9;prop erty[cou nt]=cou nt; for (i=cou nt-1; i>=1; i--) {//王子数目为 9的倍数if (prop erty[i+1]%9!=0 )break;//数目不符跳岀elsefor 循环} 4.}} while( i>=1 );// 当 i>=1cout <<"皇帝有"<<count<<"个儿子"<< endl; cout<<"遗产被分成"<<property[1]<<"份"<<endl; 继续做do 循环//返回王子数//返回遗产份数运行结果rs\ID E0_\ De s klo 箭建交件夹\ Deb uq\C pp1.题目分析由最后一天的金鱼数目，可递推得到每天的金鱼数目，第一天的数目即为金鱼总数。
2.算法构造 fish[5]=11;for (i=4; i>=1; i--) fish[i]=(fish[i+1]*(i+1)+1)/i; 3.算法实现 //计算到第i 天剩余金鱼条数#include <iostream> // 预编译命令using n ames pace std; void mai nO //主函数int i=0;P ro perty[i]=prop erty[i+1]T0/9+i;〃计算到第i 个王子时剩余份数int fish [ 6];fish[5]=11;for (i=4; i>=1; i--)fish[i]=(fish[i+1]*(i+1)+1)/i; //计算到第i天剩余金鱼条数cout<<"浴缸里原有金鱼"<<fish[1]<<"条"<<endl; 〃返总金鱼数using n ames pace std; voidint i=0;num[9];num[8]=6;for(i=7; i>=2; i--)num[i]=2*(num[i+1]-8+i); 〃计算到第i站车上的人数cout<<"发车时车上有"<<num[2]<<"位乘客"<<endl; //返总发站人数，即为到第二站时车上人数}4.运行结果Press anv key to continue(五)题目五：•…1.题目分析〃定义储存数组各天剩余金鱼数}4. 运行结果浴缸里原有金鱼59条.Press any key to continite1.2.(四)题目四：……题目分析有到终点站时车上的乘客数可求得到任意一站的乘客人数, 即为发车时车上的乘客数。
算法构造到第二站时车上的乘客数目num[8]=6; for(i=7; i>=2; i--)n um[i]=2*( num[i+1]-8+i);//到终点站车上还有六人〃计算到第i站车上的人数3.算法实现#in elude <iostream> //预编译命令//主函数mai nO//定义储存数组//到终点站车上还有六人int可假设有第十天， 则第十天剩余的桃子数目为 0 ,由此递推可得每一天剩余的桃子数目。
第一天的桃子数目即为猴子摘桃子的总数。
2. 算法构造n um[10]=0; for(i=9; i>=1; i--) 3.算法实现■iJ J 'C:\U5er^\DELL\De5ktop\^aS ：1W^Debug\Cpp5,exe(六)题目六： .....1.题目分析由第六天剩余的页数可递推得到每天的剩余页数，第一天的页数即为全书的页数2.算法构造num[6]=3; for(i=5; i>=1; i--)n um[i]=2* (n um[i+1]+2);3.算法实现//到第 n 天时剩余的页数//计算到第i 天剩余的页数#in clude <iostream>//预编译命令using n ames pace std; void mai nO { int i=0;//主函数int n um[7]; num[6]=3; for(i=5; i>=1; i--)n um[i]=2* (n um[i+1]+2);//定义储存数组 //到第n 天时剩余的页数//计算到第i 天剩余的页数//第n 天吃前的桃子数num[i]=2* (n um[i+1]+1);〃计算到第i 天剩余的桃子数算法实现#in elude <iostream> //预编译命令using n ames pace std; voidmai nO//主函数int i=0;n um[11];n um[10]=0;for(i=9; i>=1; i--) num[i]=2*(num[i+1]+1);//计算到第i 天剩余的桃子数cout<<"猴子共摘来了 "<<num[1]<<"个桃子"<<endl;//输岀总的桃子数，即第一天吃前的数目int〃定义储存数组//第n 天吃前的桃子数}4.运行结果cout<<"全书共有"<<num[1]<<"页"<<endl; } //输岀总页数，即第一天吃前的数目4.运行结果se pp5. exe(七)1.2. 题目七：……题目分析由已知可得，第一个儿子得到的橘子数目为平均数的一半，由此可得到第一个儿子原先的橘子数目，而第i个儿子原先的橘子数目可由递推公式得到；算法构造if(i==0){a[i]=(ave-ave/2)*(8-i)/(8-i-1);left=a[i]-ave/2;//第一个儿子的数目}else{a[i]=ave*(8-i)/(8-i-1)-left;left=ave/(8-i-1);} //由left求第i+1个儿子的橘子数目//第i+1个儿子得到的橘子数目3.算法实现#in clude<iostream> using n ames pace std;void mai n(){int a[6];int left=O;int ave=420;for(i nt i=0;i<6;i++) { //存放六个儿子原先手中的橘子数目〃存放下一个儿子得到的橘子数目if(i==0){a[i]=(ave-ave/2)*(8-i)/(8-i-1); //第一个儿子的数目left=a[i]-ave/2;}elsea[i]=ave*(8-i)/(8-i-1)-left; left=ave/(8-i-1);}}for(i=0;i<6;i++)coutvv"第"<<i+1<<"个儿子原先手中的的橘子数为"vva[i]vvendl;子原先手中的橘子数目}4.运行结果IE *C ：\Users\DELL\Desktop\^S^fr5?\ Debug\1234.exe//由left 求第i+1个儿子的橘子数目//第i+1个儿子得到的橘子数目//输岀每个儿。