信息算法知識(shí)梳理

算法與程序設(shè)計(jì)1．算法：為解決某一問題設(shè)計(jì)的確定的有限的步驟。2．算法的主要特征：有窮性、確定性、可行性、有0個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出3．算法的描述方法：自然語言，流程圖，偽代碼或程序。4．流程圖符號(hào)起止框輸入輸出框處理框判斷框流程線5．常量：在程序執(zhí)行過程中事先設(shè)置、其值不發(fā)生改變的量。6．變量：在程序執(zhí)行過程中，取值可以改變的量，對(duì)應(yīng)計(jì)算機(jī)內(nèi)部的存儲(chǔ)單元。（1）每個(gè)變量都有一個(gè)名字作為標(biāo)記，不同程序設(shè)計(jì)語言對(duì)變量的命名規(guī)則個(gè)不相同。（在Vb程序中,變量的命名,只能由字母、數(shù)字和下劃線三類字符組成，但第一個(gè)字符必須是字母）（2）從變量中讀取數(shù)據(jù)后，變量的值不發(fā)生改變。（3） 變量的賦值：a=2或a一2（4） 變量賦值的特點(diǎn)：取之不盡，賦值即覆蓋（5） 數(shù)據(jù)類型數(shù)據(jù)類型名說明性質(zhì)Integer整數(shù)型-32768—32767范圍內(nèi)的任何整數(shù)Long長整型-2147483648-2147483647范圍內(nèi)的任何整數(shù)Single單精度實(shí)數(shù)型絕對(duì)值在1.40E-45~3.40E38內(nèi)的實(shí)數(shù)，有效數(shù)字約6~7位Double雙精度實(shí)數(shù)型絕對(duì)值在-4.94E324~3.40E308內(nèi)的實(shí)數(shù)，有效數(shù)字約14~15位String字符串型一段文字與符號(hào)Boolean邏輯型判斷的結(jié)果：值為真（True）或假（False）Date日期型日期和時(shí)間

7．運(yùn)算符類別運(yùn)算符運(yùn)算結(jié)果優(yōu)先級(jí)算術(shù)運(yùn)算符八、*、/、mod、+、-數(shù)值*/\mod+-關(guān)系運(yùn)算符＞、＜、＞=、〈二、二、＜＞True或False相同邏輯運(yùn)算符not、and、orTrue或FalseNot>and>or8．三類運(yùn)算符的優(yōu)先級(jí)：算術(shù)運(yùn)算符＞關(guān)系運(yùn)算符＞邏輯運(yùn)算符9.主要函數(shù)：取整函數(shù)Int()、求算術(shù)平方根函數(shù)sqr()、求絕對(duì)值函數(shù)abs()10．算法的三種結(jié)構(gòu)：順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。丿1順序結(jié)構(gòu)雙分支結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)11?默寫分支結(jié)構(gòu)的語句代碼丿1順序結(jié)構(gòu)雙分支結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)11?默寫分支結(jié)構(gòu)的語句代碼雙分支結(jié)構(gòu)單分支結(jié)構(gòu)if條件thenif條件then語句組A語句組Aelseendif語句組Bendif

11．默寫循環(huán)結(jié)構(gòu)的兩種語句代碼for循環(huán)變量=初值to終值step步長循環(huán)體next循環(huán)變量循環(huán)次數(shù)=int((終值-初值)/步長值)+1Dowhile循環(huán)條件Dowhile循環(huán)條件循環(huán)體Loopdo循環(huán)體loopuntil循環(huán)條件12．循環(huán)結(jié)構(gòu)中要注意：循環(huán)初始狀態(tài)、循環(huán)體、循環(huán)條件。13．計(jì)數(shù)器：在算法執(zhí)行過程中，用來記錄某種事件發(fā)生次數(shù)的變量。計(jì)數(shù)器的初值通常為0(2)在循環(huán)體中的計(jì)數(shù)語句i=i+114.累加器：在算法執(zhí)行過程中，用來生成并存儲(chǔ)數(shù)據(jù)累加和的變量累加器的初值通常為0(2)在循環(huán)體中的累加語句s=s+a15．累乘器：在算法執(zhí)行過程中，用來生成并存儲(chǔ)數(shù)據(jù)累乘積的變量。累乘器的初值通常為1(2)在循環(huán)體中的累乘語句s=s*a16．解析算法：用解析的方法找出表示問題的前提條件與結(jié)果之間關(guān)系的數(shù)學(xué)表達(dá)式，并通過表達(dá)式的計(jì)算來實(shí)現(xiàn)問題求解。【解析算法實(shí)例1】輸入已知三角形三條邊的長a、b、c,利用海倫公式求三角形面積。開始輸入三角形三條

