新知识
例1.插入数值
有一个序列，初始时只有两个数x和y，之后每次操作时，在原序列的任意两个相邻数之间插入这两个数的和，得到新序列。问操作n次之后，得到的序列的所有数之和是多少？
题目分析
以初始序列1,2为例进行说明。
- 初始数列：1,2
- 操作1次：1,3,2
- 操作2次：1,4,3,5,2
- 操作2次后序列数值和=1+4+3+5+2=15
第1次操作在1和2中间插入1+2=3。
第2次操作在1和3中间插入4,3和2中间插入5。
完整代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x,y,n;
cin>>x>>y>>n;
vector<int> s,tmp;
s.push_back(x);
s.push_back(y);
for(int i=0;i<n;i++){
for(int c=0;c<s.size()-1;c++){
tmp.push_back(s[c]);
tmp.push_back(s[c]+s[c+1]);
}
tmp.push_back(s[s.size()-1]);
s = tmp;
tmp.clear();
}
cout<<accumulate(s.begin(),s.end(),0);
return 0;
}
程序利用两个vector容器s和tmp，每次计算除了把原有数加入，还把相邻两个数的和也加入。最后用accumulate函数计算容器中的和。
更好的办法
上面程序虽然可以求出正确值，但要把每次循环的新值都罗列一便。随着次数越多，新容器中的值就越多。不是很方便。其实我们可以通过观察每次循环后，新数值的数量变化来找出规律，把规律转换成公式来计算。
| n值 | 数列 | x和y的数量 |
|---|
| 0 | 6,7 | 1 |
| 1 | 6,(6,7),7 | 2 |
| 2 | 6,(6,6,7),(6,7),(6,7,7),7 | 5 |
| 3 | 6,(6,6,6,7),(6,6,7),(6,6,7,6,7),(6,7),(6,7,6,7,7),(6,7,7),(6,7,7,7) | 14 |
思考：通过表格中的数据，你能归纳出公式了吗？
