递推算法5——逆推法之猴子摘桃问题

逆推法是根据结果推出已知条件，推算方法与顺推法类似，只是需要将结果作为初始条件向前推算。比较典型的例子是猴子摘桃和存取问题

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

【分析】
根据第10天的桃子个数往前推算：
第10天只剩1个桃子；
第九天吃了桃子的一半零一个，假设第9天吃之前的桃子个数为x，则有x-(x/2+1)=1，即x=2×(1+1)。其中第一个1表示第10天的桃子个数。接着往前推算；
假设第八天吃桃子之前有x个，第九天吃桃子前有y个（第九天的桃子个数可以由第10天的桃子个数推算得到），则有x-(x/2+1)=y，即y=2×(y+1)。依此类推，可以得到第1天的桃子个数。推算过程如下：

这个逆推过程可以使用循环实现。

code：

#include<stdio.h>
void main()
{
	int day, x, y;
	day = 10;
	y = 1;
	while (day > 1)
	{
		x = (y + 1) * 2;
		y = x;
		day--;
	}
	printf("第一天摘到的桃子总数是%d.\n", x);
	getchar();
}

结果：