《算法分析》教學方法探索

張本群

（興義民族師范學院，興義562400）

0 引言

問題的描述：求n 的歐拉函數，即為小于n 且與n互質的數的個數（包含1）。下面均用Euler（n）來表示n 的歐拉函數。

對于歐拉函數的求解，一種方法是直接講最優算法；另一種方法是通過概念的描述，找出問題的本質，最后才寫出最優算法。解決同一問題，用這兩種不同的方法，在實踐中對學生的接受程度和取得的效果進行分析比較。

1 直接講解最優算法

在往屆的授課時，講歐拉函數的求解時都是直接講最優化的方法，利用歐拉函數的性質：

對于一個正整數n 的素數冪分解n=p1q1×p2q2×p3q3×…×pkqk

主要是求每一個素數因子p1，p2，…，pk，根據上面的公式，就可求出歐拉函數。

時間復雜度為ο(sqrt(n))。具體算法如下：

但用這種方法學生不易理解，計算公式和問題的描述相差甚遠，學生是知其然不知其所以然。對于怎么來的歐拉函數的性質不理解，給出性質后，能寫出算法，但如果不給性質，學生是寫不出算法的，算法沒有寫出來，也就談不上對算法的分析了。于是，在教學過各中調整了教學內容和方法，在這一學期的《算法分析與設計》中，先讓學生理解問題的描述，分析問題的本質，最后再著手寫最優的算法。

2 改進后的教學內容及方法

2.1 先理解概念

先根據問題的描述，理解概念，即直接用概念來解決問題（蠻力法）。

求n 的歐拉函數，就是小于n 且與n 互質的數的個數（包含1）。那么，賦歐拉函數初始值為1，對于小于n 的數i（i 從2 到n-1），逐個判定i 與n 有沒有除1以外的其他因數，如果有，判定下一個，否則歐拉函數加1。

算法對小于n 的數i（i 從2 到n-1），判定i 與n 有沒有除1 以外的其他因數，如果有，跳過這個數，如果沒有，即i 與n 互質，與n 互質的數加1。最后函的的返回什就是歐拉函數的值。這樣寫學生很容易理解，完全根據概念來寫算法，但該算法有很多重復的計算。例如，求Euler（10），已經判定2 是10 的因數了，那么只要是含有因數2 的數，都不會和10 互質。我們再判定4，6，8 是否為10 的因數，就顯然是重復的計算，該算法的時間復雜度為O(n2)。明顯有改進的空間。為了避免如此重復的計算，想到用類似于篩法求素數的方法，用篩法刪去與n 不是互質的數，剩下的就是與n 互質的數了。

2.2 分析問題的本質

根據問題的描述，分析出歐拉函數Euler（n）本質特征。

如果n 是素數，根據素數的概念，n 沒有除1 和它本身以外的其他因數，n 與i（i 從1 到n-1）都是互質的，由此得出性質1。

性質1：如果n 是素數，Euler（n）=n-1；

事實上，對于兩個不同的素數p 和q，有Euler（pq）=Euler（p）×Euler（q）

對于1 到pq 間的數，因為p，q 不相同的素數，它們間的共同因數p 的倍數和q 的倍數，即p，2p，…，（q-1）p，qp 和q，2q，…，（p-1）q，pq。又因為pq 既是p 的倍數，又是q 的倍數，所以Euler（pq）=pq-p-q+1=（p-1）（q-1）=Euler（p）×Euler（q）

推廣得出，對任意兩個互為質數的m，n；均有Euler（mn）=Euler（n）×Euler（m）

證明：由m，n 均為素數可知m，n 無公因數，得出：

