猴子吃桃

2016-01-11

猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第 10 天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。

可以使用逆向推理来解决，假设第 10 天早上的桃子数为 x，然后逆向计算前一天、前两天，一直到第一天的桃子数。假设 An 表示第 n 天剩下的桃子数，那么前一天的桃子数量与后一天的桃子数量关系为：An-1 = (An + 1) * 2。

  • 递归
1
2
3
4
5
6
7
8
9
10
11
function calculatePeaches(day, remaining) {
  // 如果是第一天，则直接返回桃子的数量
  if (day === 1) {
    return remaining
  } else {
    // 每天早上吃掉一半零一个，递归计算前一天剩下的桃子数量
    let yesterdayPeaches = (remaining + 1) * 2
    // 递归调用计算前一天的情况
    return calculatePeaches(day - 1, yesterdayPeaches)
  }
}
1
2
3
4
5
6
7
8
9
10
function calculatePeaches(day) {
  if (day === 1) {
    return 1
  } else {
    // (当日数量 + 1) * 2 即为前一日数量
    return (calculatePeaches(day - 1) + 1) * 2
  }
}

calculatePeaches(10)
  • 循环
1
2
3
4
5
6
7
8
9
function calculatePeaches(day) {
  let peaches = 1
  for (let i = day - 1; i >= 1; i--) {
    peaches = (peaches + 1) * 2
  }
  return peaches
}

calculatePeaches(10)