当前位置: 代码迷 >> 综合 >> JAVA算法:猴子吃桃子(JAVA版本算法)
  详细解决方案

JAVA算法:猴子吃桃子(JAVA版本算法)

热度:3   发布时间:2024-01-15 19:21:44.0

JAVA算法:猴子吃桃子(JAVA版本算法)

问题描述

猴子吃桃子 有一只猴子第一天摘了很多桃,觉得很高兴就立刻吃了桃总数的一半,然后觉得没吃饱又吃了3个。猴子感觉这样吃桃会立刻没有,于是就定下一个规矩: 

  • 每次在奇数天吃剩余桃总数的一半再多加3个
  • 每次在偶数天吃剩余桃的总数的一半再多吃一个。

请输入一个天数,使得该天数的剩余桃数正好为1,请输出猴子第一天共摘了多少个桃?


问题分析

我们采用“倒推法”,来寻找规律:

第1天:猴子摘了N个桃子;

第2天:剩余桃子数量为1,倒推第1天的情况。N/2 - 3 = 1 ,则 N = 8;

第3天:剩余桃子数量为1,倒推第2天的情况。N_2/2 - 1 = 1,则 N_2 = 4; 那么第1天的情况:N_1/2-3 = 4;则 N_1 = 14;

反过来想:

设输入的天数为n; 首先,找到问题入口: 
第1天时, 求剩余桃数:F(1) ; 其次,找到问题的递归方程,
在本题中,递归方程有两个:
若n天为奇数天:有F(n) = (F(n+1)+3)*2 
若n天为偶数天:有F(n) = (F(n+1)+1)*2 
其中,奇数天与偶数天相互递归。
最后,问题结束:当程序