算法及程序?qū)崿F(xiàn)知識點(diǎn)

1、算法及程序?qū)崿F(xiàn)知識點(diǎn)一、枚舉算法及程序?qū)崿F(xiàn)枚舉算法基本思想是根據(jù)問題本身的性質(zhì)，一一列舉出該問題所有可能的情況，并根據(jù)題目的條件逐個作出判斷， 從中挑出符合要求的解。枚舉算法屬于搜索策略，適用于解變量確定的連續(xù)值域的問題。設(shè)計枚舉算法時要在盡可能小的范圍內(nèi)羅列出所有可能的情況，不能遺漏，也不能重復(fù)。例 : 假如我有一個 QQ的密碼是一位數(shù)字， 如果讓同學(xué)們來破解的話，會把 0 到 9 十個數(shù)字都試一遍，找到密碼，這種方法使用的算法就是枚舉算法。枚舉算法解題的主要方法，必須把所有的可能情況都一一列出來，這種可能情況，一般通過循環(huán)列舉出來。例如課本例題，一份單據(jù)被抹除的數(shù)字的推算問題?？赡艿那闆r有

2、25006 至 25996 一共 100 種，通過循環(huán)把這一百種情況全部列出來，在循環(huán)列出來的過程對，對每一種情況進(jìn)行比較，是否符合要求。n=25006+j*100 ，j 的范圍為 0 至 99，此處列出來的表達(dá)式只有一個未知數(shù)j ，所以只需用一重循環(huán)就夠了。DO循環(huán)c=0如果需要統(tǒng)計符合要求的單據(jù)的張數(shù)的話，用c 做計數(shù)器j=0do while j<100j 的范圍是0 至 99，此處也可寫成j<=99n=25006+j*100通過 j 把單據(jù)的所有的可能情況列出來if n mod 37=0 or n mod 67=0 then判斷是否符合要求print nc=c+1通過判斷把符

3、合要求的單據(jù)的值輸出符合要求的單據(jù)加一張end ifj=j+1j 每次增加1 直到99loopFOR循環(huán)c=0如果需要統(tǒng)計符合要求的單據(jù)的張數(shù)的話，用For j=0 to 99一重循環(huán)，把j 所有可能情況列出來n=25006+j*100通過 j 把單據(jù)的所有的可能情況列出來if n mod 37=0 or n mod 67=0 then判斷是否符合要求print n通過判斷把符合要求的單據(jù)的值輸出c=c+1符合要求的單據(jù)加一張c 做計數(shù)器end ifNext j在 for 循環(huán)中不需要 j=j+1 ，因?yàn)?for 循環(huán) j 的值每次會自己增加步長，此處步長省略沒寫，即表示步長為 1，所以 j

4、每次會自動增加 1。課本例題變形金剛問題：小盒5 個，大盒 12 個， 1200 個多少種裝法。設(shè)小盒為x 個，則 x 的范圍是： 0 至 240；設(shè)大盒為y 個，則 y 的范圍是： 0 至 100要求符合的條件為5*x+12*y=1200 ，此處有兩個未知數(shù)x、y，所以的用二重循環(huán)（三個未知數(shù)即用三重、四個未知數(shù)即用四重循環(huán) ）DO循環(huán)c=0：x=0： y=0do while x<=240do while y<=100n=5*x+12*yif n=1200 thenprint x,yc=c+1第一重循環(huán)， x 的范圍是0 至 240第二重循環(huán)， y 的范圍是0 至 100通過 x

5、,y 把所有的可能裝法情況列出來判斷是否符合要求（5*x+12*y=1200 ）通過判斷把符合要求的裝法情況輸出符合要求的裝法增加一次end ify=y+1loopx=x+1loopy 每次增加 1 直到第二重循環(huán)結(jié)束x 每次增加 1 直到第一重循環(huán)結(jié)束100240FOR循環(huán)c=0for x=0 to 240for y=0 to 100n=5*x+12*yif n=1200 thenprint x,yc=c+1第一重循環(huán)， x 的范圍是0 至 240第二重循環(huán)， y 的范圍是0 至 100通過 x,y 把所有的可能裝法情況列出來判斷是否符合要求（5*x+12*y=1200 ）通過判斷把符合要求

6、的裝法情況輸出符合要求的裝法增加一次end ifnext y第二重循環(huán)結(jié)束next x第一重循環(huán)結(jié)束同樣在 for循環(huán)中也不需要x=x+1 、 y=y+1，因?yàn)?for循環(huán)略沒寫，即表示步長為1，所以 x、y 每次會自動增加1。x、y的值每次會自己增加步長，此處步長省二、解析算法及程序?qū)崿F(xiàn)是指用解析的方法找出表示問題的前提條件與所求結(jié)果之間關(guān)系的數(shù)學(xué)表達(dá)式，并通過表達(dá)式的計算來實(shí)現(xiàn)問題求解。例：同學(xué)們在數(shù)學(xué)的應(yīng)用題中、物理、化學(xué)的計算題中通過理解題意得出表達(dá)式，再通過計算得到答案，所使用的算法就是解析算法。解題方法：主要是要得出前提條件與所求結(jié)果之間關(guān)系的數(shù)學(xué)表達(dá)式， 并且在程序中這個數(shù)學(xué)表達(dá)

