猴子吃桃

【题目描述】

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

【输入描述】

一行，表示第N天

【输出描述】

桃子总数

【样例输入】

10

【样例输出】

1534

---

【题目分析】

(1)如果N是定值可以当成小学奥数题来反推
(2)可以采用逆向思维，从后往前推

【参考代码1】

#include<cstdio>
int main() {
	int n,i,s=1;
	scanf("%d",&n);
	for(i=0; i<n-1; i++)
		s=2*(s+1);
	printf("%d",s);
	return 0;
}

---

【增加难度】

这是一道比较简单的递推题，根据公式推导即可，但是可以把这个题目加大难度，比如N<=100。那么普通的做法就会超范围。如果我把代码改成下面的样子

#include<cstdio>
int main() {
	long long n,i,s=1;
	scanf("%d",&n);
	for(i=0; i<n-1; i++)
		s=2*(s+1);
	printf("%lld",s);
	return 0;
}

最多支持62位，距离100位还有一段，所以要考虑使用高精度了。

---

返回目录：题解目录

---