设计四种求解斐波那契数列问题的c语言算法程序,并用计时法测量算法运行时间
时间: 2024-09-18 21:11:48 浏览: 14
设计四种不同的C语言算法来求解斐波那契数列问题:
1. **递归**:
```c
#include <stdio.h>
#include <time.h>
long long fib_recursive(int n) {
if (n <= 1)
return n;
else
return fib_recursive(n - 1) + fib_recursive(n - 2);
}
int main() {
int n;
clock_t start, end;
double duration;
printf("Enter the value of n: ");
scanf("%d", &n);
start = clock();
long long result = fib_recursive(n);
end = clock();
duration = ((double)(end - start)) / CLOCKS_PER_SEC; // 计算运行时间
printf("Fibonacci number at position %d is: %lld\n", n, result);
printf("Recursive method took %.6f seconds.\n", duration);
return 0;
}
```
2. **循环迭代**:
```c
#include <stdio.h>
#include <time.h>
long long fib_iterative(int n) {
long long a = 0, b = 1, c;
if (n <= 1)
return n;
for (int i = 2; i <= n; ++i) {
c = a + b;
a = b;
b = c;
}
return b;
}
// 同样在main函数里测量时间...
```
3. **矩阵快速幂**(使用动态规划思想,效率更高):
```c
#include <stdio.h>
#include <time.h>
long long fast_fib(int n) {
static const long long fib_matrix[2][2] = {{1, 1}, {1, 0}};
long long result = {1, 0};
while (n > 0) {
if (n % 2 == 1)
result = matrix_multiply(result, fib_matrix);
fib_matrix = matrix_multiply(fib_matrix, fib_matrix);
n /= 2;
}
return result[0];
}
// ...同样在main里计算时间...
```
4. **预计算表**(适用于较小范围内的查询):
```c
#include <stdio.h>
#include <time.h>
static long long fib_table[100];
void init_fib_table() {
fib_table[0] = 0;
fib_table[1] = 1;
for (int i = 2; i < 100; ++i)
fib_table[i] = fib_table[i - 1] + fib_table[i - 2];
}
// 在主函数里,先初始化表格然后查询...
```
在这四个例子中,你需要分别在`main`函数中记录开始和结束时间,然后计算并打印出各自算法的运行时间。