CSP/信奥赛C++语法基础刷题训练（11）：洛谷P5743：猴子吃桃

CSP/信奥赛C++语法基础刷题训练（11）：洛谷P5743：猴子吃桃

题目描述

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

输入格式

输入一个正整数 n n n，表示天数。

输出格式

输出小猴买了多少个桃子。

样例 #1

样例输入 #1

4

样例输出 #1

22

提示

数据保证， 1 ≤ n ≤ 20 1\le n\le20 1≤n≤20。

AC代码

#include<bits/stdc++.h>
using namespace std;
/*思路： 
1、研究 a1 a2
   非空子集为{a1}、{a2}、{a1、a2}
   子集元素之和为a1+a2+a1+a2=(a1+a2)*2
2、研究 a1 a2 a3
   非空子集为{a1}、{a2}、{a3}、{a1、a2}、{a1、a3}、{a2、a3}、 {a1、a2、a3}
   子集元素之和为a1+a2+a3+a1+a2+a1+a3+a2+a3+a1+a2+a3=(a1+a2+a3)*2^2
3、继续研究a1、a2、a3、a4
   子集元素之和为(a1+a2+a3+a4)*2^3
4、总结归纳：如果有x个元素，则自己元素之和为：  所有元素之和*2^(x-1)
*/
int a[40],n=1;
long long sum=0;

int main(){
	while(cin>>a[n]) n++; 
	for(int i=1;i<n;i++){
		sum+=a[i];//计算所有元素之和 
	}
	sum=sum*pow(2,n-2); 
	cout<<sum;
	return 0;
} 
//提醒测试验证时，输入结束后按ctrl+Z结束输入 

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容