基于欧几里德算法的使用

欧几里德算法称为辗转相除法，用来求已知m、n两个自然数的公因数。结合程序说明一下辗转相除的具体情况。

首先看递归实现：


代码如下:

int getcd(int m,int n)
 {
     if (m < 0 || n <0) {
         return 0;
     }
     if(m < n)
     {
         int t = m;
         m = n;
         n = t;
     }
     if(m % n)
     {
         return getcd(n,(m % n));
     }
     else
     {
         return n;
     }
 }

主要计算过程分为三个步骤：

1、对输入的两个自然数m > n取余数r，使得0<= r < n

2、如果r为0，n即为所求结果，直接返回

3、r不为0，则赋值m=n,n=r从步骤1开始重新执行

　　两自然数的公因数的定义说明了计算结果产生的条件。如果步骤1中计算出的余数r = 0，则较小的数为公因数。如果r!=0则自然数m、n的关系可表示为：m = kn + r（其中k为自然数），等式可以证明能整除m的任何数必定能整除n和r；等式进一步可变形为：r = m - kn，说明同时整除m、n的任何数也必定能整除r。也就是说，能整除m、n的数的集合与整除n、r的数的集合相等。所以辗转相除的方法成立。

再发布一个循环实现欧几里德算法的版本。


代码如下:

int getcd2(int m,int n)
 {
     if (m < 0 || n <0) {
         return 0;
     }
     if(m<n)
     {
         int t=m;
         m=n;
         n=t;
     }
     int cd = 1;
     while(1){
         int r = m % n;
         if(0==r)
         {
             cd = n;
             break;
         }
         else {
             m=n;
             n=r;
         }
     }
     return cd;
 }

赞 (0)

相关推荐

  • 基于欧几里德算法的使用

    欧几里德算法称为辗转相除法,用来求已知m.n两个自然数的公因数.结合程序说明一下辗转相除的具体情况. 首先看递归实现: 复制代码 代码如下: int getcd(int m,int n) {     if (m < 0 || n <0) {         return 0;     }     if(m < n)     {         int t = m;         m = n;         n = t;     }     if(m % n)     {       

  • PHP基于回溯算法解决n皇后问题的方法示例

    本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向

  • 判断用户输入的银行卡号是否正确的方法(基于Luhn算法的格式校验)

    开发中,有时候,为了打造更好的用户体验,同时减轻服务器端的压力,需要对于一些如,手机号码,银行卡号,身份证号码进行格式校验 下面是判断银行卡号输入是否正确的代码(基于Luhn算法的格式校验): iOS代码: /** * 银行卡格式校验 * * @param cardNo 银行卡号 * * @return */ + (BOOL) checkCardNo:(NSString*) cardNo{ int oddsum = 0; //奇数求和 int evensum = 0; //偶数求和 int al

  • Python基于分水岭算法解决走迷宫游戏示例

    本文实例讲述了Python基于分水岭算法解决走迷宫游戏.分享给大家供大家参考,具体如下: #Solving maze with morphological transformation """ usage:Solving maze with morphological transformation needed module:cv2/numpy/sys ref: 1.http://www.mazegenerator.net/ 2.http://blog.leanote.com

  • Python基于DES算法加密解密实例

    本文实例讲述了Python基于DES算法加密解密实现方法.分享给大家供大家参考.具体实现方法如下: #coding=utf-8 from functools import partial import base64 class DES(object): """ DES加密算法 interface: input_key(s, base=10), encode(s), decode(s) """ __ip = [ 58,50,42,34,26,18,

  • Nodejs基于LRU算法实现的缓存处理操作示例

    本文实例讲述了Nodejs基于LRU算法实现的缓存处理操作.分享给大家供大家参考,具体如下: LRU是Least Recently Used的缩写,即最近最少使用页面置换算法,是为虚拟页式存储管理服务的,是根据页面调入内存后的使用情况进行决策了.由于无法预测各页面将来的使用情况,只能利用"最近的过去"作为"最近的将来"的近似,因此,LRU算法就是将最近最久未使用的页面予以淘汰. 可以用一个特殊的栈来保存当前正在使用的各个页面的页面号.当一个新的进程访问某页面时,便将

  • Python基于动态规划算法计算单词距离

    本文实例讲述了Python基于动态规划算法计算单词距离.分享给大家供大家参考.具体如下: #!/usr/bin/env python #coding=utf-8 def word_distance(m,n): """compute the least steps number to convert m to n by insert , delete , replace . 动态规划算法,计算单词距离 >>> print word_distance("

  • Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例

    Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例

    本文实例讲述了Python2.7基于笛卡尔积算法实现N个数组的排列组合运算.分享给大家供大家参考,具体如下: 说明:本人前段时间遇到的求n个数组的所有排列组合的问题,发现笛卡尔积算法可以解决,但是网上搜索的只有Java版本的实现,于是自己试着用python实现,由于新手代码不太规范. 代码:本人封装了一个类Cartesian(笛卡尔),其中封装了变量和方法: 1.变量 datagroup : 表示n个list(python 中的list与其他编程中的数组定义类似)的集合,即一个二维数组 coun

  • Java基于分治算法实现的线性时间选择操作示例

    Java基于分治算法实现的线性时间选择操作示例

    本文实例讲述了Java基于分治算法实现的线性时间选择操作.分享给大家供大家参考,具体如下: 线性时间选择问题:给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素,(这里给定的线性集是无序的). 随机划分线性选择 线性时间选择随机划分法可以模仿随机化快速排序算法设计.基本思想是对输入数组进行递归划分,与快速排序不同的是,它只对划分出的子数组之一进行递归处理. 程序解释:利用随机函数产生划分基准,将数组a[p:r]划分成两个子数组a[p:i]和a[i+1:r],使a[p

  • Java基于分治算法实现的棋盘覆盖问题示例

    Java基于分治算法实现的棋盘覆盖问题示例

    本文实例讲述了Java基于分治算法实现的棋盘覆盖问题.分享给大家供大家参考,具体如下: 在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖.四个L型骨牌如下图: 棋盘中的特殊方格如图: 实现的基本原理是将2^k * 2^k的棋盘分成四块2^(k - 1) * 2^(k - 1)的子棋盘,特殊方格一定在其中的一个子棋盘中,如果特殊方格在某一个子棋盘中,继续递归处理这个子棋盘,直到这个子棋盘中只有一个方格为止如果特殊方格不

随机推荐