第十三章學生評優（蠻力算法）內容目標：蠻力算法基本概念學生評優蠻力算法實現數謎問題蠻力算法實現重難點：各種蠻力算法設計思想1.功能描述某班有n個學生，期末要對該班評選出若干先進學生，評選規則如下：1：n個學生站成一排，讓每個人拿起一朵紅花；

2：將編號為2和2的整數倍的學生放下手中的紅花。

3：將編號為3和3的整數倍的學生，手中有紅花的放下紅花，沒有紅花的拿起紅花。....k：將編號為k和k的整數倍的學生，手中有紅花的放下紅花，沒有紅花的拿起紅花。....

依次下去，直到第n次后，手中有紅花的學生評為優秀。2.蠻力算法的基本概念蠻力法是基于計算機運算速度快這一特性，在解決問題時采用的一種“惰性”的策略。這種策略不經過（或者說是經過很少的）思考，把問題的所有情況或所有過程交給計算機去一一嘗試，從中找出問題的解。蠻力策略的應用很廣，具體表現形式各異，數據結構過程中學習的：選擇排序、冒泡排序、插入排序、順序查找等，都是蠻力策略的具體應用。比較常用的枚舉法和窮舉搜索法，本章只講枚舉法。枚舉（Enumerate）法（窮舉法）是蠻力策略的一種表現形式，也是一種非常普遍的思維方式。它是根據問題中的條件將可能的情況一一列舉出來，逐一嘗試從中找出滿足問題條件的解。但有的時候一一枚舉的情況數目很大，如果超出了所能忍受的范圍，則需要進一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的枚舉數目。用枚舉法解決問題，通常可以從兩個方面進行算法設計。找出枚舉范圍：分析問題所涉及的各種情況。找出約束條件：分析問題的解需要滿足的條件，并用邏輯表達式表示。3.1業務實現---學生評優算法設計1：我們可以想到設置n個元素的一維數組a【n】，記錄學生的信息和拿花的狀態，1為拿起，0為放下。用數學運算模擬開關，“對i號學生拿花操作”可以轉化為算術運算a【i】=1-a【i】。由題意，得到每次拿起和放下的學生編號如下：第1次，拿起和放下操作的學生編號為1，2，3，…，n號第2次，拿起和放下操作的學生編號為2，4，6，…號第3次，拿起和放下操作的學生編號為3，6，9，…號……第i次，拿起和放下操作的學生編號為i，2i，3i，…號，它們是起點為i，公差為i的等差數列。數據結構設計：我們用數組元素a【i】（i=1，2，3，…，n）的初值均為1，用蠻力法通過循環模擬學生紅花拿起和放下操作，最后當第i號學生對應的數組元素a【i】為1時，該學生為優秀學生。3.2業務實現---學生評優代碼實現1：publicvoidyn1(){ intn,i,j;//定義局部變量

n=Convert.ToInt16(Console.Read());//輸入囚犯的個數n int[]a=newint[n+1]; for(i=1;i<=n;i++)//為每個囚犯所在的牢房狀態付初值

a[i]=1; for(i=1;i<=n;i++) { for(j=i;j<=n;j=j+i)//執行牢房狀態的操作

a[j]=1-a[j]; } for(i=1;i<=n;i++) if(a[i]==0)//打印牢房打開的信息

Console.WriteLine("第{0}釋放",i);}

3.3業務實現---學生評優算法設計2：轉動門鎖的規則可以有另一種理解，第一次轉動的是編號為1的倍數的牢房，第2次轉動是編號為2的倍數，第3次轉動是編號為3的倍數牢房，…，則獄吏問題是一個因子個數的問題。令d（n）為自然數n的因子個數，這里不記重復的因子，如4的因子為1，2，4共3個因子，而非1，2，2，4.則對于不同的n，d（n）有的為奇數，有的為偶數，具體見下表：

n12345678910111213141516…d（n）1223242434262445…由于牢房開始是關著的，這樣編號為i的牢房，所含1~i之間的不重復因子個數為奇數時牢房最后是打開的，反之牢房最后是關閉的。3.4業務實現---學生評優代碼實現2：publicvoidyn2(){ ints,i,j,n; n=Convert.ToInt16(Console.Read());//輸入囚犯的個數n for(i=1;i<=n;i++)//逐個循環

{ s=1; for(j=2;j<=i;j++)//求每個給定i的因子個數

{ if(i%j==0) s++; } if(s%2==1)//因子個數為奇數打印結果

Console.WriteLine("第{0}釋放",i); }}

3.5業務實現---學生評優算法設計3：仔細觀察上表，不難發現這樣的一個規律，當且僅當n為完全平方數時，d（n）為其數。這是因為非完全平方數n的因子是成對出現的，當a是n的因子時，b=n/a也一定是n的因子。n為非完全平方數，所以a不等于b，因此n的因子必須是成對出現。而當n為完全平方數時，即n=a*a，無論a是否為素數，n的因子a都是單獨出現的，其他因子成對出現，因此d（n）為奇數。3.6業務實現---學生評優代碼實現3：publicvoidyn3(){ ints,i,j,n; n=Convert.ToInt16(Console.Read());//輸入囚犯的個數n for(i=1;i<=n;i++)//逐個循環

if(i*i<=n) //求完全平方數

Console.WriteLine("第{0}釋放",i*i); else break;}

3.7業務實現---學生評優性能比較：算法1： 以一次開關鎖計算，算法的時間復雜度為：

n(1+1/2+1/3+…+1/n)=O(n*logn)

應用數組模擬開關鎖的全過程，主要操作a【i】=1-a【i】；共執行了n*（1+1/2+1/3+…+1/n）次，使用了n個空間的一維數組。算法2：沒有使用輔助空間，主要的操作是i%j是否等于0，共執行了1+2+3+…+n次，時間復雜度為O（n2/2）算法3：非常簡單，只需要找出小于n的平方數即可，時間復雜度為O（n）。4.1知識擴展---數謎問題：問題描述：編寫算法解如下數字謎：

ABC AB * ADDDDDD 4.2知識擴展---數謎問題：問題分析：按乘法進行枚舉1)枚舉的范圍

A：3~9（A=1，2時積不會得到六位數），B：0~9，C：0~9，6位數表示為A*10000+B*1000+C*100+A*10+B，共嘗試700次，枚舉出700個可能的5位數。2）約束條件每次嘗試，先求枚舉出5位數與A的積，再測試積的各位是否相同，若相同則找到了問題的解。測試積的各位是否相同，比較簡單的方法是：從地位開始，每次都取數據的個位，然后整除10，使高位數字不斷變為個位，并逐一比較。4.3知識擴展---數謎問題：代碼實現：publicvoidshuxi(){intA,B,C,D,i; //定義局部變量longE,E1,F,G1,G2;for(A=3;A<=9;A++)//A從3到9循環{for(B=0;B<=9;B++)//B從0到9循環{for(C=0;C<=9;C++)//C從0到9循環 { F=A*10000+B*1000+C*100+A*10+B;//獲得5位數

E=F*A; //5位數乘以A E1=E; G1=E1%10; //取各位數G1 for(i=1;i<=5;i++)