《算法设计与分析》 趣味题.doc

学 号 10770114算法设计与分析实验报告一学生姓名王哲专业、班级10软件1班指导教师唐国峰成绩电子与信息工程系2012 年 10 月 10 日实验一：递归策略运用练习一、实验目的本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。二、实验步骤与要求1实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2学生独自完成实验指定内容；3实验结束后，用统一的实验报告模板编写实验报告。4提交说明： （1）电子版提交说明：a 需要提交Winrar压缩包，文件名为“算法设计与分析实验一_学号_姓名”，如“算法设计与分析实验一_09290101_张三”。 b 压缩包内为一个“算法设计与分析实验一_学号_姓名”命名的顶层文件夹，其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明：a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号字。 c 行间距：单倍行距。（3）提交截止时间：2012年10月31日16:00。三、 实验项目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给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？四、实验过程(一) 题目一：运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。1. 题目分析分析此题，可以按照从第一天开始递归，每次和前一天的金牌剩余数的关系为：（前一天金牌剩余数-当天为第几天）*6/7=当天金牌剩余数，递归终点为:当某一天的前一天的金牌剩余数等于当天的天数，即为终止点。2. 算法构造通过双重循环来寻找天数和金牌数，构造一个存放每天剩余金牌数的容器，我使用的是java语言，选择了LinkedList,在构造递归关系时候，主要要判断 该天金牌数-天数之差是否能是7的倍数，如果不能，则设置为0，在后面的条件判断时候予以舍弃情况。3. 算法实现import java.util.LinkedList;public class Work1 /* * author Wz */* * 题目要求：运动会开了N天，一共发出金牌M枚。 第一天发金牌1枚加剩下的七分之一枚， 第二天发金牌2枚加剩下的七分之一枚， * 第3天发金牌3枚加剩下的七分之一枚， 以后每天都照此办理。 到了第N天刚好还有金牌N枚， 到此金牌全部发完。编程求N和M。 */public static void main(String args) LinkedList lt = new LinkedList();for (int n = 3; n 10; n+) / 逐次循环查找天数for (int m = 1; m 50; m+) / 逐次递增寻找金牌枚数lt.add(0, m);/ 一共m枚/ 第n天剩下n枚for (int i = 1; i = n; i+) lt.add(i, giveout(lt.get(i - 1), i);if (lt.get(n - 1) - n = 0) System.out.println(金牌数: + lt.get(0) + ,天数: + n);public static int giveout(int count, int nowday) / 分发金牌if (count - nowday) % 7 != 0)return 0;elsereturn (count - nowday) * 6 / 7;4. 运行结果 5. 经验归纳算法设计时，注意逻辑性的严谨，考虑情况要全面，条件判断位置要适宜。 (二) 题目二：国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 1. 题目分析通过双重循环寻找儿子个数和份数，然后通过构造递归关系从而寻找到结果。2. 算法构造通过一个linkedlist保存每次分后的剩余财产，在递归最后如果最后剩余财产为0，且最后一个儿子正好得到n份，则该循环的结果为提目要求的结果3. 算法实现import java.util.LinkedList;public class Work2 /* * author Wz */* * 国王分财产。某国王临终前给儿子们分财产。 他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10； * 给第二个儿子两份，再加上剩余财产的1/10; 给第i个儿子i份，再加上剩余财产的1/10。 * 每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子 ？财产共分成了多少份？ */public static void main(String args) LinkedList lt = new LinkedList();for (int n = 4; n 100; n+) / 循环设置份数for (int m = 2; m 50; m+) / 设置儿子个数lt.add(0, n);/ 一共为1for (int i = 1; i = m; i+) lt.add(i, giveout(i, lt.get(i - 1), n);/ 分给第i个儿子后剩下的财产为if (lt.get(m) = 0 & lt.get(m - 1) = m) System.out.println(一共分了 + n + 份,国王有: + m + 个儿子); else lt.clear();public static int giveout(int index, int left, int n) / 分财产if (left - index) % 10 != 0)return 0;elsereturn 9 * (left - index) / 10;4. 运行结果5. 经验归纳(三) 题目三： 出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ 1. 题目分析通过循环设置条数，然后通过构造递归关系从而寻找到结果。 2. 算法构造通过递归，从最后11条金鱼开始逐次向前一天寻找。3. 算法实现import java.util.LinkedList;public class Work3 /* * author Wz */* * 出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼； * 第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ */public static void main(String args) LinkedList lt = new LinkedList();lt.add(0, 11);/ 剩余11条/ 第n天原有x条int temp = 4;for (int i = 1; i = 4; i+) lt.add(preday(temp, lt.get(i - 1);temp-;System.out.println(鱼缸里原来有：+lt.get(4)+条金鱼);public static int preday(int index, int left) / 计算前一天的条数return (left * (index + 1) + 1) / index;4. 运行结果5. 经验归纳 计算递归关系时，要切记计算正确。(四) 题目四： 某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ 1. 题目分析一共八站，每一站都是下车原先的一半的乘客，第二站再上来6位，从第三站开始都是再上来比前一站乘客少一个，一次递减，到第八站剩下6人。2. 算法构造运用循环，递归，从最后一站开始递归，直到第一站。3. 算法实现import java.util.LinkedList;public class Work4 /* * author Wz */* * 某路公共汽车，总共有八站， 从一号站发轩时车上已有n位乘客， 到了第二站先下一半乘客，再上来了六位乘客； * 到了第三站也先下一半乘客，再上来了五位乘客 ，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个， * 到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ */public static void main(String args) LinkedList lt = new LinkedList();lt.add(6);/ 最后一站还有6人for (int i = 1; i 7; i+) / 逐次递归记录每站人数lt.add(getpre(i,lt.get(i-1);System.out.println(发车时车上的乘客有+lt.get(6)+名。);public static int getpre(int side, int passage) return (passage -side) * 2;4. 运行结果5. 经验归纳计算递归关系时，要切记计算正确。(五) 题目五： 猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ 1. 题目分析桃子前一天和当天存在递归关系。2. 算法构造通过list保存递归结果，递归终点为剩余0个桃子，从而得到桃子原先个数3. 算法实现import java.util.LinkedList;public class Work5 /* * author Wz */* * 猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ */public static void main(String args) LinkedList lt = new LinkedList();for (int i = 0; i 2000; i+) / 循环设置桃子个数lt.add(0, i);for (int j = 1; j = 9; j+) / 第九天吃完lt.add(j, eat(lt.get(j - 1);if (lt.get(9) = 0)/ 判断是否正好吃完System.out.println(猴子们摘来了+lt.get(0)+只桃子);elselt.clear();public static int eat(int left) if (left % 2 != 0)return -1;elsereturn left / 2 - 1;4. 运行结果5. 经验归纳计算递归关系时，要切记计算正确。(六) 题目六： 小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此，第六天读完了最后的三页，问全书有多少钱页？ 1. 题目分析读书页数前一天和当天存在递归关系。 2. 算法构造通过正向 循环设置全书页数，递归出每天读的页数。3. 算法实现import java.util.LinkedList;public class Work6 /* * author Wz */* * 小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此，第六天读完了最后的三页，问全书有多少钱页？ */public static void main(String args) LinkedList lt = new LinkedList();for (int i = 0; i 2000; i+) / 循环设置页数lt.add(0, i);for (int j = 1; j = 5; j+) / 循环每天剩下的页数lt.add(j, eat(lt.get(j - 1);if (lt.get(5) = 3)/ 判断是否剩下3也System.out.println(全书有+lt.get(0)+页);elselt.clear();public static int eat(int left) if (left % 2 != 0)return -1;elsereturn left / 2 - 2;4. 运行结果5. 经验归纳计算递归关系时，要切记计算正确。(七) 题目七： 日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？1. 题目分析题目通过6个兄弟依次轮流从上一个兄弟得到橘子再给予下一个兄弟，进行2次操作，把橘子最后平均分成了6分。2. 算法构造可以通过每次循环 如果得到再给予之后的橘子数 等于460，则该原橘子数就是所需要查找的数目。3. 算法实现package com.hourglass.suanfa;import java.util.LinkedList;public class Work7 /* * author Wz */* * /*日本著名数学游戏专家中村义作教授提出这样一个问题： 父亲将2520个桔子分给六个儿子。分完后父亲说： “老大将分给你的桔子的1/8给老二； * 老二拿到后连同原先的桔子分1/7给老三； 老三拿到后连同原先的桔子分1/6给老四； 老四拿到后连同原先的桔子分1/5给老五； * 老五拿到后连同原先的桔子分1/4给老六； 老六拿到后连同原先的桔子分1/3给老大”。 结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ */public static void main(String args) LinkedList lt = new LinkedList();int arvOrange = 2520 / 6;/ 六个儿子平均分后每人橘子数loop: for (int i = 8; i = 2520; i += 8) / 1int a = i;a = a * 7 / 8;for (int j = 1; j 2520; j+) / 2if (j + a / 7) % 7 != 0) continue; else int b = (j + a / 7);/ 老二的橘子if (b * 6 / 7 = arvO