欧几里德算法及扩展

目录

今天老师跟我们讲算法于程序设计了

嗯嗯 说到算法 就是有很多话说了 算法是计算机的基石、灵魂,李开复曾经写过一篇算法的力量

伟大的高德纳没错就是发明Tex的伟大科学家,写了 The Art of Computer Programming这又一经典的书籍

看得我们是仰望膜拜不已。现在 我终于又再一次回归到算法的源头来了 。是的源头。

大一曾经学习过算法,不过那不是学习,仅仅是在学习打字而已,把代码敲到电脑上去,然后debug,就这么简单,没有人告诉怎么样学习算法。现在 大多快忘光光了把 什么二叉树 快速选择 谁还会记得

没办法 现在只有捡起来了。继续算法研究,额,惭愧。。。

定理:gcd(a,b) = gcd(b,a mod b)

证明: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)的公约数

假设d 是(b,a mod b)的公约数,则 d | b , d |r ,但是a = kb +r 因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

欧几里德算法

根据这个原理来做的,其算法用C++语言描述为:

void swap(int & a, int & b){//交换数字大小
    int c = a;
    a = b;
    b = c;
}

int gcd(int a,int b){//取公约数
    if(0 == a ){//a不等于0
        return b;
    }

    if( 0 == b){//b不等于0
        return a;
    }

    if(a > b){//交换a,b的值
        swap(a,b);
    }

    int c;
    for(c = a % b ; c > 0 ; c = a % b){//for循环 初始条件c=a取b的模  结束条件 c=0
        a = b;
        b = c;
    }

    return b;
}

用Java实现代码:

package algorithm;
/**
 *<p>hibernate-tutorialDescription:欧几里德算法</p>
 *@version1.0.0
 *@CopyrightCopyright(c)2008
 */
public class MaxFeed{
    public int getnum(int m,int n){//获取两个数字
 int r=getleave(m,n);//这个是什么?
        while(r!=0){
            int[] s=swapnum(m,n,r);
            m=s[0];
            n=s[1];
            r=getleave(m,n);
        }
        return n;
    }
    /**
     *@paramm
     *@paramn
     *@return
     */
    private int getleave(int m,int n){//求余函数
        int r=m%n;
        return r;
    }
    /**
     *<p>comments:交换
     *          </p>
     *@paramm
     *@paramn
     *@paramr
     *@return
     */
    private int[] swapnum(int m,int n,int r){//什么意思
        m=n;
        n=r;
        int[] s=newint[2];
        s[0]=m;
        s[1]=n;
        return s;
    }
    /**
     *<p>comments:测试用例
     *          </p>
     *@paramargs
     */
    public static void main(String[] args){//主函数
        MaxFeed maxFeed=new MaxFeed();//实例化 嘿嘿
        int r=maxFeed.getnum(96,27);
        System.out.println("***********************************\n\n\n");
        System.out.println("                 "+r);
        System.out.println("***********************************");
    }
}
求n个整数的最大公约数扩展
#include <stdio.h>

void main()
{  int k,n;
 long a,b,c,r,m[100];
 printf("请输入整数个数n:");//输入原始数据
 scanf("%d",&n);
 printf("请依次输入%d个整数:",n);

 for(k=0;k<=n-1;k++)//循环输入正整数
 { printf("\n请输入第%d个整数: ",k+1);
 scanf("%ld",&m[k]);}

 b=m[0];
 for(k=1;k<=n-1;k++)//利用n-1次欧几里德算法
 {  a=m[k];
 if(a<b) {c=a;a=b;b=c;}//交换a  b
 r=a%b;
 while(r!=0)//判断终止条件
 { a=b;b=r;r=a%b;}
 }

 printf("%ld",m[0]);
 for(k=1;k<=n-1;k++)//输出结果
 printf(",%ld",m[k]);
 printf("的最大公约数是%ld",n);
}