****** 《算法设计与分析》***
实验一：递归策略运用练习***
一、实验目的
本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。
二、 实验项目
1．运用递归策略设计算法实现下述题目的求解过程。
题目列表如下：
【必做题】
（1）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出剩余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？
（2）某路公共汽车，总共有八站，从一号站发车时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？
（3）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？
（4）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？
（5）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。
（6）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？
（7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？
（8）某种传染病第一天只有一个患者，前5天为潜伏期，不发作也不会传染人，第6天开始发作，从发作到治愈需要5天时间，期间每天传染3个人，求第N天共有多少患者。
【选做题】
（1）50个阶梯，你一次可以上一阶或两阶，走上去，共有多少种走法？
四、实验过程
【必做题】
（一）题目一：出售金鱼问题
- 题目分析
得知最后还剩11条金鱼，用递归法以此类推出第四次、第三次、第二次、第一次出售前金鱼的数量。
- 算法构造
递归函数：result=(Fish(i+1)+(Fish(i+1)+1)/i)。
- 算法实现
程序源代码（请写入必要的注释）。
package com.cn;
public class Fish {
public static float fish(float n){ //第几次卖鱼时共有多少条鱼
if(n==5) return (11); //如果是第五次卖鱼，则有11条鱼
else return ((n+1)/n)*(fish(n+1)+1/(n+1)); //前一次卖的鱼等于((n+1)/n)乘以后一次卖的鱼加上后一次分之一
}
public static void main(String[] args) {
float n;
n=fish(1); //第1次卖鱼时共有多少条鱼
System.out.println(“第一次共有”+n+“条鱼”);
}
}
-
运行结果
-
经验归纳
只要分析出递归式，就找到了本题的突破口。
（二）题目二：汽车乘客问题
-
题目分析
重点理解“到了终点站车上还有乘客六人”，此时的人数应该是第七站发车后的人数，根据终点站的人数运用递归法依次推出到达前几站的人数。
-
算法构造
递归函数：sum=2*(f(i+1)-7+i)。
-
算法实现
程序源代码（请写入必要的注释）。
package com.cn;
public class Bus {
public static float station(float n){ //第几站上车时车上有多少人
//第一站上车时人员不发生变动，所以将第二站作为始发点
if(n<7) return (2*(station(n+1)+n-7)); //如果传入值不是最后一站则向后递归寻找边界值
else return (6); }
public static void main(String[] args) {
float n;
n=station(1); //第1站公交车上有多少人
System.out.println(“第一站公交车上有”+n+“人”);
}
}
-
运行结果
-
经验归纳
先分析出递归公式，用代码的方式表示出来即可。
（三）题目三：猴子吃桃问题
-
题目分析
由每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完可以分析出递归函数。
-
算法构造
递归函数：result=2*(f(i+1)+1)。
-
算法实现
程序源代码（请写入必要的注释）。
package com.cn;
public class Monkey {
public static float eatPeach(float n){
if(n==9) return (2); //循环终止条件,第九天吃之前剩了两个桃子
else return (2*(eatPeach(n+1)+1));//如果不满足条件，当天吃之前剩的=（（后一天的）+1）*2
}
public static void main(String[] args) {
float n;
n=eatPeach(1); //算第几天猴子吃之前有多少个桃子eatPeach方法体中写天数
System.out.println(“猴子们摘来了”+n+“个桃子”);
}
}
-
运行结果
-
经验归纳
先分析问题，列出递推公式，找到突破口。
（四）问题四：小华读书问题
-
题目分析
由“第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页”用递归法推出书本页数。
-
算法构造
递归函数：result=2*(f(i+1)+2)。
-
算法实现
程序源代码（请写入必要的注释）。
package com.cn;
public class Reading {
public static float Read(float n){
if(n==6) return (3); //循环终止条件,第六天读之前有3页没读
else return (2*(Read(n+1)+2));//如果不满足条件，当天读之前剩的页数=（（后一天的）+2）*2
}
public static void main(String[] args) {
float n;
n=Read(1); //算第1天读之前有多少页没读等价于求全书有多少页
System.out.println(“整本书有”+n+“页”);
}
}
-
运行结果
-
经验归纳
首先要列出递推公式，写出代码即可。
（五）问题五：运动会发金牌问题
-
问题分析
根据问题很容易分析出递归函数，只有这一个递归函数并不能求出来运动会开了多少天，共有多少块金牌，所以还要有限制条件，分发的金牌都是整数，与金鱼出售问题类似。
-
算法构造
递归函数：result=((nSum(i+1,n)*7)/6+i);
限制条件：nSum(i,n)-i)%70&&(nSum(i,n)%60
-
算法实现
程序源代码（请写入必要的注释）。
package com.cn;
public class First {
public static int broken(int num, int today) {//num为前一天所剩的金牌数，today为当天天数
if ((num-today)%7!=0) //判断前一天所剩金牌数-当天天数能否被7整除，不可以返回0
return 0;
else //如果可以返回当天剩余金牌的数量
return (num-today) *6/7;
}
}
测试类：
package com.cn;
import java.util.LinkedList;
public class Test {
static First one=new First();
public static void main(String[] args) {
LinkedList<Integer> lt = new LinkedList<Integer>();
for(int n=3;n<10;n++) {// 根据题干可知，n>=3,将n的初值设为3可以降低递归算法的重复率
for(int m =1;m<100;m++) {//利用穷举法计算m的值
lt.add(0,m);// 第一天没发之前一共有m枚金牌
for(int i=1;i<=n;i++) {//调用第一题中的判断算法，依次计算每天发了多少枚
lt.add(i,one.broken(lt.get(i-1),i));//到达第n天依旧没有符合终止条件的情况跳出循环
}
if (lt.get(n-1)-n==0) {//第n天发了n枚金牌循环终止条件
System.out.println("金牌总数为:"+lt.get(0)+",运动会进行天数为:"+n);
}
}
}
}
}
-
运行结果
-
经验归纳
此类问题要比前面的问题复杂一些，但是还是要先找到递推公式，然后再进行编译。
（六）问题六：国王分财产问题
-
问题分析
由问题可知，国王分给每个儿子的财产都相同，即2*f(i,n)-f(i-1,n)-f(i+1,n)0；同时还要限制剩余的财产分去第i个人的i份之后保证是10的倍数，即f(i,n)-i)%100
-
算法构造
递归函数：sum=(f(i+1,n)*10)/9+i。
-
算法实现
程序源代码（请写入必要的注释）。
package com.cn;
public class Treasure {
public static void main(String[] args) {
int i=0;
int n=0;
int prince[]=new int[100]; //规定一个边界值，以免数值过大影响计算速度(本题已经确定份数在100份以内)
while(true){ //如果没有break则继续循环
n=n+9; //因为财产数必为9的倍数
prince[n]=n; //第n个王子得到n份
for(i=n-1;i>=1;i--) //从最后一个王子开始往前算每一位王子所拥有的财产能否被9整除
{ //不能则跳出循环，n再加9，可以的话再判断前一位
if(prince[i+1]%9!=0) {break;}
else prince[i]=prince[i+1]*10/9+i;
}
if(i==0) break; //当所有王子所拥有的财产都能被9整除，及经过若干次i--之后i变成了零
} //跳出外循环，完成循环终止条件，得出结果
System.out.println("国王一共有"+n+"个儿子");
System.out.println("一共有资产"+n*prince[1]+",总共分了"+prince[1]+"份");
}
}
-
运行结果
-
经验归纳
这类问题不仅要列出递归函数，同时还要考虑限制条件
（七）问题七：六兄弟分桔子问题
-
问题分析
最后每个人手中的桔子数量相同是这道题的关键，以此为突破口，找出递归函数
-
算法构造
递归函数：a[i][1]=(average-average/(Fenmu_min-1))*(Fenmu_max-i)/(Fenmu_max-1-i)。
-
算法实现
程序源代码（请写入必要的注释）。
package com.cn;
public class Orange {
static int MAX=8;//分母最大值
static int MIN=3;//分母最小值
//a[i][0]表示第i个孩子分出的桔子
//a[i][1]表示第i个孩子分到的桔子
public static int orange(int a[][],int i){
int ave=2520/6;
int p;
if(i==0){//边界条件
//第一个孩子得到的桔子总数等于平均数-最后一个孩子分给老大的差乘以8/7.
a[i][1]=(ave-ave/(MIN-1))(MAX-i)/(MAX-1-i);
//第一个孩子分给第二个孩子的橘子数量
a[i][0]=a[i][1]-(ave-ave/(MIN-1));
}
else{
a[i][1]=ave(MAX-i)/(MAX-i-1)-orange(a,i-1);//第i个孩子分到的
a[i][0]=a[i][1]+orange(a,i-1)-ave; //第i个孩子分出的
}
p=a[i][0];
return p;
}
public static void main(String[] args) {
int o[][]={{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}};
orange(o,5);//给数组里的六个元素赋值
for(int i=0;i<=5;i++)
{
System.out.println(“第”+(i+1)+“个儿子最初有”+o[i][1]+“个桔子”);
}
}
}
-
运行结果
-
经验归纳
这道题与国王分财产问题类似，推出递归函数，同时考虑限制条件。
（八）问题八：传染病问题
-
问题分析
前五天为潜伏期，只有一个病人，到了第六天开始传染其他人，到了第十天才能够治愈一个病人，同时还要考虑病人每天传染三个人。
-
算法构造
递归函数：sum=Day(n-5)*3+Day(n-1)。
-
算法实现
程序源代码（请写入必要的注释）。
package com.cn;
import java.util.Scanner;
public class Disease {
public static int diseaseDay(int n){
int sum=0;
if(n<=5){
return 1; //五天之内既不发作也不会传染，所以患病人数就是1
}
else{
sum=diseaseDay(n-5)*3+diseaseDay(n-1)-diseaseDay(n-5);//五天之后患病人数等于前一天被传染和发作的加上当天又传染的的减去当天被治愈好的。
}
return sum;
}
public static void main(String[] args) {
int n;
System.out.println(“请输入传染病发生后的天数（疾病五天之后才开始传染）”);
Scanner scanner=new Scanner(System.in);//控制台输入
String day=scanner.nextLine();
n=Integer.parseInt(day);
for(int i=1;i<=n;i++){
System.out.println(“第”+i+“天”+“得病人数为：”+diseaseDay(i)+“人”);
}
}
}
-
运行结果
-
经验归纳
这道题主要是在病人治愈的同时还会有传染病人的增加，还要考虑潜伏期，综合考虑
到这些问题，这道题就比较简单了。
【选做题】
（一）走阶梯问题
-
问题分析
由题意可知，一次可以上一阶或两阶阶梯，由此可以列出当有一阶，两阶，三阶，四阶，五阶…它们的走法，可以推导出递推公式。
-
算法构造
递归函数：stair n = stair(n-1)+stair(n-2)。
-
算法实现
程序源代码（请写入必要的注释）。
package com.cn;
import java.util.Scanner;
public class X3 {
public static int upStairs(int n){ //n阶台阶有多少种上法
if(n0) return 1; //边界条件，一阶或者0阶台阶时都只有一种上法
if(n1) return 1;
else return upStairs(n-1)+upStairs(n-2);//因为只能是一阶一阶上或者两阶两阶上，所以到达顶点的最后一步不是一阶就是两阶,倒数第二步也是这样
//将从倒数第一步到第一步，每一步的两种可能加在一起就是最后的答案
}
public static void main(String[] args) {
int n;
System.out.println(“请输入楼梯的阶数：”);
Scanner scan=new Scanner(System.in);
n=scan.nextInt(); //控制台输入
for(int i=1;i<=n;i++)
{
System.out.println(i+“阶台阶，一共有”+upStairs(i)+“种上法”);//将从1阶到输入的n阶的可能数量遍历输出
}
}
}
-
运行结果
-
经验归纳
此类问题重点是分析出递推公式，当能想到递推公式，这类问题就比较简单了。
五、实验总结
通过这些实验，我能够更好地理解递归函数在编程化语言下的使用，前四个实验类型一样，只需要分析出递归函数，问题就迎刃而解了，此类问题比较简单；第五个、第六个和第七个实验类型一样，在分析出递归函数的同时还要考虑问题的限制条件，此类问题主要是以限制条件为突破口，比前四个实验稍微复杂（第七个实验比较难）；第八个实验和选做实验一是同一类型的题，问题看似简单，但是需要细心思考，关键是写出递归函数，这样问题就容易多了，与前几个实验相比，此类问题反而更加简单了。
