C语言算法猴子吃桃问题

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

代码如下：

#include <stdio.h>
int main()
{
	int day,x1,x2;        /*定义 day,x1,x2 3个变量为基本整型 */
	day=9;
	x2=1;
	while(day > 0){
		x1 = (x2 + 1)*2;     /*第一天的桃子数是第二天桃子数加1后的2倍*/
		x2 = x1;             
		day--;               /*因为从后向前推所以天数递减*/
	}
	printf("The total is %d\n", x1);   /*输出桃子的总数*/
	return 0;
}

   运行结果：

   The total is 1534

评论

1 楼 kyzaqlx 2015-07-31  

设第n天剩下桃子个数为f(n)
则f(n+1)=f(n) / 2 - 1
=> f(n+1) + 2 = [f(n) + 2] / 2
=> f(n) + 2 = [f(1) + 2] / 2 ^ (n - 1)
=> f(1) = [f(n) + 2] * 2 ^ (n - 1) - 2
因为n = 10, f(n) = f(10) = 1
所以f(1) = 3 * 2 ^ 9 - 1 = 1534

public class OJ {
    public static void main(String[] args) {
        int day = 10;
        int left = 1;
        int total = (left + 2) * (1 << (day - 1)) - 2;
        
        System.out.println(total);
    }
}