• 人脑走一遍欧几里得算法

    从欧几里得算法开始
    服务器君一共花费 12.959 ms 进行了 4 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    算法是贯穿在所有计算机程序设计中的一个基本概念,前面一小节也提到了改变人类进程的重要算法,所以我们要理解算法这一概念。

    1950年左右,algorithm一词经常地同欧几里德算法(Euclid's algorithm)联系在一起。这个算法就是在欧几里德的《几何原本》(Euclid's Elements ,第VII卷,命题i和ii)中所阐述的求两个数的最大公约数的过程(即辗转相除法),而在中国则可以追溯至东汉出现的《九章算术》。这里就开始谈一下欧几里得算法,并且试图以别的方式去理解算法的推导。

    先来看这么一个问题:求两个整数a,b的最大公约数。或者,具体一点,就10和15的最大公约数。

    一看就是5啦,那么为啥我们会如此之快地知道它们的最大公约数是5呢?因为 2*5=10, 3*5=15, 所以一眼就锁定5了。那么从这个计算过程,我们能不能推导出更加适用的算法?

    假设a=10, b=15,那么我们现在求的是 gcd(10,15)。

    假设 d=5 是 a 和 b 的一个公约数(明知故设……),那么是不是 a % d == 0 (就是 10 % 5 == 0 了),同时 b 对 d 取模也是 0,就是 b % d == 0 (15 % 5 == 0),

    我们建立一下 a 和 b 之间的联系,比如模运算关系为:a = kb + r (10 = 0 * 15 + 10),那么 r = a % b (10 = 10 % 15)。这个 r 就是这个算法的关键,欧几里德算法为何又叫辗转相除法呢?

    r = a - kb (10 = 10 - 0 × 15),既然 a % d == 0,b % d == 0,就是说,a 能整除 d,b 也能整除 d,那么 a - kb 是不是可以理解成 x*d - k*y*d (x,y是随意整数),那么很明显了 r = (x - ky)d, 就是说,r 也能整除 d,就是 r % d == 0。

    问题得以转化,求gcd(a,b),可以转化为求gcd(b,a mod b)。就是求gcd(10,15),可以用求gcd(15,10)来替代。

    那么gcd(15,10)又可以用什么来代替呢?我们来看下 r,这个时候 r = a % b = 15 % 10 = 1*10 + 5 = 5,所以根据 gcd(b,a mod b),gcd(15,10) 可以用gcd(10,5)来替代,再替代一下,就是gcd(10,5)可以用gcd(5,5)来替代,问题答案出来了,5和5公约数是多少?就是5了。这里辗转相除了3次。

    这里是用人脑粗暴地走了一下算法的步骤。具体欧几里得如何发现这个算法,一开始我是打算把这个算法定理的推导过程走一次的,结果走了证明这条路。

    也就是说,(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等。欧几里德算法就是根据这个原理来做的。

    下面用程序验证一下吧:

    #include <stdio.h>
    
    int gcd(int a, int b)
    {
        if (b == 0) {
            return a;
        } else {
            printf("a=%d, b=%d, a mod b=%d\n", a, b, a%b);
            return gcd(b, a % b);
        }
    }
    
    int main(void)
    {
        int intA, intB;
    
        printf("Enter two number to calculate its GCD:\n");
        scanf("%d %d", &intA, &intB);
        printf("The GCD of %d and %d is %d\n", intA, intB, gcd(intA, intB));
    
        return 0;
    }
    

    程序输出:

    Enter two number to calculate its GCD:
    10
    15
    a=10, b=15, a mod b=10
    a=15, b=10, a mod b=5
    a=10, b=5, a mod b=0
    The GCD of 10 and 15 is 5
    
    Process returned 0 (0x0)   execution time : 2.503 s
    Press any key to continue.
    

    努力去理解与验证一个算法,还是挺有意思的。当然,我们最好还是尽量想办法自己去推导算法,这个过程对大脑思维的训练很有用。

    in little things, and thence proceed to greater.

    先从小事做起吧,而后才能做更大的事。

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [移动开发] Android布局中的一些常用控件 2 个条目
  2. [移动开发] Android SQLite增删查改实例(数据:魔弹之王) 2 个条目
  3. [C语言程序设计] C语言里的全局变量 2 个条目
  4. [PHP程序设计] httpd.conf设置相关 3 个条目
  5. [移动开发] 简单了解Android Fragment 3 个条目
  6. [移动开发] ListView 使用相关问题集 1 个条目
  7. [PHP程序设计] 对输入文件类型的检测 1 个条目
  8. [软件工程与项目管理] 浏览器的HTML解析器 8 个条目
  9. [智力开发与知识管理] 整体性学习步骤 9 个条目
  10. [JavaScript程序设计] jQuery与表单操作 2 个条目
  11. [Linux操作系统] 基本 Linux Shell 命令 2 个条目
  12. [Python程序设计] Python HTTP服务器 7 个条目
窗口 -- [资讯]