用迭代和递归解决——猴子吃桃子问题

古城微笑少年丶 2022-12-26 13:28 136阅读 0赞

### 猴子吃桃子 ###

*  题目描述
 *   *   *  猴子吃桃子问题：
 *  迭代方法
 *   *   *  分析题目：
 *  递归方法
 *   *   *  分析题目
         *  注意：

# 题目描述 #

### 猴子吃桃子问题： ###

> 一天猴子摘了若干桃子，每天吃现有桃子数的一半多一个，第7天早上只剩下1个桃子，问猴子一共摘了多少个桃子？

# 迭代方法 #

### 分析题目： ###

可以使用后一天的桃子数推出前一天的桃子数。  
设第n天的桃子为xn，就是前一天的桃子的二分之一减去一。  
即：xn-1=（xn\+1）X 2

所以：

> 第7天：1个  
> 第6天： 4个  
> 第5天： 10个  
> …  
> 第一天： 190

代码实现:

//迭代
    #include <stdio.h>
    
    int main()
    { 
    	int sum = 1;//最后一天剩1个
    	for (int i = 1; i < 7; i++)//往前算6天
    	{ 
    		sum = (sum + 1) * 2;//向前迭代，每次加一乘以2
    	}
    	printf("%d\n", sum);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]

# 递归方法 #

### 分析题目 ###

根据题意，第n天的桃子数=（第n+1天的桃子数+1）X 2，而第7天的桃子数为1，这就是终止条件。

> **当n=1时 ,f ( n ) = 1;**  
> **当 n < 7 时, f ( n ）= ( f ( n + 1 ) + 1 ) X 2**

代码实现：

#include <stdio.h>
    int func(int day)
    { 
    	int a = 1;
    	if (day == 7)//当第7天时候，为1
    	{ 
    		a = 1;
    	}
    	else
    	{ 
    		a = ((func(day + 1) +1 )*2);//递归调用
    	}
    	return a;
    }
    
    int main()
    { 
    	int day = 1;
    	int sum = 0;
    	sum = func(day);
    	printf("%d\n", sum);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]

### 注意： ###

**使用递归时候，一定要注意判出条件，不然会一直处在递归之中，死循环，最后造成栈溢出**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221120/4d46c574f5b14a10aaf0fd49dddd001e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/3b7d219e40bf443a8c59526244d7c1e6.png