秒杀一道水题qwq[猴子吃桃问题]

题目：
一只小猴买了若干个桃子。第一天他刚好吃了这些桃子的一半，又贪嘴多吃了一个；接下来的每一天它都会吃剩余的桃子的一半外加一个。第
n(n\le20)n(n≤20) 天早上起来一看，只剩下 1 个桃子了。请问小猴买了几个桃子？

这是本蒟蒻第一次写题解qwq
废话少说贴代码：
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; long
long t=3*pow(2.0,n-1)-2; if(n!=0)cout<<t; else if(n==0)cout<<1; }
原理很简单
我们将最后一天记为a1=1

然后我们有递推关系 an =2*（ an-1 +1）

dalao可以直接用不动点法求得an

当然，经过恒等变换

可得an+2 =2*（ an-1 +2） 令bn=an+2

有b1=3 且bn=2bn-1 bn是公比为2首项为3的等比数列！

故bn=32^(n-1) an=32^(n-1)-2;

于是我们就可以直接输出了！（别忘记讨论n==0的情况）

注意，在n较大时为了保证范围要开long long

我就是因为这个第一次没AC

• « 上一篇：iOS 系统校园无线WIFI认证上网指南
• » 下一篇：小梅哥——38译码器