猴子吃桃问题

来自计算思维百科
跳转至: 导航搜索
猴子吃桃问题.png

猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个。第二天又将剩下的桃子吃掉一半,又多吃了一个。以后每天都吃前一天剩下的一半零一个。到第10天在想吃的时候就剩一个桃子了,求第一天共摘下来多少个桃子?

涉及的计算思维

解决这个问题可以计算思维中的递归思想。

解决方案

假设f(n)是第n天的桃子数量,可以发现每一天的桃子的数量都是用后一天桃子的数量加上1之后再乘以2。于是可以得出递推公式f(n-1)=(f(n)+1)*2 ,然后进行递推计算,当n=1时停止,就是最初的桃子数量。 即是从第十天只剩下1个来往前推,前一天都是后一天的数量加1之后再乘以2。具体递推过程如下:已知第十条桃子是1个,所以f(10)=1,则

  1. 第九天有桃子f(9)=(f(10)+1)*2=(1+1)×2=4 个
  2. 第八天:f(8)=(f(9)+1)*2=(4+1)×2=10
  3. 第七天:f(7)=(f(8)+1)*2=(10+1)×2=22
  4. 第六天:f(6)=(f(7)+1)*2=(22+1)×2=46
  5. 第五天:f(5)=(f(6)+1)*2=(46+1)×2=94
  6. 第四天:f(4)=(f(5)+1)*2=(94+1)×2=190
  7. 第三天:f(3)=(f(4)+1)*2=(190+1)×2=382
  8. 第二天:f(2)=(f(3)+1)*2=(382+1)×2=766
  9. 第一天:f(1)=(f(2)+1)*2=(766+1)×2=1534