yuanyuelang

常用链接

统计

最新评论

数论(1)-----欧几里得算法

 一.  欧几里得算法------求最大公约数

1.公式：
      gcd(a,b)=gcd(b,a mod b)    (a为非负整数，b为正整数)

2.证明：
      思路：
           两个整数a和b，如果a|b&&b|a（即a,b能互相整除），那么a=b.

      基础知识准备：
           A. (a mod b)=a-qb , q=(int)a/b;
           B. d|a&&d|b => d|(xa+yb) x,y为任意整数
           C. d|a&&d|b => d|gcd(a,b)

      过程：（1）证：gcd(a,b)|gcd(b,a mod b)

                  设d=gcd(a,b)=>d|a&&d|b, 
                  由A和B知道，d|a&&d|b=>d|(xa+yb)=>d|(a mod b)
                  由C知道，d|b&&d|(a mod b)=>d|gcd(b,a mod b)=>gcd(a,b)|gcd(b,a mod b);

            (2) 证：gcd(b,a mod b)|gcd(a,b)
                   
                  设d=gcd(b,a mod b)=>d|b&&d|(a mod b),
                  由A和B知道, d|b&&d|(a mod b)=>d|(xb+y(a mod b)=>d|a(由A，a=qb+(a mod b))
                  由C知道，d|a&&d|b=>d|gcd(a,b)=>gcd(b,a mod b)|gcd(a,b)

             由（1）和（2），可以知道我们得证了。

3.程序模板：
//递归版本
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

//循环版本
int gcd1(int a,int b)
{
  for(int c=a%b;c;a=b,b=c,c=a%b);
  return b;
}

4.学习心得
  
    欧几里得算法是之后很多数论算法的基础，了解它的原理是很有必要的。
    自己要举几个例子来熟悉一下算法的执行过程中的每一步骤，这样才能记忆深刻。
    上述的基础知识也是很有用的，平时注意积累。不懂的地方就几个实例看一下。                        
                    













                 

posted on 2009-09-05 15:48 原语饿狼 阅读(459) 评论(0)  编辑 收藏 引用 所属分类: 数论


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理