python猴子吃桃是穷举法_Python算法题孙悟空吃蟠桃

孙悟空第一天摘下若干蟠桃&＃xff0c;当即吃了一半&＃xff0c;还不过瘾&＃xff0c;又多吃了一个。第二天早上&＃xff0c;他又将剩下的蟠桃吃掉了一半&＃xff0c;还不过瘾&＃xff0c;又多吃了一个。之后每天早上都吃掉前一天剩下的桃子的一半零一个。到第十天早上再想吃时&＃xff0c;就只剩下一个蟠桃了。求孙悟空第一天共摘了多少个蟠桃&＃xff1f;

此题目利用递推的思想&＃xff0c;倒推是一种很直观的做法。第十天是1个&＃xff0c;根据题意后一天吃掉前一天的一半零一个。那第九天的蟠桃是第十天的一倍加1个再加上第十天的。 即&＃xff1a;

x9 &＃61; 2 * x10 &＃43; 1 &＃43; x10 &＃61; 2 * x10 &＃43; 2 &＃61; 4

那好办了。有了这个2x&＃43;2的公式。我用一个循环代入&＃xff0c;倒推到第一天就能知道第一天的蟠桃数了。

递推法

def eat01(n&＃61;10):

x &＃61; 1

while n > 1:  # 因为从10开始循环&＃xff0c;第十天是1个桃&＃xff0c;终止条件不能等1&＃xff0c;否则就多算了1天

x &＃61; (2 * x &＃43; 2)

n -&＃61; 1

return x

这道题用递归的方法也能解决。

上面的公式我们可以表示为&＃xff1a;

x(n-1) &＃61; 2 * xn &＃43;2

因为这是一个从大到小的递减数列&＃xff0c;递归终止条件为10&＃xff0c;算起来不方便。我们可以把数列逆序排列一下&＃xff0c;公式可以变成这样&＃xff1a;

xn &＃61; 2 * x(n-1) &＃43; 2

递归公式也就出来了。

x1 &＃61; 1 &＃xff1b;n &＃61; 1(递归终止条件)

xn &＃61; 2 * x(n-1) &＃43; 2

递归法

def eat02(n&＃61;10):

if n &＃61;&＃61; 1:

return 1

else:

return eat02(n-1) * 2 &＃43; 2

答案&＃xff1a;1534