• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【思维】P5743 【深基7.习8】猴子吃桃——有趣的解法,归纳推导

开发技术 开发技术 6个月前 (07-09) 35次浏览

P5743 【深基7.习8】猴子吃桃 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解 P5743 【【深基7.习8】猴子吃桃】 – 菜鸡 return 的 blog – 洛谷博客 (luogu.com.cn)

题目很简单,循环或者递归都可解决,但这篇题解的思路很有趣。

题目描述:

一只小猴买了若干个桃子。第一天他刚好吃了这些桃子的一半,又贪嘴多吃了一个;接下来的每一天它都会吃剩余的桃子的一半外加一个。

第 n(n20) 天早上起来一看,只剩下 1 个桃子了。请问小猴买了几个桃子?

设ansi表示n=1时的答案,显然ans1=1。

则(ansi/2)-1=ansi​-1 ,即ansi=2(ansi​-1+1)

到了这一步,再运用高中的数列表达式推导,可得:ansn=3×2n-1-2。


喜欢 (0)