请写出对应计算如下算式的程序段：

注：改编自第二届全国青少年信息学（计算机）奥林匹克分区联赛1-7

【答案】

O(n^2)的算法非常容易想到，这里介绍O(n)的算法。

我们可以对原始函数做如下变化：

可以看出，原始函数的计算方式就可以变成不停计算加法和乘法的迭代式子。

示例代码如下：

1. #include  

2. using namespace std;  

3. const int N = 3;  

4. int main()  

5. {  

6.     int a[N+1] = {1, 2, 3, 4};  

7.     int x = 2;  

9.     //方法1   

10.     int y = a[N];  

11.     for(int i=N-1; i>=0; i--)      

12.     {      

13.         y = y*x+a[i];  

14.     }  

15.     cout << y << endl;  

17.     //方法2   

18.     y = a[N];  

19.     for(int i=N; i>=1; i--)      

20.     {      

21.         y = y*x+a[i-1];  

22.     }  

23.     cout << y << endl;  

25.     //方法3   

26.     y = 0;  

27.     for(int i=N; i>=0; i--)      

28.     {      

29.         y = y*x+a[i];  

30.     }  

31.     cout << y << endl;  

32.     return 0;   

33. }  

小智编程由硅谷人工智能专家伯克利大学熊宇红博士和清华大学靳简明博士后创立。为5~18岁青少年量身定制线下小班素质课程，通过学习Scratch、Python、C++、信息学奥赛，培养解决复杂问题的能力、提高逻辑思维能力和计算能力，实现与未来的对话。

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com