第十章班長評選（循環算法）內容目標：循環算法的基本概念。循環算法的設計要點班長評選循環算法案例分析具體到抽象循環算法案例分析用單向鏈表實現循環算法案例分析重難點：循環算法設計思想以及應用1.功能描述2.循環算法的基本概念基本概念 事實上，在一般情況下只有處理大量數據才借助于計算機，所以算法設計中很重要的工作就是對數據的處理歸結成較規范的可重復的“機械化的操作”交給計算機去完成。即將重復處理大量數據的步驟抽象成“循環”或“遞歸”的模式，設計出可以針對不同規模解決問題的方法。不同于機器生產產品的“機械化的操作”，計算機進行數據處理不可能是完全相同的重復。所以必須要設計出表現形式不變，但能實現動態處理數據的“機械化的操作”。也就是說，在重復操作中，“循環條件”、:“循環體”都必須是“不變式”，而數據處理對象卻是變化的，算法是在漸進地完成處理數據的操作。算法設計中，一個重要的工作就是從已建立好的數學模型中，構造出“不變式”的“循環條件”、“循環體”?！安蛔兪健敝饕且揽孔兞炕驍到M元素表示的，因為變量名或數組元素是“不變”的，而變量或數組元素中的數據是不斷變化的，從而數據處理是動態的、漸進的。3.1.1業務實現---班長評選算法設計：將所有的學生信息放入到順序表中，并進行編號標識，編號標識順序為1，2，3，…，n，當報號到r時，作淘汰操作，將對應的學生編號標識改為-1，如此下去當剩下一個時，即為所要評選的班長，最后輸出編號標志不為-1的學生信息即是班長。數據結構設計：用一維數組的順序表來保存學生的信息和編號標識。3.1.2業務實現---班長評選定義學生信息順序表結點類：用以記錄學生的信息和學生在順序表中的編號，具體實現如下：publicclassnode{//學生信息順序表結點類

publicStudent_infoData; //學生信息對象

publicintflag; //學生編號用以記錄是否淘汰的標準，若為-1表示已經淘汰

publicnode() { }}

3.1.3業務實現---班長評選定義學生信息順序表結點類：用以記錄學生的信息和學生在順序表中的編號，具體實現如下：publicclassbanzhang{ public LinkL;//實現班長評選算法的鏈表對象

publicStudentMangerBa=newStudentManger();//創建數據控制層對象

publicnode[]tp;//實現班長評選算法的順序表對象

publicbanzhang() { } publicintLink_Init(intn)//單向循環鏈表的初始化

publicStudent_infoLink_select(intn,intr){…}//用單向循環鏈表實現班長評選算法

publicintsx_Init(intn){…}//順序表的初始化

publicStudent_infosx_select(intn,intr){…}//用順序表實現班長評選算法

}

3.1.4業務實現---班長評選為學生信息順序表的初始化：根據所傳入的學生總人數，進行學生信息順序表的初始化，實現的步驟如下：判斷所傳入的學生總人數是否超出數據庫中總學生數，若是返回0。為學生信息順序表分配足夠的內存空間。逐個為學生信息順序表每個成員進行初始化。初始化完畢返回1。 publicintsx_Init(intn) {//初始化順序表，輸入總的學生人數

if(n>Ba.Max)return0; tp=newnode[n]; for(inti=0;i<n;i++)//為順序表每個學生信息進行初始化

{ tp[i]=newnode(); tp[i].Data=Ba.base_info[i]; tp[i].flag=i+1; } return1; }

3.1.5業務實現---班長評選用以實現對給定的學生總人數n和所要淘汰號r，進行班長評選的設計，在這里采用“自頂向下”的方法來設計：首先：將算法分為三部分，即：學生信息初始化、學生信息淘汰、班長信息顯示。其次：學生信息初始化包括：學生信息順序表初始化，局部變量初始化（包括：記錄學生報數變量，記錄學生淘汰人數變量，記錄所訪問的學生編號變量）。學生信息淘汰，確定循環算法結束條件，進行信息淘汰，步驟如下：學生依次報數，實現報數變量自加。判斷報數號是否與淘汰號r相等，若相等，實現淘汰操作處理，否則繼續報數。判斷學生報數是否一圈走完，若是從頭開始，否則繼續。班長信息顯示：在順序表中，逐個判斷，尋找未淘汰的的學生信息，進行返回。 最后，對各個步驟進行細化，進行算法實現，代碼如下：3.1.5業務實現---班長評選publicStudent_infosx_select(intn,intr){//應用順序表實現班長評選

if(sx_Init(n)==0)//初始化順序表

returnnull; inti,Out,count; i=0; Out=0;//記錄淘汰的學生人數

count=0;//記錄學生報數的

while(Out<n-1) { if(tp[i].flag!=-1)//該學生為淘汰，報數加1 { count++; } if(count==r)//報數為r，淘汰學生數加1，報數從0開發

{tp[i].flag=-1; count=0;Out++; } i++; if(i==n)//當一輪走完后，回到第一個學生位置

i=0; } for(i=0;i<n;i++)//返回最后的評選結果

{if(tp[i].flag>-1) returntp[i].Data; } returnnull;}

