更多课程 选择中心

C/C++培训
达内IT学院

400-996-5531

C语言三种算法求解

  • 发布:C++培训
  • 来源:学习笔记
  • 时间:2018-02-11 16:42

最大公约数与最小公倍数的求解是很多初学C的人所面临的一个问题。当然这道问题并不难解答,也有很多人已经写过相关的博客,我在此书写此篇博客,一是为了让自己能够夯实基础,另外就是希望能够帮到和我一样的初学者。

问题:请从键盘上输入两个数值 x,y,请用C语言求出这两个数值的最大公约数与最小公倍数。

首先,我们要想解决这道问题,就要了解什么是最大公约数与最小公倍数。

最大公因数;也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。----来源百度百科

最小公倍数:两个或多个整数公有的倍数叫做它们的公倍数。----来源百度百科

了解了其含义,接下来就是构思算法,通常而言,求解最大公约数有三种算法,而最小公倍数的求解,我们可以很容易的推断出,最小公倍数等于两个数值的乘积除以这两个数值的最大公约数。那么接下来的算法我将在此一一进行列举和解释。

1.辗转相除法: 

又名欧几里德算法(Euclidean algorithm),它是已知最古老的算法, 其可追溯至公元前300年前。 ----来源百度百科

辗转:望文生义,就是翻来覆去。相除就很好理解了,就是进行除法运算。

辗转相除法的核心就是不断的让两个数做除法运算。其原理基于两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。

假设两数为 x,y。

先令 z = x % y ;

之后 y 赋给 x 即令  x = y ;

再将 z 赋给 y 即令  y = z;

辗转相减,其终止条件为:y 等于0时。 

代码如下:

C语言最大公约数与最小公倍数

2.辗转相减法:

即尼考曼彻斯法,其特色是做一系列减法,从而求得最大公约数。----来源百度百科

辗转相减法即通过对两数的不断减法运算。

假设两数为 x, y。

当 x > y 时,令 x = x - y;

反之,则令 y = y - x;

之后一直辗转相减,直至 x = y 时,终止。

代码如下:

C语言最大公约数与最小公倍数

3.穷举法:

穷举法的基本思想是根据题目的部分条件确定答案的大致范围,并在此范围内对所有可能的情况逐一验证,直到全部情况验证完毕。----来源百度百科

穷举法又称枚举法,通过对数值范围内的所有数字进行检验,得出其结果。

代码如下:

C语言最大公约数与最小公倍数

以上即为求解最大公约数与最小公倍数的三种算法,如有纰漏,还请各位不吝赐教。

预约申请免费试听课

填写下面表单即可预约申请免费试听!怕钱不够?可就业挣钱后再付学费! 怕学不会?助教全程陪读,随时解惑!担心就业?一地学习,可全国推荐就业!

上一篇: 学习C语言基本思路与参考书籍
下一篇:C++编程语言“类”知识点总结

C语言创建windows窗口实例

C++回调函数是什么?

C++ shared_ptr和动态数组

C语言有哪些关键词,C语言44个关键词大全

Copyright © 2023 Tedu.cn All Rights Reserved 京ICP备08000853号-56 京公网安备 11010802029508号 达内时代科技集团有限公司 版权所有

选择城市和中心
黑龙江省

吉林省

河北省

湖南省

贵州省

云南省

广西省

海南省