




已閱讀5頁(yè),還剩77頁(yè)未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
基礎(chǔ)算法教案 目錄第一課 算法簡(jiǎn)介 .1第二課 多精 度數(shù)值處理 .1第三課 排列與 組合 .6第四課 枚 舉法 .9第五課 遞歸與回 溯法 .25第六課 遞 推法 .42第七課 貪心法 .50第八課 分 治法 .64第九課 模 擬法 .70習(xí) 題 .79第一課 算法簡(jiǎn)介算法是一組(有限個(gè))規(guī)則,它為某個(gè)特定問(wèn)題提供了解決問(wèn)題的運(yùn)算序列。在信息學(xué)競(jìng)賽中,就是計(jì)算機(jī)解題的過(guò)程。在這個(gè)過(guò)程中,無(wú)論是形成解題思路還是編寫(xiě)算法,都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)的算法,后者是操作實(shí)現(xiàn)的算法。計(jì)算機(jī)解題的核心是算法設(shè)計(jì)。一個(gè)算法應(yīng)該具有以下五個(gè)重要特征: 有窮性:一個(gè)算法必須能在執(zhí)行有限步之后結(jié)束; 確切性:算法的每一步驟必須確切定義; 輸入:一個(gè)算法有零個(gè)或多個(gè)輸入,以描述運(yùn)算對(duì)象的初始情況。所謂 0 個(gè)輸入是指算法本身給出了初始條件; 輸出:一個(gè)算法有一個(gè)或多個(gè)輸出,以反映對(duì)輸入數(shù)據(jù)處理后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的; 可行性:算法原則上能夠精確的運(yùn)行,而且其運(yùn)算規(guī)模是可以承受的。為了獲得一個(gè)既有效又優(yōu)美的算法,必須首先了解一些基本的常用算法設(shè)計(jì)思路。下面,我們就對(duì)構(gòu)成算法所依據(jù)的一些基本方法展開(kāi)討論,如遞推法,遞歸法,枚舉法,分治法,模擬法,貪心法等。第二課 多精度數(shù)值處理課題:多精度數(shù)值的處理目標(biāo):知識(shí)目標(biāo):多精度值的加、減、乘、除能力目標(biāo):多精度值的處理,優(yōu)化!重點(diǎn):多精度的加、減、乘難點(diǎn):進(jìn)位與借位處理板書(shū)示意:1) 輸入兩個(gè)正整數(shù),求它們的和2) 輸入兩個(gè)正整數(shù),求它們的差3) 輸入兩個(gè)正整數(shù),求它們的積4) 輸入兩個(gè)正整數(shù),求它們的商授課過(guò)程:所謂多精度值處理,就是在對(duì)給定的數(shù)據(jù)范圍,用語(yǔ)言本身提供的數(shù)據(jù)類型無(wú)法直接進(jìn)行處理(主要指加減乘除運(yùn)算) ,而需要采用特殊的處理辦法進(jìn)行??纯聪旅娴睦?。例 1 從鍵盤(pán)讀入兩個(gè)正整數(shù),求它們的和。分析:從鍵盤(pán)讀入兩個(gè)數(shù)到兩個(gè)變量中,然后用賦值語(yǔ)句求它們的和,輸出。但是,我們知道,在 pascal 語(yǔ)言中任何數(shù)據(jù)類型都有一定的表示范圍。而當(dāng)兩個(gè)被加數(shù)據(jù)大時(shí),上述算法顯然不能求出精確解,因此我們需要尋求另外一種方法。在讀小學(xué)時(shí),我們做加法都采用豎式方法,如圖 1。這樣,我們方便寫(xiě)出兩個(gè)整數(shù)相加的算法。如果我們用數(shù)組 A、B 分別存儲(chǔ)加數(shù)和被加數(shù),用數(shù)組 C 存儲(chǔ)結(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 存儲(chǔ)被加數(shù),b 存儲(chǔ)加數(shù),c 存儲(chǔ)結(jié)果 var i,x:integer;begini:=1while (i0) or(i=10 then 處理最高進(jìn)位begin lenc:=i;ci:=1 end else lenc:=i-1;for i:=lenc downto 1 do write(ci); 輸出結(jié)果writelnend.例 2 高精度減法。從鍵盤(pán)讀入兩個(gè)正整數(shù),求它們的差。分析:類似加法,可以用豎式求減法。在做減法運(yùn)算時(shí),需要注意的是:被減數(shù)必須比減數(shù)大,同時(shí)需要處理借位。因此,可以寫(xiě)出如下關(guān)系式if ai1) do dec(lenc); 最高位的 0 不輸出for i:=lenc downto 1 do write(ci);writelnend.例 3 高精度乘法。從鍵盤(pán)讀入兩個(gè)正整數(shù),求它們的積。分析:類似加法,可以用豎式求乘法。在做乘法運(yùn)算時(shí),同樣也有進(jìn)位,同時(shí)對(duì)每一位進(jìn)乘法運(yùn)算時(shí),必須進(jìn)行錯(cuò)位相加,如圖 3, 圖 4。分析 C 數(shù)組下標(biāo)的變化規(guī)律,可以寫(xiě)出如下關(guān)系式C i = C i +C ”i +由此可見(jiàn),C i跟 Ai*Bj乘積有關(guān),跟上次的進(jìn)位有關(guān),還跟原 C i的值有關(guān),分析下標(biāo)規(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 對(duì)乘數(shù)的每一位進(jìn)行處理x := ai*bj + x div 10 + ci+j-1; 當(dāng)前乘積+上次乘積進(jìn)位+原數(shù) ci+j-1 := x mod 10;end;ci+j:= x div 10; 進(jìn)位end;lenc:=i+j;while (clenc=0) and (lenc1) do dec(lenc);for i:=lenc downto 1 do write(ci);writelnend.例 高精度除法。從鍵盤(pán)讀入兩個(gè)正整數(shù),求它們的商(做整除) 。分析:做除法時(shí),每一次上商的值都在,每次求得的余數(shù)連接以后的若干位得到新的被除數(shù),繼續(xù)做除法。因此,在做高精度除法時(shí),要涉及到乘法運(yùn)算和減法運(yùn)算,還有移位處理。當(dāng)然,為了程序簡(jiǎn)潔,可以避免高精度乘法,用 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 個(gè)人選取 M 個(gè)人出來(lái)做游戲,共有多少種取法?例如:N=4,M=2 時(shí),有12,13,14,23,24,34 共六種。分析:因?yàn)榻M合數(shù)跟順序的選擇無(wú)關(guān)。因此對(duì)同一個(gè)組合的不同排列,只需取其最小的一個(gè)(即按從小到大排序) 。因此,可以設(shè)計(jì)如下算法:1最后一位數(shù)最大可達(dá) N,倒數(shù)第二位數(shù)最大可達(dá) N-1,依此類推,倒數(shù)第 K 位數(shù)最大可達(dá)N-K+1。若 R 個(gè)元素組合用 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; 建立下一個(gè)組合for i:=1 to m do write(ci);writeln 輸出end;End.第四課 枚舉法課題:枚舉法目標(biāo):知識(shí)目標(biāo):枚舉算法的本質(zhì)和應(yīng)用能力目標(biāo):枚舉算法的應(yīng)用!重點(diǎn):利用枚舉算法解決實(shí)際問(wèn)題難點(diǎn):枚舉算法的次數(shù)確定板書(shū)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 公司背景墻策劃方案
- 公司春季放風(fēng)箏活動(dòng)方案
- 公司游園小活動(dòng)策劃方案
- 公司職稱評(píng)審策劃方案
- 公司群體互動(dòng)策劃方案
- 公司群體性運(yùn)動(dòng)活動(dòng)方案
- 公司節(jié)前大掃除活動(dòng)方案
- 公司知識(shí)跨年活動(dòng)方案
- 公司管理規(guī)范年活動(dòng)方案
- 公司旅游預(yù)熱引流活動(dòng)方案
- 人教版七年級(jí)下冊(cè)歷史期末試卷與答案
- 2023陜西中考數(shù)學(xué)(副題)含答案解析版
- 李可老中醫(yī)急危重癥疑難病經(jīng)驗(yàn)專輯
- 生理學(xué)全套課件
- 孕期保健主題宣教培訓(xùn)課件
- 《高血壓健康教育規(guī)范》
- 小學(xué)特色課程《口風(fēng)琴課程》校本教材
- 電腦教室搬遷方案
- 《如何寫(xiě)文獻(xiàn)綜述》課件
- 汽車美容店計(jì)劃書(shū)案例
- 2023高教版中職中國(guó)特色社會(huì)主義基礎(chǔ)模塊課程標(biāo)準(zhǔn)
評(píng)論
0/150
提交評(píng)論