用Python实现常见算法 -- qingfeng (2009-04-21)

求最大公约数

欧几里得算法

分析：求最大公约数的算法思想：
(1) 对于已知两数m，n，使得m>n； 
(2) m除以n得余数r； 
(3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； 
(4) m←n，n←r，再重复执行(2)。 
例如: 求 m=14 ,n=6 的最大公约数. m n r 

代码:

   1 def f(m,n):
   2     m,n=max(m,n),min(m,n)
   3     if n==0:return m
   4     return f(n,m%n)
   5 f(14,6)

Stein算法

欧几里德算法是计算两个数最大公约数的传统算法，无论是理论，还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在很大的素数时才会显现出来。
考虑现在的硬件平台，一般整数最多也就是64位， 对于这样的整数，计算两个数值就的模很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。
Stein算法由J.Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。
为了说明Stein算法的正确性，首先必须注意到以下结论：
  gcd(a, a) = a， 也就是一个数和他自己的公约数是其自身。
  gcd(ka, kb) = k * gcd(a, b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数比如能被2整除。

代码:

   1 def f(a, b):    
   2     a,b = max(a,b),min(a,b)
   3     if (b == 0):
   4         return a
   5     if a % 2 == 0 and b % 2 == 0:
   6         return 2 * f(a/2, b/2)
   7     if a % 2 == 0:
   8         return f(a / 2, b)
   9     if b % 2 == 0:
  10         return f(a, b / 2)
  11     
  12     return f((a + b) / 2, (a - b) / 2) 

快速排序1

说明

快速排序法（quick sort）是目前所公認最快的排序方法之一（視解題的對象而定），雖然快速排序法在最差狀況下可以達O(n2)，但是在多數的情況下，快速排序法的效率表現是相當不錯的。

快速排序法的基本精神是在數列中找出適當的軸心，然後將數列一分為二，分別對左邊與右邊數列進行排序，而影響快速排序法效率的正是軸心的選擇。

這邊所介紹的第一個快速排序法版本，是在多數的教科書上所提及的版本，因為它最容易理解，也最符合軸心分割與左右進行排序的概念，適合對初學者進行講解。

解法

這邊所介紹的快速演算如下：
將最左邊的數設定為軸，並記錄其值為 s

廻圈處理：
令索引 i 從數列左方往右方找，直到找到大於 s 的數
令索引 j 從數列左右方往左方找，直到找到小於 s 的數
如果 i >= j，則離開迴圈
如果 i < j，則交換索引i與j兩處的值
將左側的軸與 j 進行交換
對軸左邊進行遞迴
對軸右邊進行遞迴

透過以下演算法，則軸左邊的值都會小於s，軸右邊的值都會大於s，如此再對軸左右兩邊進行遞迴，就可以對完成排序的目的，例如下面的實例，*表示要交換的數，[]表示軸：
[41]　24　76*　11　45　64　21　69　19　36*
[41]　24　36　11　45*　64　21　69　19*　76
[41]　24　36　11　19　64*　21*　69　45　76
[41]　24　36　11　19　21　64　69　45　76
21　24　36　11　19　[41]　64　69　45　76

在上面的例子中，41左邊的值都比它小，而右邊的值都比它大，如此左右再進行遞迴至排序完成。 

实战

   1