算法設(shè)計：第八講.ppt

【例題7】游戲問題： 12個小朋友手拉手站成一個圓圈，從某一個小朋友開始報數(shù)，報到7的那個小朋友退到圈外，然后他的下一位重新報“1”。這樣繼續(xù)下去，直到最后只剩下一個小朋友，求解這個小朋友原來站在什么位置上呢？,3.2.3 數(shù)組記錄狀態(tài)信息,在個人計算機中，對超過長整型的多位數(shù)操作時，只能借助于數(shù)組才能精確存儲及計算。 （1）使用字符數(shù)組存儲輸入的高精度數(shù)，每個數(shù)組元素對應(yīng)一個數(shù)字。 【例題8】高精度數(shù)據(jù)*長整數(shù),3.2.4 大整數(shù)存儲及運算,（2）使用數(shù)組存儲輸出的高精度數(shù)，每個數(shù)組元素存儲多位數(shù)字。 【例題9】編程求N！的準確值。N=100（每個數(shù)組元素存儲6位數(shù)字） （1）存儲結(jié)果需要的數(shù)組長度 事先估計（長度=log(n)*n/6+2) 邊計算邊統(tǒng)計 （2）結(jié)果的輸出,3.2.4 大整數(shù)存儲及運算,矩陣：用二維數(shù)組存儲 問題：趣味矩陣中字符或數(shù)據(jù)的規(guī)律很容易發(fā)現(xiàn)，但是按規(guī)律直接輸出卻不容易。 解決方法：設(shè)計算法將數(shù)據(jù)先存儲到二維數(shù)組中，最后輸出二維數(shù)組的內(nèi)容。,3.2.5 構(gòu)造趣味矩陣,3.2.5 構(gòu)造趣味矩陣,3）用i代表行下標，以j代表列下標，則對n*n矩陣有以下常識： 主對角線元素i= =j； 副對角線元素: 下標下界為1時 i+j= =n+1， 下標下界為0時i+j= =n-1； 主上三角元素: i =j； 次上三角元素：下標下界為1時i +j=n+1， 下標下界為0時i+j=n-1；,【例題10】編程打印有如下規(guī)律的n*n方陣,3.2.4 大整數(shù)存儲及運算,【例題11】螺旋陣：任意給定的n值，按如下螺旋的方式輸出方陣,3.2.4 大整數(shù)存儲及運算,3.2.5 構(gòu)造趣味矩陣,【算法設(shè)計1】：四角元素分別歸四個邊 （1）此例可以按照“擺放”數(shù)據(jù)的過程，逐圈分別處理每圈的左側(cè)、下方、右側(cè)、上方的數(shù)據(jù)。 圈數(shù)：(n+1)/2 第i圈的處理過程： for( j=i;j=i+1;j=j-1) ajn+1-i=k;k=k+1; /右側(cè)/ for( j= n-i+1;j=i+1;j=j-1) aij=k; k=k+1; /上方/,3.2.5 構(gòu)造趣味矩陣,【算法設(shè)計2】：通過算術(shù)運算將4個方位的處理歸結(jié)為一個循環(huán)完成，約定四角數(shù)據(jù)分別屬于先處理的行或列。 一圈的情況為：,3.2.5 構(gòu)造趣味矩陣,/n代表矩陣的規(guī)模，x代表填入的數(shù)據(jù) int a100100; k=n; t=1; while(x=n*n) for(y=1;y=2*k-1;y+)/半圈 if(y=k)i+=t; else j+=t; aij=x; x+; t=-t; k-; ,int b2;/b0代表i，b1代表j,by/(k+1)+=t; ab0b1=x;,【例題12】打印魔方陣（奇數(shù)魔方陣）,3.2.4 大整數(shù)存儲及運算,3.2.5 構(gòu)造趣味矩陣,【算法設(shè)計】規(guī)則描述如下： （1）首先將1填在方陣第一行的中間。 （2）下一個數(shù)填在上一個數(shù)的主對角線的上方，即若上一個數(shù)的位置是（i,j），下一個數(shù)應(yīng)填在（i-1,j-1）。 （3）若應(yīng)填寫的位置下標出界，則出界的值用n 來替代； （4）若應(yīng)填的位置雖然沒有出界，但是已經(jīng)填有數(shù)據(jù)的話，則應(yīng)填在上一個數(shù)的下面（行加1，列不變），即取i1=i+1，j1=j。 直到把n*n個數(shù)全部填入方陣中。,3.2.5 構(gòu)造趣味矩陣,Input(n); while(n%2=0)printf(“error!”,input(n); i=1; j=(n+1)/2; x=1; While(x=n*n) aij=x; m=i; n=j; i-;j-; if(i=0)i=n; if(j=0)j=n; if(aij!=0)i=m+1;j=n; ,3.2.6 一維與二維的選擇,在有些應(yīng)用中，原始數(shù)據(jù)表面上看是一維信息，但使用二維數(shù)組存儲有關(guān)信息后，更容易設(shè)計算法。 【例題13】統(tǒng)計問題：找出鏈環(huán)數(shù)字對的出現(xiàn)的次數(shù) 輸入n（2n100）個數(shù)字（即09之間的數(shù)據(jù)），然后統(tǒng)計出這組數(shù)中相鄰兩數(shù)字組成的鏈環(huán)數(shù)字對出現(xiàn)的次數(shù)。 例如： 輸入：n=20 0 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9 輸出：（7,8)=2 (8,7)=3 (7,2)=1 (2,7)=1 (2,2）=2 (2,3)=1 (3,2)=1,3.2.6 一維與二維的選擇,實現(xiàn) （1）使用一維數(shù)組存儲計數(shù)： 將相鄰的兩個數(shù)轉(zhuǎn)換成一維數(shù)組的下標：x=m*10+j;ax+ 將一維數(shù)組下標轉(zhuǎn)換成對應(yīng)的數(shù)對： m=i/10 n=i%10 if(m*10+n)!=0 &(n*10+m)!=0 （2）使用二維數(shù)組存儲計數(shù)： am,n+,3.2.6 一維與二維的選擇,【例題14】有3n個花盆，紅、黃、藍各有n個。開始排列的順序是混亂的。請編寫一程序?qū)⒏骰ㄅ璋凑占t、黃、藍的順序排列。要求各花盆之間的交換次數(shù)最少 本例題屬于約定排序的問題：目標是 將紅送到3i-2的位置 將黃送到3i-1的位置 將藍送到3i的位置 使用二維數(shù)組：一列是一種顏色(紅、黃、藍）,3.2.6 一維與二維的選擇,為保證交換次數(shù)最少： 第一列的黃與第二列的紅交換 第一列的藍與第三列的紅交換 第二列的藍與第三列的紅交換 第一列的黃、第二列的藍、第三列的紅循環(huán)交換 第一列的藍、第二列的紅、第三列的黃循環(huán)交換,3.3 優(yōu)化算法的基本技巧,算術(shù)運算的妙用：通過恰當?shù)乃阈g(shù)運算可以很好地提高編程效率，以及相關(guān)算法的編程效率。 【例題15】一次考試，共考了五門課。統(tǒng)計五十個學(xué)生中至 少有三門課成績高于90分的人數(shù)。 算法設(shè)計： 1）對每個同學(xué)，先計算其成績高于90分的課程數(shù)目，若超過3，則累加滿足條件的人數(shù)中。 2）用二重循環(huán)實現(xiàn)以上過程，外層循環(huán)模擬50個同學(xué)，內(nèi)層循環(huán)模擬5門課程,3.3 優(yōu)化算法的基本技巧,【例題16】開燈問題：有從1到n依次編號的n個同學(xué)和n 盞燈。1號同學(xué)將所有的燈都關(guān)掉；2號同學(xué)將編號為2的倍數(shù)的燈都打開；3號同學(xué)則將編號為3的倍數(shù)的燈作相反處理（該號燈如打開的，則關(guān)掉；如關(guān)閉的，則打開）；以后的同學(xué)都將自己編號的倍數(shù)的燈，作相反處理。問經(jīng)n個同學(xué)操作后，哪些燈是打開的？,3.3 優(yōu)化算法的基本技巧,問題分析： 1）用數(shù)組表示某種狀態(tài)，這里定義有n個元素的數(shù)組a ，它 的每個下標變量ai視為一燈，i表示其編號。ai=1 表示燈處于打開狀態(tài)，ai=0表示燈處于關(guān)閉狀態(tài)。 2）實現(xiàn)將第i 燈作相反處理的操作，可以用條件語句if表 示：if(ai=1) ai=0； else ai=1; 但通過以下算術(shù)運算:ai=1-ai;就很好地模擬“開關(guān)”燈的操作。,3.3 優(yōu)化算法的基本技巧,【例題17】右圖中所示的圓圈中，我們把相隔一個數(shù)據(jù)的兩個數(shù)（如1和10，3和5，3和6）稱作是“一對數(shù)”，試編程求出乘積最大的一對數(shù)和乘積最小的一對數(shù)。輸出格式如下： max=?*?=? min=?*?=?,3.3 優(yōu)化算法的基本技巧,標志量的妙用：使用標志量表示不同情況或狀態(tài)。 【例題18】冒泡排序算法的改進。 【例題20】輸入3個數(shù)值，判斷以它們?yōu)檫呴L是否能構(gòu)成三角形。若能構(gòu)成三角形，請指出是那種三角形。 【例題21】編寫算法，求任意三個數(shù)的最小公倍數(shù),3.3 優(yōu)化算法的基本技巧,信息數(shù)字化：本節(jié)就一些表面上看是非數(shù)值，但經(jīng)過數(shù)字化后，就可方便進行算法設(shè)計。 【例題22】警察局抓了a，b，c，d四名偷竊嫌疑犯，其中只有一人是小偷。審問中 a說：“我不是小偷?！?b說：“c是小偷?！?c說：“小偷肯定是d?！?d說：“c在冤枉人?！?現(xiàn)在已經(jīng)知道四個人中三人說的是真話，一人說的是假