1205: 神奇数列

题目描述：

现一个函数f(x)，它满足：
f[1] = a, f[2] = b, f[3] = c;
f[n] = 函数前n-1项中偶数的个数（n>=3）;
请求出这个数列的前m项和

输入:

输入四个正整数数对应题目中的a,b,c,m（保证都小于100）
输出
输入前m项和

样例输入

3 1 2 5

样例输出

8

提示

对于样例：f[4]=f[5]=1

问题分析

首先对于这一个问题，我们是知道前三项的，因为给出的函数是递归定义的，也就是我们要求$f(n)$就需要先求出前n-1项都是偶数还是奇数，所以我们可以采用两种方法解决这一个问题。

1. 我们可以在求f(n)的过程中，每一次都遍历所有的元素，然后统计偶数的个数，这样我们需要一个不定长的空间来保存整个数组的元素，然后每一次都需要查看所有已经求出的元素值所以时间复杂度为$O(n^2)$空间复杂度为$O(n)$
2. 第二种方法就是设置一个变量随时记录整个序列中为偶数元素的个数，然后用这个变量去更新序列这样时间复杂度为$O(n)$空间复杂度为$O(1)$

代码如下

方法一：

#include<stdio.h>
#include<stdlib.h>
int main(){
	int a,b,c,m, sum=0;
	scanf("%d %d %d %d", &a, &b, &c, &m);
	int *num = (int *)malloc(sizeof(int)*m);
	num[0] = a;
	num[1] = b;
	num[2] = c;
	for(int i=3; i<m; i++){
		int even = 0;
		for(int j = 0; j < i; j++){
			if(num[j]%2 == 0){
				even += 1;
			}
		}
		num[i] = even;
	}
	for(int i=0; i<m; i++){
		sum += num[i];
	}
	printf("%d", sum);
	return 0;
}

方法二：

#include<stdio.h>
int main(){
   int a[3],m,sum=0;
   int even = 0;
   scanf("%d %d %d %d", &a[0], &a[1], &a[2], &m);
   for(int i = 1; i <= 3; i++){
       if(a[i-1] % 2 == 0){
           even += 1;
       }
       if(i <= m){
           sum += a[i-1];
       }
   }
   for(int i=3; i < m; i++){
       sum += even;
   	if(even%2 == 0){ // 因为偶数的个数就是序列中下一个元素的值，所以直接加上even就行了。
   		even += 1;
   	}
   }
   printf("%d", sum);
   return 0;
}

总结

显然方法二要优于方法一。