递归求解双递推摆动数列 a(1)=1,a(2i)=a(i)+1,a(2i+1)=a(i)+a(i+1) (i为正整数) 试建立递归,求该数列的第n(n<100000)项与前n项之和。C语言 含注释
时间: 2024-05-04 08:18:39 浏览: 10
以下是递归求解双递推摆动数列的 C 语言代码,同时包括了第 n 项和前 n 项之和的计算。注释中有详细解释。
```c
#include <stdio.h>
int a[100000]; // 定义一个数组存储数列的值
// 递归函数,计算第 n 项
int calc_nth(int n) {
if (n == 1) {
return 1;
} else if (n % 2 == 0) {
return calc_nth(n / 2) + 1;
} else {
return calc_nth((n - 1) / 2) + calc_nth((n + 1) / 2);
}
}
// 递归函数,计算前 n 项之和
int calc_sum(int n) {
if (n == 0) {
return 0;
} else {
return a[n] + calc_sum(n - 1);
}
}
int main() {
int n;
scanf("%d", &n);
a[1] = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
a[i] = a[i / 2] + 1;
} else {
a[i] = a[(i - 1) / 2] + a[(i + 1) / 2];
}
}
printf("第%d项的值为:%d\n", n, calc_nth(n));
printf("前%d项之和为:%d\n", n, calc_sum(n));
return 0;
}
```
需要注意的是,由于这个数列的项数最大可以达到 100000,因此需要使用数组来存储每一项的值。同时,为了避免重复计算,我们在计算第 n 项的同时也计算出了前 n 项之和,并且在计算前 n 项之和时直接使用了数组中已经计算好的值。