赶鸭子问题

今天药忘吃喽~ 2022-01-23 02:29 472阅读 0赞

题目：赶鸭子问题

一.题目分析

用递归方法设计下列各题，并给出每道题目的递归出口（递归结束的条件）和递归表达式。同时考虑题目可否设计为非递归方法，如果可以，设计出非递归的算法。

一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？

分析思路：从后向前推测，最后剩余鸭子两只，每次相对于上一次来说，剩余x-（x/2+1）只鸭子。

二.算法设计

采用递归函数f(n)来完成整个过程，因为每次的过程步骤都相同，因此用同一个函数反复调用即可，最后给出一个结束条件，就是村庄数超过8时，递归调用结束。

三.源代码

package duck_qustion;
    
    import java.util.Scanner;
    
    public class Duck{//用循环法
    	/*一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子
    	 * 的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他
    	 * 出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
    	 */
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		count();
    		
    	}
    
    	public static void count() {
    		int sub_duck = 2;
    		int sum = 0 ;
    		int duck = 2;
    		for(int s = 0;s<7;s++) {
    			duck = (duck + 1) * 2;
    		}
    		sum  = duck ;
    		System.out.println("鸭子的总数为" + sum);
    
    		System.out.println("请输入需要查询的村庄序号");
    		
    		 @SuppressWarnings("resource")
    		Scanner input = new Scanner(System.in);
    		 int n = input.nextInt();
    
    		for (int i = 0; i < (7 - n); i++) {
    			sub_duck = (sub_duck + 1) * 2;
    		}
    		System.out.println("经过第 " + n + "个村庄时，剩余鸭子的个数为" + sub_duck);
    	}
    }

四.运行，调试截图

运行截图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70][]

图1

调试截图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 1][]

图2

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 2][]

图3

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 3][]

图4

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 4][]

图5

五.心得体会

使用递归调用时，优点在于代码量少，使得代码有更高的可读性，开起来不繁琐，但是缺点在于效率没有非递归的效率高，并且代码的可读性不高，对于判断递归的出口不易判断。

使用非递归调用时，优点在于效率比递归的效率高，并且代码的可读性高，容易理解。缺点在于代码量多，使得代码没有良好的可读性，看起来过于冗杂。

此次的程序使我对于递归和非递归的理解更深刻，在实际题目中的运用更熟练。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70]: /images/20220123/952ca70eef0d43ff844b8f01ced468ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 1]: /images/20220123/cdd598421c414b66b964452d68f3ac10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 2]: /images/20220123/457b3c8b441a4632b33d7e25e051ceda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 3]: /images/20220123/9c5724bcdaf74d37a37f071aadb4a72e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 4]: /images/20220123/a1658657110b4daeb46e7939e89f8668.png