3.1.6業務實現---班長評選用單向循環鏈表實現班長評選：算法設計：應用單向循環鏈表的思想，進行班長的評選，首先將所有學生添加到單向循環鏈表中，通過鏈表指針的移動，實現結點的刪除（即進行淘汰操作），當循環鏈表中只有一個元素時，即得到問題的解。數據結構設計：應用不帶頭指針的單向循環鏈表保存學生信息，通過指針移動實現淘汰元素的刪除。3.1.7業務實現---班長評選學生單向循環鏈表結點類

publicclassLink {//學生信息鏈表結點

publicStudent_infoData;//學生信息對象

publicLinknext; //指向下一個學生信息對象

publicLink() { } }

3.1.8業務實現---班長評選學生信息循環鏈表的初始化：根據所傳入的學生總人數，實現單向循環鏈表的初始化，實現的步驟如下：根據所傳入的學生總人數n與數據庫中學生總數進行比較，若大返回0。初始化單向循環鏈表對象L和局部結點對象s。逐個取出數據庫中學生信息，添加到鏈表中。在添加第一個學生信息時，添加到首結點的數據域中，并記錄該結點對象s。添加其他學生信息結點時，依次添加到首結點前面。最后將第一次添加對象s的指針域指向首結點。。3.1.9業務實現---班長評選publicintLink_Init(intn){//單向循環鏈表初始化，輸入要創建的n個結點

if(n>Ba.Max)return0; inti;L=newLink();L.next=L;//初始化不帶頭指針的循環鏈表

Links=newLink(); for(i=n-1;i>=0;i--) {Student_infotemp=Ba.base_info[i]; Linkp=newLink(); if(i==n-1)//初始化第一個結點的數據域

{ L.Data=temp; s=L;//s指向尾結點 } else//初始化其他結點的數據域和指針域

{ p.Data=temp; p.next=L; L=p; } } s.next=L;//尾結點指針域指向頭結點

return1;}

3.1.10業務實現---班長評選用循環鏈表實現班長評選：用以實現對給定的學生總人數n和所要淘汰號r，進行班長評選的設計，在這里采用“自頂向下”的方法的循環鏈表設計如下：首先：將算法分為三部分，即：學生信息初始化、移動指針淘汰學生、班長信息返回。其次：學生信息初始化包括：循環鏈表初始化、局部對象初始化移動指針實現學生信息的淘汰：循環終止條件：循環鏈表只剩一個學生即：test.next!=test。循環體：鏈表指針的移動r次，實現鏈表中淘汰學生結點刪除。最后：實現班長信息的返回。3.1.11業務實現---班長評選publicStudent_infoLink_select(intn,intr){//用循環鏈表實現班長評選

if(Link_Init(n)==0)//初始化循環鏈表

returnnull; Linklast,test;//局部結點對象

Student_infotemp; inti; test=L; last=L; while(test.next!=test) { for(i=1;i<r;i++)//在循環鏈表中，結點指針移動

{ last=test; test=test.next; } last.next=test.next;//在循環實現學生信息刪除

test=last.next; } temp=test.Data; returntemp; }

4.1.1知識擴展：長整數問題設計方法介紹：自頂向下的設計方法是從全局走向局部、從策略走向詳盡的設計方法。自頂向下是系統分解和細化的過程。首先，根據題意，總體規劃設計算法的主要組成或步驟。其次，分別對各個步驟進行分解，理清各個子步驟的算法框架。最后，繼續為各個子步驟算法進行細化，直至算法實現。4.1.1知識擴展：長整數問題

問題描述：.給定1個正整數n（n<35），求n!的精確值。問題分析：由于34！的位數已經是40位了，在個人計算機中，沒有任何一種標準的數據類型能夠準確記錄這樣大的數。我們可以考慮用一個大小為40的一維整數數組，分別記錄其各位的值。在輸出時，按高位到低位進行輸出。在每次n*(n-1)!時，用n乘以數組的每個元素，然后對數組的每個元素進行是否進位的檢查，若第k元素大于9，將其十位上的數字加到第k+1元素上去，其個位仍然保留。4.1.2知識擴展：長整數問題實現步驟：現采用“自頂向下”的設計方法解決該問題的具體步驟如下：首先：從總體上該問題可分為如下幾個部分：數組定義和初始化；n！階乘的實現；n！階乘的顯示。其次：將各個組成部分的算法進行細化，設計出各個子步驟的算法框架:數組定義和初始化；數組的定義和初始化算法所用的變量的確定和初始化n！階乘的實現；實現n*（n-1）!的算法進行數組元素進位判斷，實現進位操作。、n！階乘的顯示。從高位到低位輸出數組進行高位是否為0的判斷，若為0，不進行輸出，否則其后的各位都應進行輸出。最后，對各個子步驟進行算法細化，進行算法實現。4.1.3知識擴展：長整數問題4.1.4知識擴展：長整數問題代碼實現：publicvoidjc(intn)//任意輸入n，n<=34{int[]a=newint[40];//初始化一維數組

a[0]=1;inti,j,k; //定義算法中的循環變量

boolflag=false;//定義數組元素是否該打印標志，開始為不用打印

for(i=2;i<=n;i++)//實現n的階乘

{for(j=0;j<40;j++)//為數組每一元素都乘以某一值j { a[j]=a[j]*i; } for(k=0;k<40;k++)//檢查數組每一元素是否超過10 {if(a[k]>9)//進行進位操作

{a[k+1]=a[k+1]+a[k]/10;//將k元素的高位進位到k+1元素上

a[k]=a[k]%10; //保留第k元素的個位

}}}Console.Write("{0}!=",n); for(k=39;k>=0;k--)//進行階乘打印

