当前位置：首页 > news >正文

累和，累积，斐波拉契

news 2025/7/18 14:34:37

累和、累积、斐波拉契

一、累和（Sum）

1. 定义

累和指将一系列数值依次相加的结果。例如，数列 1,2,3,4 的累和为 1+2+3+4=10。

2. C 语言实现

#include <stdio.h>// 计算前n个自然数的累和（迭代法）
int sum_iterative(int n) {int sum = 0;for (int i = 1; i <= n; i++) {sum += i;}return sum;
}// 计算前n个自然数的累和（数学公式）
int sum_formula(int n) {return n * (n + 1) / 2;
}int main() {int n = 10;printf("迭代法累和: %d\n", sum_iterative(n));printf("公式法累和: %d\n", sum_formula(n));return 0;
}

3. 性能分析

迭代法：时间复杂度 (O(n))，需遍历 n 次。
公式法：时间复杂度 (O(1))，直接计算。

二、累积（Product）

1. 定义

累积指将一系列数值依次相乘的结果。例如，数列 1,2,3,4 的累积为 1×2×3×4=24（即 4 的阶乘）。

2. C 语言实现

#include <stdio.h>// 计算前n个自然数的累积（迭代法）
int product_iterative(int n) {int product = 1;for (int i = 1; i <= n; i++) {product *= i;}return product;
}// 计算前n个自然数的累积（递归法）
int product_recursive(int n) {if (n == 0) return 1;return n * product_recursive(n - 1);
}int main() {int n = 5;printf("迭代法累积: %d\n", product_iterative(n));printf("递归法累积: %d\n", product_recursive(n));return 0;
}

3. 性能分析

迭代法：时间复杂度 (O(n))，需遍历 n 次。
递归法：时间复杂度 (O(n))，但递归深度为 n，可能导致栈溢出（如 n>10000）。

三、斐波那契数列（Fibonacci）

1. 定义

斐波那契数列满足：(F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2))（n≥2）。例如：0, 1, 1, 2, 3, 5, 8, 13, ...

2. C 语言实现

#include <stdio.h>// 方法1：递归法
int fib_recursive(int n) {if (n <= 1) return n;return fib_recursive(n - 1) + fib_recursive(n - 2);
}// 方法2：迭代法（循环）
int fib_iterative(int n) {if (n <= 1) return n;int a = 0, b = 1, c;for (int i = 2; i <= n; i++) {c = a + b;a = b;b = c;}return b;
}// 方法3：矩阵快速幂（高效算法）
void multiply(int F[2][2], int M[2][2]) {int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];F[0][0] = x;F[0][1] = y;F[1][0] = z;F[1][1] = w;
}void power(int F[2][2], int n) {if (n == 0 || n == 1) return;int M[2][2] = {{1, 1}, {1, 0}};power(F, n / 2);multiply(F, F);if (n % 2 != 0) multiply(F, M);
}int fib_matrix(int n) {if (n == 0) return 0;int F[2][2] = {{1, 1}, {1, 0}};power(F, n - 1);return F[0][0];
}int main() {int n = 10;printf("递归法斐波那契: %d\n", fib_recursive(n));printf("迭代法斐波那契: %d\n", fib_iterative(n));printf("矩阵法斐波那契: %d\n", fib_matrix(n));return 0;
}