邊長abcs?(a+b+c)/2x?開始輸入三角形三條

邊長abcs?(a+b+c)/2x?sqr(s*(s-a)*(s-b)*(s-c))輸出x結(jié)束DimaasintegerDimbasintegerDimcasintegerDimxassingle| a = InputBox("a:")| b = InputBox("b:")| c = InputBox("c:")| s = (a+b+c)/2x=Sqr(s*(s-a)*(s-b)*(s-c))Printx17．枚舉算法：列出各種可能的情況并逐一進(jìn)行檢驗(yàn)，根據(jù)檢驗(yàn)的結(jié)果執(zhí)行相應(yīng)的操作?！懊丁本褪且粋€(gè)一個(gè)；“舉”就是列舉。核心：不遺漏不重復(fù)。枚舉算法充分利用了計(jì)算機(jī)“運(yùn)行速度快、不知疲倦”的優(yōu)勢(shì)。（1）結(jié)構(gòu)特點(diǎn)：循環(huán)中嵌套分支結(jié)構(gòu)列舉 由循環(huán)結(jié)構(gòu)實(shí)現(xiàn)檢驗(yàn)——由分支結(jié)構(gòu)實(shí)現(xiàn)算機(jī)“運(yùn)行速度快、不知疲倦”的優(yōu)勢(shì)。（1）結(jié)構(gòu)特點(diǎn)：循環(huán)中嵌套分支結(jié)構(gòu)列舉 由循環(huán)結(jié)構(gòu)實(shí)現(xiàn)檢驗(yàn)——由分支結(jié)構(gòu)實(shí)現(xiàn)初始狀態(tài)J叫否繼續(xù)列舉FT準(zhǔn)備列舉下一個(gè)2）設(shè)計(jì)步驟1）確定列舉的范圍：不能隨意擴(kuò)大和縮小范圍，否則會(huì)造成重復(fù)或漏解2）明確檢驗(yàn)的條件：根據(jù)檢驗(yàn)的對(duì)象來設(shè)定條件，以及檢驗(yàn)后所執(zhí)行的相關(guān)操作。3）確定循環(huán)控制的方式和列舉的方式：借助循環(huán)變量的變化來列舉，或通過輸入。枚舉算法實(shí)例】若一個(gè)三位數(shù)x=100*a+10*b+c（a、b、c都是個(gè)位數(shù)），滿足找出三位數(shù)中所有的水仙花數(shù)。dimxasintegerdimaasintegerdimbasintegerdimcasintegerx=100DoWhilex<=999a=Int(x/100)b=Int((xMod100)/10)c=xMod10Ifa八3+b八3+c八3=xThenPrintxEndIfx=x+1Loop

18．?dāng)?shù)組：一種特殊的變量，在內(nèi)存中的位置是連續(xù)的，用于存儲(chǔ)一批類型、作用相同的數(shù)據(jù)。幾個(gè)相關(guān)概念：數(shù)組名、數(shù)組元素、數(shù)組元素名、數(shù)組元素下標(biāo)、數(shù)組元素值。數(shù)組必須先聲明后使用。Dim〈數(shù)組名〉(下標(biāo))As〈數(shù)據(jù)類型〉例1：Dima(3)asinteger定義了a(0),a(l),a(2),a(3)四個(gè)變量是數(shù)組類型例2：DimSc(3to6)AsString定義了Sc(3),Sc(4),Sc(5)和Sc(6)，并且每個(gè)元素都是字符串型的數(shù)組實(shí)例】輸入10個(gè)數(shù)字，依次存放到數(shù)組中，再將其逆序輸出。iTO.i>=1.上-結(jié)束Dimd(1To10)iTO.i>=1.上-結(jié)束PrivateSubCommandlClick()i=1DoWhilei<=10a=InputBox("請(qǐng)輸入數(shù)字："，i)d(i)=ai=i+1Loopi=10DoWhilei>=1Printd(i)i=i-1LoopEndSub19．冒泡排序的算法思想從最下面一個(gè)元素起，自下而上地比較相鄰兩個(gè)元素中的數(shù)據(jù)，將較小的數(shù)值交換到上面一個(gè)元素。重復(fù)這一過程，直到處理完最后兩個(gè)元素中的數(shù)據(jù)，稱為一遍加工。此時(shí)，最小的數(shù)據(jù)已經(jīng)上升到第一個(gè)元素的位置。然后對(duì)余下的i-1個(gè)元素重復(fù)上述過程。由于每一遍加工都是將最小的元素像氣泡一樣浮至頂端，故稱為冒泡排序。例：有一組數(shù)據(jù)23、61、24、15、89，問第二輪冒泡的第一次交換后數(shù)據(jù)排序的結(jié)果如何？

