電子教案C 語言案例教程第五章2

1、第二節(jié)二分檢索法 本節(jié)任務 學會二分檢索法 學習要點 掌握二分檢索法的一般步驟，二分檢索又稱為折半檢索，是效率比順序檢索要高的檢索方法，對于數(shù)據(jù)量較多時，排序的速度要快得多。 【引例】5_2_1 猜數(shù)游戲。計算機隨機產(chǎn)生一個兩位自然數(shù)，學員從鍵盤猜，看幾次猜中。5次內(nèi)猜中者“優(yōu)秀”；610次猜中者“良好”；1115次猜中者“合格”；15次以上竟然還未猜中便不用再猜了，直接輸出“下次努力！”。定義不斷從a,b得到a1,b1、從a1,b1 得到a2,b2，每個新區(qū)間長度均是其前一個區(qū)間的一半（新區(qū)間的左端點或右端點取上一區(qū)間的中點，這個中點便是您猜的數(shù)），最后所得區(qū)間必縮為一點，即為所求。這就是折

2、半查找法（二分法）。 折半檢索法的變量表見表5-4；折半法流程圖見圖5-3； #include conio.h#include math.h#include time.hmain() int data,x,n=0; clrscr(); srand(time(0); /* 動態(tài)置隨機函數(shù)種子 */ data=rand()%90+10; do n+; printf(第 %d 次猜: ,n);scanf(%d,&x); if (xdata) printf(大了!); else if (xdata) printf(小了!); while (x!=data & n15); printf(n); if(x

3、=data) if (n=5) printf(n%d 次猜中,優(yōu)秀！,n); else if (n=10) printf(n%d 次猜中,良好！,n); else printf(n%d 次猜中,合格！,n); else printf(n已超過15次，下次努力！); 例5-2-2有n個學生，其學習成績已從小到大排好序，放在數(shù)組ai中，用二分法查詢有無成績x。#includestdio.h #includestdlib.h #includetime.h #includemath.hmain() int i,j,m,n,x,w1,w2,a100; randomize(); printf(input

4、n=); scanf(%d,&n); printf(nr); for(i=1;i=n;i+) ai=random(81)+10; printf(%4d,ai); printf(nrnr); for(i=1;i=n-1;i+) for (j=i+1;jaj) x=ai; ai=aj; aj=x; for(i=1;iam) w1=m; else w2=m; /* 未找到，改變區(qū)間的一個端點 */ i+; /* 統(tǒng)計查找的次數(shù) */ while(ilog(n)/log(2)+1，停止查找，說明數(shù)列中不存在所需找的數(shù)數(shù)；作業(yè)與練習以下各題，要求列變量表，作大致流程圖，關(guān)鍵語句注釋。2同學通訊錄。鍵盤輸入某同學的姓名，即輸出其電話、家庭住址。3在一個有序序列中插入（或刪除）