作业帮设计要求 （1）先用C语言描述正确的计算最大公约数的算法 ,保证算法的正确性 （2）然后设计一个该算法的设计要求（1）先用C语言描述正确的计算最大公约数的算法 ,保证算法的正确性（2
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/18 02:43:50
设计要求 （1）先用C语言描述正确的计算最大公约数的算法 ,保证算法的正确性 （2）然后设计一个该算法的设计要求（1）先用C语言描述正确的计算最大公约数的算法 ,保证算法的正确性（2
设计要求 （1）先用C语言描述正确的计算最大公约数的算法 ,保证算法的正确性 （2）然后设计一个该算法的
设计要求
（1）先用C语言描述正确的计算最大公约数的算法 ,保证算法的正确性
（2）然后设计一个该算法的硬件电路,能够计算出来两个32位数的最大公约数.
设计提示
可以采用本节课介绍的基于带有数据的有限状态机设计方法进行硬件电路的设计.给出该设计在ModelSim环境下仿真波形验证结果.
设计要求 （1）先用C语言描述正确的计算最大公约数的算法 ,保证算法的正确性 （2）然后设计一个该算法的设计要求（1）先用C语言描述正确的计算最大公约数的算法 ,保证算法的正确性（2
欧几里德算法又称辗转相除法,用于计算两个正整数a,b的最大公约数.其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)
证明：a可以表示成a = kb + r,则r = a mod b
假设d是a,b的一个公约数,则有
d|a,d|b,而r = a - kb,因此d|r
因此d也是(b,a mod b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证.
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
1.若 r 是 a ÷ b 的余数,则
gcd(a,b) = gcd(b,r)
2.a 和其倍数之最大公因子为 a.
另一种写法是：
1.令r为a/b所得余数（0≤r＜b）
若 b= 0,算法结束；a 即为答案.
2.互换：置 a←b,b←r,并返回第一步.
欧几里德算法的C语言版
/*欧几里德算法：辗转求余
原理:gcd(a,b)=gcd(b,a mod b)
当b为0时,两数的最大公约数即为a
getchar()会接受前一个scanf的回车符
*/
#include
unsigned int Gcd( unsigned int M,unsigned int N )
{
unsigned int Rem;
while( N > 0 )
{
Rem = M % N;
M = N;
N = Rem;
}
return M;
}
void main()
{
int temp;
int a,b;
scanf("%d",&a);
scanf("%d",&b);
printf("the greatest common factor of %d and %d is ",a,b);
printf("%d\n",Gcd(a,b));
}