7、式必須符合 VB格式。儲蓄問題，不考慮復(fù)利，年利率2.8%， M元錢需存多少年，才能得到K 元本息？設(shè)需要 y 年，根據(jù)題意得出的數(shù)學(xué)表達(dá)式為：km，但是在VB 中表達(dá)式必須符合VB 語法：y=0.028my=(k-m)/(0.028*m)流程圖及程序?qū)崿F(xiàn)略。三、排序算法及程序?qū)崿F(xiàn)1冒泡排序冒泡排序的基本思想是把待排序的 n個元素的數(shù)組看成是垂直堆放的一列數(shù)據(jù)，從最下面的一個元素起，自下而上地比較相鄰的兩個元素中的數(shù)據(jù)，將較小的數(shù)據(jù)換到上面的一個元素中。重復(fù)這一過程，直到處理完最后兩個元素中的數(shù)據(jù)，稱為一遍加工（一趟冒泡）。當(dāng)?shù)谝槐榧庸ね瓿蓵r，最小的數(shù)據(jù)已經(jīng)上升到第一個元素的位置。然后對余下的

8、 n-1 個元素重復(fù)上述過程，直至最后進(jìn)行余下兩個數(shù)據(jù)的比較和交換。冒泡排序算法舉例設(shè)有數(shù)列 65,13,76, 27,49第 1 趟比較第 1 次 65,13,76, 27,49 不需要交換第 1 趟比較第 2 次 65,13,76, 27,49 76,27 交換第 1 趟比較第 3 次 65,13,27, 76,49 不需要交換第 1 趟比較第 4 次 65,13,27, 76,49 65,13 交換第 1 趟結(jié)束： 13,65,27,76,49第 1 趟比較 4 次，交換2 次第 2 趟比較第 1 次： 1365,27,76,49 76,49 交換第 2 趟比較第 2 次： 1365,2

9、7,49,76 不需要交換第 2 趟比較第 3 次： 1365,27,49,76 65,27 交換第 2 趟結(jié)束： 13,27,65,49,76第 2 趟比較 3 次，交換2 次第 3 趟比較第 1 次： 13,2765,49,76 不需要交換第 3 趟比較第 2 次： 13,2765,49,76 65,49 交換第 3 趟結(jié)束： 13,27,49c65,76第 3 趟比較 2 次，交換1 次第 4 趟比較第 1 次： 13,27,4965,76 不需要交換第 4 趟結(jié)束： 13,27,49,65,76第 4 趟比較 1 次，沒有交換5 個元素的數(shù)據(jù)系列，一共冒泡了4 趟，分別比較次數(shù)為 4、

10、 3、 2、 1，交換次數(shù)根據(jù)實(shí)際情況確定。所以可以總結(jié)出，n 個元素的數(shù)組系列通過冒泡排序，需要經(jīng)過n-1 趟冒泡，總的比較次數(shù)為：(n-1)+(n-2)+(n-3)+ +1= ( n 1) * n 次。2兩個元素中的數(shù)據(jù)交換一般需要通過第三個變量來進(jìn)行D(1)=5:D(2)=8交換的過程為：T=D(1)D(1)=D(2)D(2)=T流程圖：冒泡排序的程序?qū)崿F(xiàn)：通過例子我們知道，5 個元素的數(shù)據(jù)系列，一共冒泡了4 趟，分別比較次數(shù)為設(shè)計中，我們通過循環(huán)來進(jìn)行控制，需要兩重循環(huán)，大循環(huán)控制冒泡了4 趟：For i=1 to 4 （ 5-1）4、 3、 2、1。所以在程序Next i小循環(huán)控制每

11、趟冒泡比較的次數(shù)：For j=5 to i（ i 的值根據(jù)大循環(huán)分別為1到4）Next i所以小循環(huán)是在大循環(huán)里面的通過判斷if d(j)<d(j-1) 來控制是否需要交換程序主體部份如下：For i=1 to n-1For j=n to I step -1If d(j)<d(j-1) thenT=d(j)D(j)=d(j-1)D(j-1)=tEnd ifNext jNext i2選擇排序選擇排序的基本思想是在所有的記錄中選出最?。ù螅┑臄?shù)據(jù)，把它與第一個數(shù)據(jù)交換，然后在其余的記錄中再選出最?。ù螅┑臄?shù)據(jù)與第二個數(shù)據(jù)交換，依此類推，直至所有數(shù)據(jù)排序完成。流程圖：選擇排序算法舉例設(shè)有

12、數(shù)列 65,97,76,13,27,49,58 第 1 趟 65,97,76,13,27,49,58尋找最小數(shù)據(jù) d(k)=d(4)=13 與 d(1)交換第 2 趟 1397,76,65,27,49,58尋找最小數(shù)據(jù) d(k)=d(5)=27 與 d(2)交換第 3 趟 13,2776,65,97,49,58尋找最小數(shù)據(jù) d(k)=d(6)=49 與 d(3)交換第 4 趟 13,27,4965,97,76,58尋找最小數(shù)據(jù) d(k)=d(7)=58 與 d(4)交換第 5 趟 13,27,49,5897,76,65尋找最小數(shù)據(jù) d(k)=d(7)=65 與 d(5)交換第 6 趟 13,2

