递归程序设计（卖鸭子角谷定理）

本文主要是介绍递归程序设计（卖鸭子角谷定理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一．实验目的
掌握递归程序设计的方法。明确递归的概念，通过对问题的分析，找出递归关系以及递归出口以对问题进行递归结构设计；掌握递归程序转换为非递归程序的方法。

二、实验内容
用递归方法设计下列各题，并给出每道题目的递归出口（递归结束的条件）和递归表达式。同时考虑题目可否设计为非递归方法，如果可以，设计出非递归的算法。
1.一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
2.角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。如：输入22，输出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 STEP=16

三、第一题
1.题目分析
设经过第n个村子时有num(n)只鸭子，卖去num(n)/2+1只鸭子，剩下num(n+1)只鸭子，则有num(n)=num(n)/2+1+num(n+1),即num(n)=2*(num(n+1)+1)。经过了七个村子后还剩两只鸭子，即num(8)=2。因此出发时共赶num(1)只鸭子，经过第n个村子时卖出num(n)/2+1只鸭子。
2.算法构造
function(n){
count(n)=2*(count(n+1)+1) ，1<=n<8;
count(n)=2 ， n=8;
}

3. 程序实现

public class Duck {public static void main(String[] args) {int result = SellDuck(0);//出发时鸭子总数int num = 0; //经过村庄卖掉的鸭子数量System.out.println("出发时共赶"+ result+"只鸭子");for(int i=1;i<=7;i++) {int ducks = (result / 2) + 1;num += ducks;result = 510-num;if(i!=7) {System.out.println("经过第" + i + "个村庄卖了" + ducks + "只鸭子,剩余" + (510-num) + "只鸭子");}else{System.out.println("经过第" + i + "个村庄卖了" + ducks + "只鸭子,剩余" + (510-num) + "只鸭子");}}}public static int SellDuck(int amount){ //amount为经过的村庄数if(amount==7){return 2;}else{return 2*(SellDuck(amount+1)+1);}}
}

4.运行结果
在这里插入图片描述

四、第二题
1.题目分析
设num(n)表示关于自然数n的一个函数，当n=1时，num(1)=1。当n>1且n为偶数时，num(n)=num(n/2)；当 n>1且n为奇数时，num(n)=num(3n+1)。得到自然数1的运算次数为每次运算次数之和。
2. 算法构造
num(n)=1 ,n=1
num(n)=num(n/2) ，n>1且n为偶数
num(n)=num(3n+1) ，n>1且n为奇数
3.程序实现

public class JiaoGu {static int i=0;public static void main(String[] args) {System.out.println("Please input a number : ");Scanner in = new Scanner(System.in);int n = in.nextInt();int i = num(n);System.out.print("STEP = "+i);}public static int num(int n) {if (n == 1) {System.out.println(n);} else if (n % 2 == 0) {System.out.println(n);num(n / 2);i++;} else {System.out.println(n);num(n * 3 + 1);i++;}return i;}
}

4.运行结果

在这里插入图片描述