冒泡過程：原始數(shù)據(jù)2361241589第一輪冒泡（交換3次）1589152489156124891523612489第二輪冒泡（第1次父換）2489246189答：第二輪冒泡的第一次交換后數(shù)據(jù)排序結(jié)果為15、23、24、61、89接輸出部分

20．選擇排序的算法思想（找最值——擂臺(tái)法）（1）從第一個(gè)元素起，自上而下找出最小數(shù)，并記錄下它的位置，將最小數(shù)交換到第一個(gè)元素中。完成第一遍加工。（2）然后對(duì)余下的i-1個(gè)元素重復(fù)上述過程。（3）在每一遍加工中，只需交換一次位置即可上例中的這組數(shù)據(jù)23、61、24、15、89，用選擇排序的過程如下：原始數(shù)據(jù)2361241589第一遍加工1561242389第二遍加工1523246189〖冒泡排序與選擇排序的比較〗選擇排序?qū)嶋H上是一種優(yōu)化了的排序方法，它和冒泡排序的區(qū)別在于減少了交換的次數(shù)，在每一遍的加工過程中，選擇排序采用的方法是通過遍歷，記錄下最值的位置，最后再將最值所在位置的數(shù)據(jù)與待排元素所在的位置進(jìn)行交換，因此每一遍加工只需交換依次位置。大大減少了算法的復(fù)雜度。i=1Fiv=n-lk=iF<=nTk=jd(j)<d(k)F交換d（i）與d（k）中的數(shù)據(jù)j=j+1i=1Fiv=n-lk=iF<=nTk=jd(j)<d(k)F交換d（i）與d（k）中的數(shù)據(jù)j=j+1j=i+1i=i+1DoWhilei<=n-1k=ij=i+1DoWhilej<=nIfd(j)<d(k)Thenk=jEndIfj=j+1Loopt=d(i)d(i)=d(k)d(k)=ti=i+1Loop

21．擂臺(tái)法實(shí)例：已知數(shù)組d中已經(jīng)存放了10個(gè)數(shù)，輸出其中的最大值先假設(shè)d[1]中的數(shù)值是最大值，令k-d[1]。用d[2]與k比較，若d[2]大，則令k-d[2],否則繼續(xù)比較，直至d[10]如果還需輸出最大值所在的位置，則還需跟蹤數(shù)組元素的下標(biāo)。如下圖右。i=2Fi<=10Fd(i)>kT輸出k結(jié)束i=i+1k=d(i)k=d(1)F.i<=10Fd(i)>kTn=i開始]輸出k,n/(結(jié)束)i=2,n=1k=d(1)i=2Fi<=10Fd(i)>kT輸出k結(jié)束i=i+1k=d(i)k=d(1)F.i<=10Fd(i)>kTn=i開始]輸出k,n/(結(jié)束)i=2,n=1k=d(1)i=i+1k=d(i)22．順序查找的算法思想：按照數(shù)組元素的先后次序，從第一個(gè)元素開始遍歷，逐個(gè)檢驗(yàn)是否和查找的數(shù)據(jù)相等。例：在包含10個(gè)數(shù)字的數(shù)組中順序查找一個(gè)符合要求的數(shù)。X10輸出0Yd[i]=n輸出iX1-1開始/X10輸出0Yd[i]=n輸出iX1-1開始/輸An/（結(jié)束）Key=inputbox(“”i=1Dowhilei<=nIfd(i)=KeyThenPrintiExitsubEndIfi=i+1loopIfi=n+1ThenPrint"在數(shù)組中沒有找到"EndIf23．對(duì)分查找的算法思想：先取數(shù)組中間的元素和關(guān)鍵字比較，若不相等則