Euler（m）Euler（n）=m（1-1/p1）（1-1/p2）（1-1/p3）…（1-1/pk）·n（1-1/q1）（1-1/q2）（1-1/q3）…（1-1/qr），其中p1，p2，p3，…，pk 為m 的質因數，q1，q2，q3，…，qr 為n 的質因數，而m，n 無公因數，所以p1，p2，p3，…，pk，q1，q2，q3，…，qr 互不相同，所以p1，p2，p3，…，pk，q1，q2，q3，…，qr 均為mn 的質因數且為mn質因數的全集，所以Euler（mn）=mn（1-1/p1）（1-1/p2）（1-1/p3）…（1-1/pk）（1-1/q1）（1-1/q2）（1-1/q3）…（1-1/qr），所以Euler（mn）=Euler（m）Euler（n）。

即Euler（mn）=Euler（n）×Euler（m）

如果n 有一個素數因數p1，那么p1 的所有倍數將被岀除，也就是p1 的所有倍數都不會與n 互質，由此可推得下面的性質。

性質2：對于一個正整數n 的素數冪分解n=p1q1×p2q2×p3q3×…×pkqk

根據性質2，刪除掉所有素數因數p1，p2，…，pk 的倍數，所剩的數的個數就是歐拉函數。類似于用篩法求素數的方法，用篩法求與n 互質的數。具體程序如下：

算法的時間復雜度為ο(nsqrt(n))。這一算法相對于根據概念逐個判定的方法有所改進，但仍然有可以再改進的地方。對于n 的每一個素數因數，我們都要遍歷一次它的倍數，把該數換成0，篩選結束后又要遍歷小于n 的每一個數組元素，不為0時才計數。

2.3 分析寫出最優算法

事實上，求n 的歐拉函數只是求與n 與小于n 且與n 互質的個數，并沒有要求求出哪些數與它互質，所以當找出n 的一個素數因數p 時，只需找出包含有因數p1 的數的個數即可，如果p1 是n 的一個素數因數，則有個n/p1 個數與n 有共同因數，故除去p1 的倍數后，還剩n-n/p1 個，以此類推，對于n 的全部互不相同的素數因數p1，p2，…，pk，歐拉函數

此算法在找出素數因數的同時就求出了歐拉函數。如72 的素數因數為2 和3，euler（72）=72×（1-1/2）（1-1/3）=24，最差的情況就是n 為素數時，需要搜索時間為ο(sqrt(n))。此算法的關鍵在于計算res=res/i*（i-1）時刪除了i 的所有倍數，while（a%i==0）a/=i;展轉相除后所得的a 不會包含因數i。

3 比較結果

對于n 的全部互不相同的素數因數p1，p2，…，pk，歐拉函數

這一描述中強調了三個問題，第一是全部，即不能是一部份，因數從2 到n 本身；第二是素數因數，如72＝8×9，不能用來求euler（72），原因是8 和9 雖然是72 的因數，但它們不是素數，故euler（72）＝72（1-1/8）（1-9）＝56 是錯的，是素數不是因數也不行，例如5 是素數，但5 不是72 的因數，因此也不能算；第三是互不相同，如72=2×2×2×3×3，有3 個因數是2，2 個因數3，2和3 均為素數，但2 和3 都只能算一次，而不能算多次，所以在找到一個素數因數p 時，不是進行下一輪的循環，急于找下一個因數，而是輾轉除去所有的因數p，得到的新數n 繼續找素數因數。

如果直接根據性質2 來講解，學生不易理解。通過概念，直接用蠻力求n 的歐拉函數，時間復雜度是ο(n2)，用篩法先將互質因數篩出來，再線性搜索出不為0 的結果，時間復雜度為ο(nsqrt(n))，而用改進后用篩法，找出素數因數的同時就再接算歐拉函數，同時除去所有含該因數的數，時間復雜度是ο(sqrt(n))；時間上得到了很大的提高，所以對同一個問題的求解，由于使用的算法不同，花費的時間完成不一樣。顯然，改進后的算法更有效。通過這一問題的講解，讓學生認識到解決問題前要先分析，找出問題的本質特征，再著手分析寫出算法，寫出更好的算法。這樣逐步優化時間復雜度的教學方法，使學生體會到對算法分析的重要性，學生效果更好。