斐波那契最大公约数c语言代码
时间: 2023-12-16 16:04:46 浏览: 106
根据提供的引用[1],斐波那契最大公约数算法可以通过以下C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000
void swap(char *a, char *b) {
char temp = *a;
*a = *b;
*b = temp;
}
void reverse(char *num, int len) {
int i = 0, j = len - 1;
while (i < j) {
swap(&num[i], &num[j]);
i++;
j--;
}
}
void add(char *a, char *b, char *result) {
int len_a = strlen(a);
int len_b = strlen(b);
int len = len_a > len_b ? len_a : len_b;
int carry = 0;
int i, j, k;
for (i = len_a - 1, j = len_b - 1, k = len - 1; k >= 0; i--, j--, k--) {
int x = i >= 0 ? a[i] - '0' : 0;
int y = j >= 0 ? b[j] - '0' : 0;
int sum = x + y + carry;
result[k] = sum % 10 + '0';
carry = sum / 10;
}
if (carry) {
printf("Error: the result is out of range!\n");
exit(1);
}
reverse(result, len);
}
void gcd(char *a, char *b, char *result) {
if (strcmp(a, "0") == 0 || strcmp(b, "0") == 0) {
strcpy(result, "0");
return;
}
char temp[MAX];
while (strcmp(b, "0") != 0) {
strcpy(temp, b);
add(a, b, result);
strcpy(a, temp);
strcpy(b, result);
}
strcpy(result, a);
}
void fib(int n, char *result) {
if (n == 0) {
strcpy(result, "0");
return;
}
if (n == 1) {
strcpy(result, "1");
return;
}
char a[MAX], b[MAX], c[MAX];
strcpy(a, "0");
strcpy(b, "1");
int i;
for (i = 2; i <= n; i++) {
add(a, b, c);
strcpy(a, b);
strcpy(b, c);
}
strcpy(result, b);
}
void fib_gcd(int n, char *result) {
char a[MAX], b[MAX], c[MAX];
fib(n, a);
fib(n + 1, b);
gcd(a, b, c);
strcpy(result, c);
}
int main() {
int n = 10;
char result[MAX];
fib_gcd(n, result);
printf("The GCD of F(%d) and F(%d+1) is: %s\n", n, n, result);
return 0;
}
```
阅读全文