递推法求两个整数的最大公约数c语言代码
时间: 2023-12-10 08:19:49 浏览: 43
使用递推法求两个整数的最大公约数,可以使用辗转相减法,以下是示例代码:
```c
#include <stdio.h>
int gcd(int a, int b) {
while (a != b) {
if (a > b) {
a = a - b;
} else {
b = b - a;
}
}
return a;
}
int main() {
int num1, num2, result;
printf("请输入两个整数:\n");
scanf("%d %d", &num1, &num2);
result = gcd(num1, num2);
printf("最大公约数是:%d", result);
return 0;
}
```
这个程序会要求用户输入两个整数,然后使用 while 循环来计算它们的最大公约数,并输出结果。
相关问题
用C语言求斐波那契数列前多少项和递推法
斐波那契数列是指从第3项开始,每一项都是前两项的和,即:
F(1) = 1, F(2) = 1
F(n) = F(n-1) + F(n-2) (n >= 3)
用递推法可以求出斐波那契数列前n项的和,C语言代码如下:
```c
#include <stdio.h>
int main() {
int n, i;
long long a, b, c, sum;
printf("请输入要求的斐波那契数列项数:");
scanf("%d", &n);
a = b = 1; // 初始化前两项为1
sum = 2; // 初始化和为2(前两项之和)
for (i = 3; i <= n; i++) { // 从第三项开始循环
c = a + b; // 当前项为前两项之和
sum += c; // 累加到和中
a = b; // 更新前两项
b = c;
}
printf("斐波那契数列前%d项的和为:%lld\n", n, sum);
return 0;
}
```
这个程序的时间复杂度是O(n),空间复杂度是O(1)。
java递推求两数最大公约数
在Java中,可以使用递推的方式来求两个数的最大公约数。最常用的递推算法是欧几里得算法(Euclidean algorithm)。以下是一个示例代码:
```java
public class Main {
public static void main(String[] args) {
int num1 = 24; int num2 = 36;
int gcd = findGCD(num1, num2);
System.out.println("最大公约数是:" + gcd);
}
public static int findGCD(int num1, int num2) {
while (num2 != 0) {
int temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}
}
```
在上面的代码中,我们定义了一个`findGCD`方法来计算两个数的最大公约数。使用一个while循环,每次迭代都将较小的数赋值给`num1`,较大的数赋值给`num2`,然后计算它们的余数并更新`num1`和`num2`的值,直到`num2`为0时停止循环。最后返回`num1`作为最大公约数。
运行上述代码,将输出最大公约数为12。