基礎(chǔ)算法教案

基礎(chǔ)算法教案 目錄第一課 算法簡介 .1第二課 多精 度數(shù)值處理 .1第三課 排列與 組合 .6第四課 枚 舉法 .9第五課 遞歸與回 溯法 .25第六課 遞 推法 .42第七課 貪心法 .50第八課 分 治法 .64第九課 模 擬法 .70習(xí) 題 .79第一課 算法簡介算法是一組（有限個）規(guī)則，它為某個特定問題提供了解決問題的運算序列。在信息學(xué)競賽中，就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫算法，都是在實施某種算法。前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法。計算機解題的核心是算法設(shè)計。一個算法應(yīng)該具有以下五個重要特征： 有窮性：一個算法必須能在執(zhí)行有限步之后結(jié)束； 確切性：算法的每一步驟必須確切定義； 輸入：一個算法有零個或多個輸入，以描述運算對象的初始情況。所謂 0 個輸入是指算法本身給出了初始條件； 輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)處理后的結(jié)果。沒有輸出的算法是毫無意義的； 可行性：算法原則上能夠精確的運行，而且其運算規(guī)模是可以承受的。為了獲得一個既有效又優(yōu)美的算法，必須首先了解一些基本的常用算法設(shè)計思路。下面，我們就對構(gòu)成算法所依據(jù)的一些基本方法展開討論，如遞推法，遞歸法，枚舉法，分治法，模擬法，貪心法等。第二課 多精度數(shù)值處理課題：多精度數(shù)值的處理目標：知識目標：多精度值的加、減、乘、除能力目標：多精度值的處理，優(yōu)化！重點：多精度的加、減、乘難點：進位與借位處理板書示意：1） 輸入兩個正整數(shù)，求它們的和2） 輸入兩個正整數(shù)，求它們的差3） 輸入兩個正整數(shù)，求它們的積4） 輸入兩個正整數(shù)，求它們的商授課過程：所謂多精度值處理，就是在對給定的數(shù)據(jù)范圍，用語言本身提供的數(shù)據(jù)類型無法直接進行處理（主要指加減乘除運算） ，而需要采用特殊的處理辦法進行?？纯聪旅娴睦?。例 1 從鍵盤讀入兩個正整數(shù)，求它們的和。分析：從鍵盤讀入兩個數(shù)到兩個變量中，然后用賦值語句求它們的和，輸出。但是，我們知道，在 pascal 語言中任何數(shù)據(jù)類型都有一定的表示范圍。而當(dāng)兩個被加數(shù)據(jù)大時，上述算法顯然不能求出精確解，因此我們需要尋求另外一種方法。在讀小學(xué)時，我們做加法都采用豎式方法，如圖 1。這樣，我們方便寫出兩個整數(shù)相加的算法。如果我們用數(shù)組 A、B 分別存儲加數(shù)和被加數(shù)，用數(shù)組 C 存儲結(jié)果。則上例有A1=6, A2=5, A3=8, B1=5,B2=5, B3=2, C4=1,C3=1, C2=1,C1=1,兩數(shù)相加如圖 2 所示。由上圖可以看出：Ci:= Ai+Bi;if Ci10 then begin Ci:= Ci mod 10; Ci+1:= Ci+1+1 end;因此，算法描述如下：procedure add(a,b;var c); a,b,c 都為數(shù)組，a 存儲被加數(shù)，b 存儲加數(shù)，c 存儲結(jié)果 var i,x:integer;begini:=1while (i0) or(i=10 then 處理最高進位begin lenc:=i;ci:=1 end else lenc:=i-1;for i:=lenc downto 1 do write(ci); 輸出結(jié)果writelnend.例 2 高精度減法。從鍵盤讀入兩個正整數(shù)，求它們的差。分析：類似加法，可以用豎式求減法。在做減法運算時，需要注意的是：被減數(shù)必須比減數(shù)大，同時需要處理借位。因此，可以寫出如下關(guān)系式if ai1) do dec(lenc); 最高位的 0 不輸出for i:=lenc downto 1 do write(ci);writelnend.例 3 高精度乘法。從鍵盤讀入兩個正整數(shù)，求它們的積。分析：類似加法，可以用豎式求乘法。在做乘法運算時，同樣也有進位，同時對每一位進乘法運算時，必須進行錯位相加，如圖 3, 圖 4。分析 C 數(shù)組下標的變化規(guī)律，可以寫出如下關(guān)系式C i = C i +C ”i +由此可見，C i跟 Ai*Bj乘積有關(guān)，跟上次的進位有關(guān)，還跟原 C i的值有關(guān)，分析下標規(guī)律，有x:= Ai*Bj+ x DIV 10+ Ci+j-1;Ci+j-1 := x mod 10; 類似，高精度乘法的參考程序：program exam3;constmax=200;vara,b,c:array1.max of 0.9;n1,n2:string;lena,lenb,lenc,i,j,x:integer;8 5 6 2 5 4 2 8 01 7 1 2 2 1 4 0 0圖 3A 3 A 2 A 1 B 3 B 2 B 1 C4C3 C2 C1 C”5C”4C”3C”2 C 6 C 5 C 4 C 3 C 2 C 1圖 4beginwrite(Input multiplier:); readln(n1);write(Input multiplicand:); readln(n2);lena:=length(n1); lenb:=length(n2);for i:=1 to lena do alena-i+1:=ord(n1i)-ord(0);for i:=1 to lenb do blenb-i+1:=ord(n2i)-ord(0);for i:=1 to lena do begin x:=0; for j:=1 to lenb do begin 對乘數(shù)的每一位進行處理x := ai*bj + x div 10 + ci+j-1; 當(dāng)前乘積+上次乘積進位+原數(shù) ci+j-1 := x mod 10;end;ci+j:= x div 10; 進位end;lenc:=i+j;while (clenc=0) and (lenc1) do dec(lenc);for i:=lenc downto 1 do write(ci);writelnend.例 高精度除法。從鍵盤讀入兩個正整數(shù)，求它們的商（做整除） 。分析：做除法時，每一次上商的值都在，每次求得的余數(shù)連接以后的若干位得到新的被除數(shù)，繼續(xù)做除法。因此，在做高精度除法時，要涉及到乘法運算和減法運算，還有移位處理。當(dāng)然，為了程序簡潔，可以避免高精度乘法，用 09 次循環(huán)減法取代得到商的值。這里，我們討論一下高精度數(shù)除以單精度數(shù)的結(jié)果，采取的方法是按位相除法。參考程序：program exam4;constmax=200;vara,c:array1.max of 0.9;x,b:longint;n1,n2:string;lena:integer;code,i,j:integer;beginwrite(Input dividend:); readln(n1);write(Input divisor:); readln(n2);lena:=length(n1);for i:=1 to lena do ai := ord(n1i) - ord(0);val(n2,b,code);按位相除x:=0;for i:=1 to lena do beginci:=(x*10+ai) div b;x:=(x*10+ai) mod b;end;顯示商j:=1;while (cj=0) and (j1) and (pi-1=pi) do dec(i);if i=1 then break;求滿足關(guān)系式 Pi -1 0) and (pi-1=pj) do dec(j);if j=0 then break;Pi -1與 Pj互換得 (P) = P 1 P2 ,Pmt:=pi-1;pi-1:=pj;pj:=t;Pi, Pm的順序逆轉(zhuǎn)for j:=1 to (m-i+1) div 2 do begint:=pi+j-1;pi+j-1:=pm-j+1;pm-j+1:=tend;打印當(dāng)前解for i:=1 to m do write(pi);inc(count);writeln;until false;writeln(count)End.例 6：求 N 個人選取 M 個人出來做游戲，共有多少種取法？例如：N=4，M=2 時，有12，13，14，23，24，34 共六種。分析：因為組合數(shù)跟順序的選擇無關(guān)。因此對同一個組合的不同排列，只需取其最小的一個（即按從小到大排序） 。因此，可以設(shè)計如下算法：1最后一位數(shù)最大可達 N，倒數(shù)第二位數(shù)最大可達 N-1，依此類推，倒數(shù)第 K 位數(shù)最大可達N-K+1。若 R 個元素組合用 C1C2 CR表示，且假定 C1n-m+1) and ( j0) do dec(j); 求 I=maxJ | CjN-R+J cj:=cj+1;for i:=j+1 to m do ci:=ci-1+1; 建立下一個組合for i:=1 to m do write(ci);writeln 輸出end;End.第四課 枚舉法課題：枚舉法目標：知識目標：枚舉算法的本質(zhì)和應(yīng)用能力目標：枚舉算法的應(yīng)用！重點：利用枚舉算法解決實際問題難點：枚舉算法的次數(shù)確定板書