《算法设计与分析》递归算法典型例题

算法递归典型例题 实验一 递归策略运用练习实验一 递归策略运用练习 三 三 实验项目实验项目 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 8 给老二 老二拿到后连同原先的桔子分 1 7 给老三 老三拿到后连同原先的桔子分 1 6 给老四 老四拿到后连同原先的桔子分 1 5 给老 五 老五拿到后连同原先的桔子分 1 4 给老六 老六拿到后连同原先的桔子分 1 3 给老大 结 果大家手中的桔子正好一样多 问六兄弟原来手中各有多少桔子 四 四 实验过程实验过程 一 题目一 1 题目分析 由已知可得 运动会最后一天剩余的金牌数 gold 等于运动会举行的天数由此可倒推每 一天的金牌剩余数 且每天的金牌数应为 6 的倍数 2 算法构造 设运动会举行了 N 天 If i N Gold i N Else gold i gold i 1 7 6 i 3 算法实现 include 预编译命令 using namespace std void main 主函数 int i 0 count 0 count 表示运动会举办的天数 int gold 100 定义储存数组 do count count 6 运动会天数加六 gold count count for i count 1 i 1 i if gold i 1 6 0 break 跳出 for 循环 else gold i gold i 1 7 6 i 计算第 i 天剩余的金牌数 while i 1 当 i 1 继续做 do 循环 cout 运动会开了 count 天 endl 返回天数 cout 总共发了 gold 1 枚金牌 1 i if property i 1 9 0 break 数目不符跳出 for 循环 else property i property i 1 10 9 i 计算到第 i 个王子时剩余份数 3 算法实现 include 预编译命令 using namespace std void main 主函数 int i 0 count 0 count 表示国王的儿子数 int property 100 定义储存数组 表示分配到每个王子时剩余份数 do count count 9 王子数目为 9 的倍数 property count count for i count 1 i 1 i if property i 1 9 0 break 数目不符跳出 for 循环 else property i property i 1 10 9 i 计算到第 i 个王子时剩余份数 while i 1 当 i 1 继续做 do 循环 cout 皇帝有 count 个儿子 endl 返回王子数 cout 遗产被分成 property 1 份 1 i fish i fish i 1 i 1 1 i 计算到第 i 天剩余金鱼条数 3 算法实现 include 预编译命令 using namespace std void main 主函数 int i 0 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 条 2 i num i 2 num i 1 8 i 计算到第 i 站车上的人数 3 算法实现 include 预编译命令 using namespace std void main 主函数 int i 0 int num 9 定义储存数组 num 8 6 到终点站车上还有六人 for i 7 i 2 i num i 2 num i 1 8 i 计算到第 i 站车上的人数 cout 发车时车上有 num 2 位乘客 1 i 3 算法实现 num i 2 num i 1 1 计算到第 i 天剩余的桃子数算法实现 include 预编译命令 using namespace std void main 主函数 int i 0 int num 11 定义储存数组 num 10 0 第 n 天吃前的桃子数 for i 9 i 1 i num i 2 num i 1 1 计算到第 i 天剩余的桃子数 cout 猴子共摘来了 num 1 个桃子 1 i num i 2 num i 1 2 计算到第 i 天剩余的页数 3 算法实现 include 预编译命令 using namespace std void main 主函数 int i 0 int num 7 定义储存数组 num 6 3 到第 n 天时剩余的页数 for i 5 i 1 i num i 2 num i 1 2 计算到第 i 天剩余的页数 cout 全书共有 num 1 页 endl 输出总页数 即第一天吃前的数目 4 运行结果 七 题目七 1 题目分析 由已知可得 第一个儿子得到的橘子数目为平均数的一半 由此可得到第一个儿子原 先的橘子数目 而第 i 个儿子原先的橘子数目可由递推公式得到 2 算法构造 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 求第 i 1 个儿子的橘子数目 left ave 8 i 1 第 i 1 个儿子得到的橘子数目 3 算法实现 include using namespace std void main int a 6 存放六个儿子原先手中的橘子数目 int left 0 存放下一个儿子得到的橘子数目 int ave 420 for int i 0 i 6 i if i 0 a i ave ave 2 8 i 8 i 1 第一个儿子的数目