c语言程序设计（写一下）
求第n个fibonacci数，注意n可能很大，当n很大时，所对应的fibonacci数可能超过整数的表示范围。
基于new bing 的编写：
【方法】
- 使用字符串数组实现斐波那契数列的计算，相较于直接使用整型数值，使用字符串数组能够方便地处理大数值的加法和赋值，从而支持求解更大范围的斐波那契数列。
【运行截图】
【思路】：
- 定义 assign() 函数，用于将一个字符数组 b 赋值给另一个字符数组 a。该函数实现了字符级别的赋值操作，避免了整个字符串的复制，因此可以提高效率。
- 定义 add() 函数，实现两个大数值字符串数组的加法运算。为了方便处理加法中的进位，我们从后往前遍历两个字符串，在各个位置上分别相加，并将结果保存在另一个字符串数组 c 中。需要注意的是，由于大数值可能超过 int 类型的范围，因此必须使用字符串数组来存储运算结果。
- 定义 fib() 函数，用于计算斐波那契数列中第 n 个数的值。在该函数的实现中，我们使用字符串数组 f、f_1 和 f_2 来保存斐波那契数列中前三个数的值。然后，从第三个数开始，每次计算斐波那契数列中下一个数的值，直到计算到第 n 个数。每次计算下一个数时，我们使用 add() 函数来实现两个数的相加，并用 assign() 函数更新前两个数的值。
【代码】：
#include <stdio.h>
#include <string.h>
#define MAX_N 10000 // 定义一个常量 MAX_N，表示字符串数组的最大长度
void assign(char a[], char b[]) { // 自定义函数 assign，实现字符串赋值
int len_b = strlen(b); // 计算字符串 b 的长度
for (int i = 0; i < len_b; i++) { // 遍历字符串 b，将每个字符赋值给字符串 a
a[i] = b[i];
}
a[len_b] = '\0'; // 字符串末尾添加空字符，表示字符串结束
}
void add(char a[], char b[], char c[]) { // 自定义函数 add，实现字符串加法
int len_a = strlen(a), len_b = strlen(b); // 计算字符串 a、b 的长度
int carry = 0, idx = 0; // 定义进位 carry 和下标 idx，初始值均为 0
for (int i = len_a - 1, j = len_b - 1; i >= 0 || j >= 0; i--, j--) { // 从后往前遍历两个字符串，相加对应位置的数字
int sum = carry;
if (i >= 0) sum += a[i] - '0';
if (j >= 0) sum += b[j] - '0';
c[idx++] = sum % 10 + '0'; // 将相加结果对 10 取模并加上字符 '0'，即得到相应位置的数字字符
carry = sum / 10; // 求出进位 carry
}
if (carry) c[idx++] = carry + '0'; // 如果最高位有进位，则在字符串末尾添加一位
c[idx] = '\0'; // 字符串末尾添加空字符，表示字符串结束
int len_c = strlen(c); // 计算字符串 c 的长度
for (int i = 0; i < len_c / 2; i++) { // 反转字符串 c，以得到正确的加法结果
char tmp = c[i];
c[i] = c[len_c - 1 - i];
c[len_c - 1 - i] = tmp;
}
}
void fib(int n) { // 自定义函数 fib，计算斐波那契数列的第 n 个数
char f[MAX_N], f_1[MAX_N], f_2[MAX_N]; // 定义三个字符串数组，用于存储斐波那契数列中的前三个数
assign(f_1, "0"); // 初始化第一个数为 0
assign(f_2, "1"); // 初始化第二个数为 1
for (int i = 2; i <= n; i++) { // 从第三个数开始依次计算斐波那契数列的下一个数
add(f_1, f_2, f); // 将前两个数相加，得到下一个数
assign(f_1, f_2); // 更新前两个数的值
assign(f_2, f);
}
printf("%dth Fibonacci number is: %s\n", n, f_2); // 输出第 n 个斐波那契数列的数值
}
int main() {
int n = 1000;
fib(n); // 计算斐波那契数列的第 n 个数
return 0;
}
文心一言
#include <stdio.h>
#include <stdlib.h>
int* fib(int n, int* res_size) {
int left = 0, right = 1;
int* res = (int*)malloc(sizeof(int) * n);
res[0] = left;
res[1] = right;
for (int i = 2; i < n; i++) {
int sum = left + right;
res[i] = sum;
left = right;
right = sum;
}
*res_size = n;
return res;
}
int main() {
int n = 100;
int* res = fib(n, &n);
printf("The %dth Fibonacci number is: ", n, res[n-1]);
free(res);
return 0;
}
int fib(int n) {
double sqrt5 = sqrt(5);
double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);
return round(fibN / sqrt5);
}
也可以用这种方法：
struct Matrix {
int mat[2][2];
};
struct Matrix matrixMultiply(struct Matrix* a, struct Matrix* b) {
struct Matrix c;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c.mat[i][j] = (*a).mat[i][0] * (*b).mat[0][j] + (*a).mat[i][1] * (*b).mat[1][j];
}
}
return c;
}
struct Matrix matrixPow(struct Matrix a, int n) {
struct Matrix ret;
ret.mat[0][0] = ret.mat[1][1] = 1;
ret.mat[0][1] = ret.mat[1][0] = 0;
while (n > 0) {
if (n & 1) {
ret = matrixMultiply(&ret, &a);
}
n >>= 1;
a = matrixMultiply(&a, &a);
}
return ret;
}
int fib(int n) {
if (n < 2) {
return n;
}
struct Matrix q;
q.mat[0][0] = q.mat[0][1] = q.mat[1][0] = 1;
q.mat[1][1] = 0;
struct Matrix res = matrixPow(q, n - 1);
return res.mat[0][0];
}
当n很大时，C所对应的Fibonacci数可能会超过整数的表示范围，
由于 C 语言中不支持多精度计算，而且计算复杂度也较高，需要手动管理内存，因此实现较为麻烦，而且计算速度也较慢
使用高精度计算一种常用的方法是使用 Python 中的 decimal 模块。以下是使用 Python 解决该问题的代码示例：
from decimal import Decimal
def fibonacci(n):
# 初始化前两个数
a, b = Decimal('0'), Decimal('1')
for i in range(n):
a, b = b, a + b
return a
n = 1000 # 求第n个数
result = fibonacci(n)
print("第{}个Fibonacci数是：{}".format(n, result))
在计算过程中，使用了两个 Decimal 类型的变量 a 和 b 来分别保存前两个斐波那契数。然后，循环计算下一个斐波那契数，直到计算到第n个数。最后输出计算结果即可。
为了实现求第n个斐波那契数，我们可以采用递归的方式来实现，具体代码如下：
int fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
其中，fibonacci(n) 表示求第n个斐波那契数。如果 n 等于 1 或 2，则直接返回 1；否则，递归地调用 fibonacci(n-1) 和 fibonacci(n-2) 两个函数，并将它们的结果相加。由于这个递归函数会在递归调用的过程中消耗大量的内存，因此在实际应用中，我们需要对递归的深度进行限制，以防止出现栈溢出等问题。
为了避免出现栈溢出，我们可以考虑使用非递归的方式来实现求第n个斐波那契数。具体代码如下：
int fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
int f1 = 1, f2 = 0;
return f2 + f1;
}
}
在这个非递归的实现中，我们用两个整型变量 f1 和 f2 来保存斐波那契数列的前两个值，然后根据 n 的值来计算 f3 的值。具体地，如果 n 等于 1 或 2，则直接返回 f1 或 f2；否则，计算 f3 = f2 + f1，并返回 f3。由于这个非递归的实现不需要使用递归的方式，因此可以避免出现栈溢出等问题。
下面是一个示例程序，演示了如何使用递归和非递归的方式来求第n个斐波那契数：
#include <stdio.h>
int fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
int main() {
int n, res;
printf("请输入斐波那契数列的长度：");
scanf("%d", &n);
res = fibonacci(n);
printf("斐波那契数列的第%d个数为：%d\n", n, res);
return 0;
}
运行示例程序，会提示用户输入斐波那契数列的长度，然后求出第n个斐波那契数。例如，如果用户输入的斐波那契数列长度为 5，则第 5 个斐波那契数为 55。
- 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/876766
- 你也可以参考下这篇文章：C语言:求Fibonacci数列的前n项和
- 除此之外, 这篇博客: 用C语言编写Fibonacci（斐波那契）数列中的 用C语言编写Fibonacci（斐波那契）数列 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
#include <stdio.h> int Fibonacci(int); int main() { int i=1; for(;i<=30;i++) { printf("第%d项:%d\n",i,Fibonacci(i)); } return 0; } int Fibonacci(int m) { int a=0,b=1; int c=1; int i=3; for(;i<m;i+=3) { a=b+c; b=a+c; c=a+b; } switch(m%3) { case 0:return c; case 1:return a; case 2:return b; } } 哈哈好好玩- 以下回答由chatgpt基于相关博客总结生成:
#include <stdio.h> #include <stdlib.h> #include <string.h> char a[20000005], b[20000005], s[20000005];//20000000<32*10^6,所以设为数组 int min(int a, int b) { return a < b ? a : b; } int main() { int i, Na, Nb, K, Al, Bl; memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(s, 0, sizeof(s)); fgets(a, 20000005, stdin); fgets(b, 20000005, stdin); Na = strlen(a) - 1; Nb = strlen(b) - 1;//把换行符忽略掉 Al = Na; for (i = 0; i < Na; i++) { s[i] += a[Na - i - 1] - 48;//把a倒过来存，借鉴大佬通过避免用i滚动数组的做法 } Bl = Nb; for (i = 0; i < Nb; i++) { s[i] -= b[Nb - i - 1] - 48;//把b倒过来存 } K = 1; for (i = 0; i <= min(Al, Bl); i++) { if (s[i] < 0) { s[i] += K * 10; s[i + 1] -= K; } if (s[i] >= K) { K = 0; } s[i] %= K + 10; K = K == 0 ? 1 : K; } for (i = 20000005 - 1; i >= 0; i--) { if (s[i] > 0) break; } for (; i >= 0; i--) { printf("%d", s[i]); } return 0; }