13、7,49,58,6576,97 尋找最小數(shù)據(jù) d(k)=d(6)=76 與 d(6)交換結(jié)束： 13,27,49,58,65,76977 個元素的數(shù)據(jù)系列需要尋找6 次。程序?qū)崿F(xiàn)：d(1)=65 ； d(2)=97for i=1 to 6k=i； d(3)=76； d(4)=13； d(5)=27 ；d(6)=49 ； d(7)=58第一重循環(huán)，控制趟數(shù)，7 個元素需要6 趟for j=i+1 to 7第二重循環(huán)，在待排序中找最小數(shù)，待排序元素每次減少一個if d(j)<d(k) then k=jnext jif k<>i thenkt=d(j)找出最小的數(shù)據(jù)結(jié)束第二重循環(huán)把

14、最小數(shù)據(jù)與待排序數(shù)據(jù)中的第一個交換d(j)=d(k)d(k)=ktend ifnext i結(jié)束第一重循環(huán)例 1：選擇排序的基本思想是在參與排序的所有數(shù)組元素中找出最小互換位置，然后再在余下的元素中重復(fù)上述過程。有一組數(shù)，順序是“這組數(shù)從大到小排序，第一次交換數(shù)據(jù)后的順序是：(或最大 )的元素，使它與第一個元素2、 6、 4、 1”，用選擇排序法將（ A） 6、2、1、4（B） 6、4、2、1 （C） 6、1、2、4 （D） 6、2、4、1四、查找算法及程序?qū)崿F(xiàn)1順序查找順序查找的基本思想是從第一個數(shù)據(jù)開始，按數(shù)據(jù)的順序逐個將數(shù)據(jù)與給定的值進(jìn)行比較，若某個數(shù)據(jù)和給定值相等，則查找成功，找到所查數(shù)

15、據(jù)的位置；反之，查找不成功。流程圖：d(1)=65 ； d(2)=97 ； d(3)=76 ； d(4)=13 ； d(5)=27 ；d(6)=49 ； d(7)=58查找 key=49程序?qū)崿F(xiàn)：For i=1 to 7If d(i)=key then輸出找到是第d(i)個Exit forEnd ifNext i2對分查找對分查找的基本思想是在有序的數(shù)據(jù)列中，首先將要查找的數(shù)據(jù)與有序數(shù)組內(nèi)處于中間位置的數(shù)據(jù)進(jìn)行比較，如果兩者相等，則查找成功；否則根據(jù)數(shù)組元素的有序性，就可確定該數(shù)據(jù)應(yīng)該在數(shù)組的前半部分還是后半部分繼續(xù)進(jìn)行查找； 在新確定的范圍內(nèi)， 繼續(xù)按上述方法進(jìn)行查找， 直到找到要查找的數(shù)據(jù)

16、，使查找成功，或直到子表不存在，查找不成功。對分查找的條件是被查找的數(shù)據(jù)必須是有序的。對分（二分）查找過程：d(1)=13 ； d(2)=27 ； d(3)=49 ； d(4)=58 ； d(5)=76；d(6)=97； d(7)=102； d(8)=138； d(9)=202查找k=138d(1)=13 第一次 d(1)=13； d(2)=27 ； d(3)=49 ； d(4)=58 ； d(5)=76 ；d(6)=97 ； d(7)=102 ； d(8)=138 ； d(9)=202k 與 d（fix （1+9 ） /2） =d（ 5）比較 ，比 d（5）大，下次在d（5）的右邊找； d(

17、2)=27 ； d(3)=49 ； d(4)=58 ； d(5)=76 ；d(6)=97 ； d(7)=102 ； d(8)=138 ； d(9)=202第二次 k 與 d（5）右邊的 d（ fix （ 6+9） /2） =d（ 7）比較 ，比 d（ 7）大，下次在 d（ 7）的右邊找 d(1)=13 ； d(2)=27 ； d(3)=49 ； d(4)=58 ； d(5)=76 ；d(6)=97 ； d(7)=102 ； d(8)=138 ； d(9)=202第三次 k 與 d（7）右邊的d（ fix （ 8+9） /2） =d（ 8）比較 ，與 d（ 8）相等，找到。依次被訪問進(jìn)行比較的數(shù)字為：d（5）、 d（7）、 d（8）流程圖：課本上的查找函數(shù)：Function search（ key as integer） as integeri=1i代表待查找數(shù)列中的第一個元素的下標(biāo)，剛開始時是1j=9j代表待查找數(shù)列中的最后一個元素的下標(biāo)，剛開始時是9（因?yàn)橐还? 個元素）nc=0統(tǒng)計查找次數(shù)do while i<=j第一個元素的下標(biāo)要小于或等于最后一個元素的下標(biāo)，否則待查找數(shù)列就不存在了nc=nc+1每找一次增加一次m=fix （i+j ） /2求等查找數(shù)列中間數(shù)的下標(biāo)if d