C语言求最大公约数代码

C语言求最大公约数代码题目:随机输入两个数,求其最大公约数在此展示三种常用解题思路1.首先展示第一种思路#include<stdio.h>intmain(){ inta,b,c;//先定义变量 printf(“请输入:\n”); scanf(“%d%d”,&a,&b);//输入两个整型数字 if(a>b) { for(inti=b;i>0;i) { if(a%i==0&&b%i==

题目:随机输入两个数,求其最大公约数

在此展示三种常用解题思路
1.首先展示第一种思路

#include <stdio.h>
 int main()
{ 
   
	int a,b,c;             //先定义变量
	printf("请输入:\n");
	scanf("%d%d",&a,&b);   //输入两个整型数字
	if(a<b)               
	{ 
   
		c=a;
		a=b;
		b=c;               //保证a≥b
	}
	int i = 0;
	for(i = b;i>0;i--)
	{ 
   
		if(a%i == 0 && b%i == 0)                
		{ 
   
			printf("gcd(%d,%d) = %d\n",a,b,i);
			break;
		}
	}
	return 0;
}

2.辗转相除法
这里涉及到一个公式:GCD(a,b) = GCD(b,a%b)

#include <stdio.h>
int main()
{ 
   
	int a,b,c;
	printf("请输入:");
	scanf("%d%d",&a,&b);
	if(a<b)
	{ 
   
		c = a;
		a = b;
		b = c;                      //确保a≥b
	}
	while(b != 0)                   
	{ 
   	
		c = b;
		b = a%b;                    //辗转相除:相比第一种思路大大提高了代码的效率
		a = c;
	}
	printf("最大公约数为:%d",a);
	return 0;
}

还有一种运用递归的思想

#include <stdio.h>
int Gcd(int a,int b)
{ 
   
	if(a > b)
	{ 
   
		if(a % b == 0)
		{ 
   
			return b;
		}
		else
		{ 
   
			return Gcd(b,a%b);    
		}
	}
	else
	{ 
   
		if(b % a == 0)
		{ 
   
			return a;
		}
		else
		{ 
   
			return Gcd(a,b%a);
		}
	}
}
int main()
{ 
   
	int a, b;
	int c = 0;
	printf("请输入两个整数:");
	scanf("%d%d",&a, &b);
	c = Gcd(a, b);
	printf("GCD(%d,%d)=%d\n",a,b,c);
}

3.更相减损术
定义:(如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用2来约分)。如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,一直到减数与差相等为止,用这个相等的数字来约分。

#include <stdio.h>
main()
{ 
   
	int a,b;
	printf("请输入两个正整数:");
	scanf("%d%d",&a,&b);
	while(a%2==0)
	{ 
   
		a/=2;
	}
	while(b%2==0)
	{ 
   
		b/=2;
	}               //让两个数都为奇数
	while(a!=b)
	{ 
   
		if(a>b) a=a-b;               
		else b=b-a;              //更相减损术:当差值等于减数的值时即为最大公约数
	}
	printf("GCD=%d\n",a);
	return 0;
}

本文结束,感谢阅览!

今天的文章C语言求最大公约数代码分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/26805.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注