package com.itheima;
public class GetPeach {
/**
* 猜一猜猴子摘了多少桃子呢?
猴子吃桃的问题:猴子第一天摘下来N个桃子,当天就吃了一半,但是还不过瘾,又多吃了一个,第二天早上又将
剩下的桃子吃了一半,又多吃了一个,以后每天早上都吃了前一天剩下的一半零一个,到第十天早上的时候就发现剩下
一个桃子了.求第一天一共摘下了多少桃子呢?
思路:
这是学C语言时候的一道经典例题,用数据结构的术语就是递归问题。
假如每天有x个桃子,猴子吃了一半加一个,就是吃了x/2+1个,那么剩余x-(x/2+1)=x/2-1个;
这样,第二天有x/2-1个桃子供当天使用。
查找到规律:今天的桃子个数+1再乘2等于昨天的桃子个数;用上面的表达式就是( x/2-1 +1 )*2=x。
如此,只要知道了最后一天的桃子个数,知道了最后一天是第几天,就可以逆推出第一天总共多少个桃子了
* @param args
* @param numOfDays 总天数
* @return 第一天总共摘的桃子数
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
GetPeach getPeach = new GetPeach();
int num = getPeach.getNumOfPeachFirstDay(10);
System.out.println(" 猴子第一天一共摘下了"+num+"个桃子");
}
public int getNumOfPeachFirstDay(int numOfDays) {
if (numOfDays < 1) {
throw new RuntimeException("NumOfDays must more than zero!");
}
if (numOfDays == 1) {
return 1;
}
//第numOfDays-1的桃子数
int num =getNumOfPeachFirstDay(numOfDays - 1);
return ( num+ 1) * 2;
}
}
|
|