洛谷 P1028 [NOIP2001 普及组] 数的计算（递推）

本文主要是介绍洛谷 P1028 [NOIP2001 普及组] 数的计算（递推），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述： 

 

---

分析： 

i	a[i]	构造数组
1	1	1
2	2	2 21
3	2	3 31
4	4	4 41 42 421
5	4	5 51 52 521
6	6	6 61 62 63 621 631
7	6	7 71 72 73 721 731
8	10	8 81 82 83 84 821 831 841 842 8421
9	10	.............
10	14	..............
11	14	.............

通过上面大家大家能发现什么呢？ 

a[1] = 1;

a[2] = 2;

a[3] = 2;

a[4] = a[2] + a[3] = a[i/2] + a[i/2+1] = 4;

a[5] = a[2] + a[3] = a[i/2] + a[i/2+1] = 4;

a[6] = a[3] + a[4] = a[i/2] + a[i/2+1] = 6;

a[7] = a[3] + a[4] = a[i/2] + a[i/2+1] = 6;

a[8] = a[4] + a[6] = a[i/2] + a[i/2 + 2] = 10;

a[9] = a[4] + a[6] = a[i/2] + a[i/2 + 2] = 10;

a[10] = a[5] + a[8] = a[i/2] + a[i/2 + 3] = 14;

a[11] = a[5] + a[8] = a[i/2] + a[i/2 + 3] = 14;

综上所述： 

        递推出的公式：         

a[i] = a[i/2] + a[i/2 + j];

---

AC代码： 

#include<iostream>using namespace std;const int N = 1010;
int a[N];int main()
{int n;cin >> n;if(n == 1) {cout << 1;}else if(n == 2){cout << 2;}else if(n == 3){cout << 2;}else{a[1] = 1,a[2] = 2,a[3] = 2;int i,j=1;for(i=4;i<=n;i++){a[i] = a[i/2 + j] + a[i/2];if(i%2!=0) j++; }cout << a[i-1] << endl;}return 0;
}

欢迎不会的小伙伴留言哦~

这篇关于洛谷 P1028 [NOIP2001 普及组] 数的计算（递推）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---