{if(flag==true||a[k]!=0)//高位不為0進行打印

{Console.Write("{0}",a[k]); flag=true; } }}

4.2.1知識擴展：具體到抽象案例分析從具體到抽象的設計步驟：從給定的問題的具體特點為依據進行算法設計，循環變量的定義不是固定不變的。其范圍及引用等細節，由具體實例進行歸納，可以比較容易地得到抽象的表達式。具體的設計步驟如下：首先：仔細了解問題的含義，從具體的問題中，歸納或抽象出具有普遍意義的共同特征。其次：根據歸納得到的共同特征，設計算法，構造出“不變式”的“循環條件”和“循環體”。最后：將問題進一步進行逐步細化，最終得到解決問題的算法。4.2.2知識擴展：具體到抽象案例分析問題描述： 問題：編寫算法：打印具有下面規律的圖形

152863109744.2.3知識擴展：具體到抽象案例分析問題分析和設計：問題分析：無論從題意理解，還是從算法的通用性來考慮，算法設計不能只針對圖中的4*4的二維數組進行。下面以任意階的二維數組n*n討論。為分析方便，數組的起始下標為1。 算法設計：對二維表的操作一般按列或行進行的，但此圖形中數據的排列方法卻不是按行、列進行的。二維表是否只能按行、列的順序進行操作呢？回答是否定的，下面根據排列的特點，按“層”對數據進行處理。容易發現圖形中自然數在矩陣中的排列規律，題目中1，2，3，4所在的位置稱為第1層（主對角線），例圖中5，6，7所在位置稱為第2層，…。一般地，第一層有n個元素，第2層有n-1個元素…。4.2.4知識擴展：具體到抽象案例分析問題分析和設計：基于以上數據變化的規律，以層號作為外層循環，循環變量為i（范圍為1~n）；以層內元素從上到下的序號作為內循環，循環變量為j（范圍為1~n+1-i）。這樣循環的執行過程正好與“擺放”自然自然數的順序相同。用一個變量k模擬要“擺放”的數據，下面的問題就是怎樣將數據存儲到對應的數組元素。數組元素的存取，只能按行、列號操作的。所以下面用由具體到抽象設計循環的“歸納法”，找出數組元素的行號