選擇排隊(duì)問題的解題思路與數(shù)據(jù)組織教學(xué)內(nèi)容

選擇排隊(duì)問題的解題思路與數(shù)據(jù)組織//************************************//*程序名：5_1.cpp（數(shù)組示例）*//*作者：wuwh*//*編制時(shí)間：2002年9月20日*//*主要功能：找出最重的羊*//************************************#include<iostream.h> //預(yù)編譯命令#include<memory.h> //預(yù)編譯命令voidmain() //主函數(shù){

floatsheep[10]; //數(shù)組，有10個(gè)浮點(diǎn)類型元素，

//用于存10只羊每一只的重量

memset(sheep,0,sizeof(sheep));//初始化數(shù)組元素為0

floatbigsheep=0.0f; //浮點(diǎn)類型變量，存放最肥羊的重量

inti=0,bigsheepNo=0; //整型變量，i用于計(jì)數(shù)循環(huán)，

//bigsheepNo用于記錄最肥羊的號(hào)2#include<memory.h>floatsheep[10];memset(sheep,0,sizeof(sheep));3

for(i=0;i<10;i=i+1) //計(jì)數(shù)循環(huán)

{ //循環(huán)，開始

cout<<"請(qǐng)輸入羊的重量sheep["<<i<<"]=";//提示用

cin>>sheep[i]; //輸入第i只羊的重量

if(bigsheep<sheep[i]) //如果第i只羊比當(dāng)前最肥羊大

{ bigsheep=sheep[i]; //讓第i只羊?yàn)楫?dāng)前最肥羊

bigsheepNo=i; //紀(jì)錄第i只羊的編號(hào)

} } //循環(huán)結(jié)束 //輸出最肥羊的重量

cout<<"最肥羊的重量為"<<bigsheep<<endl; //輸出該羊的編號(hào)

cout<<"最肥羊的編號(hào)為"<<bigsheepNo<<endl;}4

for(i=0;i<10;i=i+1)

{

cout<<“請(qǐng)輸入羊的重量sheep["<<i<<“]“<<endl;

cin>>sheep[i];

if(bigsheep<sheep[i])

{ bigsheep=sheep[i];

bigsheepNo=i;

} } 5程序框圖6

類型說明符 數(shù)組名[常量表達(dá)式]例： floatsheep[10]; inta2001[1000];說明1.數(shù)組名的第一個(gè)字符應(yīng)為英文字母；2.用方括號(hào)將常量表達(dá)式括起；3.常量表達(dá)式定義了數(shù)組元素的個(gè)數(shù)；數(shù)組的定義74.數(shù)組下標(biāo)從0開始。如果定義5個(gè)元素，是從第0個(gè)元素至第4個(gè)元素；

例如 inta[5]定義了5個(gè)數(shù)組元素如下：

a[0],a[1],a[2],a[3],a[4]

這是5個(gè)帶下標(biāo)的變量，這5個(gè)變量的類型是相同的

85.常量表達(dá)式中不允許包含變量例如 intn; n=5; inta[n]; 不合法！因?yàn)閚是變量，不是常量9#defineN100#defineM200inta[N];longb[N+M];doubleg[M+6];以上定義是合法的10

第一種方法直接聲明時(shí)初始化 例如

inta[5]={3,5,4,1,2};

a[0]=3;a[1]=5;a[2]=4;a[3]=1;a[4]=2;數(shù)組初始化11

第二種方法使用memset函數(shù) 格式為

memset(數(shù)組名,初始化值,sizeof(數(shù)組名)) 舉例：

memset(sheep,0,sizeof(sheep));

含義是將名為sheep的數(shù)組中的全部元素均初始化為0。更深一層是說讓系統(tǒng)為sheep[10]所分配的內(nèi)存單元從sheep[0]為標(biāo)志的地址單元到該數(shù)組的全部地址單元都賦以0。調(diào)用此庫函數(shù)需要加入頭文件<memory.h>。121.#include<iostream.h> voidmain() { inta[4]; //聲明項(xiàng) cout<<a[0]<<endl; cout<<a[1]<<endl; cout<<a[2]<<endl; cout<<a[3]<<endl; }2.其他不變，改變聲明項(xiàng)為

inta[4]={0,1,2,3};請(qǐng)自己上機(jī)做6個(gè)實(shí)驗(yàn)133.其他不變，改變聲明項(xiàng)為

inta[4]={3,8};4.其他不變，改變聲明項(xiàng)為

inta[4]={2,4,6,8,10};5.其他不變，改變聲明項(xiàng)為

inta[4]={2,4,6,d};6.其他不變，改變聲明項(xiàng)為

intn=4; inta[n]={0,1,2,3};14討論問題使用篩法求100以內(nèi)的所有素?cái)?shù)15思路想象將100個(gè)數(shù)看作沙子和小石頭子，讓小石頭子權(quán)稱素?cái)?shù)；讓沙子當(dāng)作非素?cái)?shù)。弄一個(gè)篩子，只要將沙子篩走，剩下的就是素?cái)?shù)了。非素?cái)?shù)一定是2、3、4……的倍數(shù)。使用數(shù)組，讓下標(biāo)就是100以內(nèi)的數(shù)，讓數(shù)組元素的值作為篩去與否的標(biāo)志。比如篩去以后讓元素值為1。16方法的依據(jù)：

1至100這些自然數(shù)可以分為三類：單位數(shù)：僅有一個(gè)數(shù)1。素?cái)?shù)：是這樣一個(gè)數(shù)，它大于1，且只有1和它自身這樣兩 個(gè)正因數(shù)。合數(shù)：除了1和自身以外，還有其他正因數(shù)。

1不是素?cái)?shù)，除1以外的自然數(shù)，當(dāng)然只有素?cái)?shù)與合數(shù)。篩法實(shí)際上是篩去合數(shù)，留下素?cái)?shù)。

17為了提高篩法效率，注意到： 令n為合數(shù)（這里是100），c為n的最小正因數(shù)，

據(jù)初等數(shù)論，只要找到c就可以確認(rèn)n為合數(shù)，將其篩去。

18程序框圖如下：19上述框圖很清晰地描述了篩法的思路：1.第一塊是一個(gè)計(jì)數(shù)型的循環(huán)語句，功能是將prime數(shù)組清零。

prime[c]=0; c=2,3,…,1002.第二塊是正因數(shù)d初始化為d=2。3.第三塊是循環(huán)篩數(shù)。這里用了一個(gè)dowhile

語句，屬于一種直到型循環(huán)，其一般形式為：

do {

循環(huán)體語句塊 }

while(表達(dá)式) 20do{

循環(huán)體語句塊;}while(表達(dá)式) 21直到型循環(huán)框圖如下：直到表達(dá)式為假時(shí)才退出循環(huán)，所以循環(huán)體至少執(zhí)行一次。22舉例求π的近似值23例.求π的近似值

用變量pi表示π的值。

令 表示括號(hào)中的每個(gè)項(xiàng)當(dāng)最后一項(xiàng)的絕對(duì)值小于等于時(shí)，忽略掉以后的項(xiàng)24//************************************//*程序名：5_2.cpp*//*作者：wuwh*//*編制時(shí)間：2002年9月20日*//*主要功能：求pi的近似值*//************************************#include<iostream.h>#include<math.h>voidmain() //主函數(shù){ intsum=0; //整型變量，總項(xiàng)數(shù)

floatpi=0,a=1.0,b=1.0,c=1.0; //浮點(diǎn)變量，a為分母，b為分子，c為b除以a

do //直到型循環(huán) { //循環(huán)體，開始 pi=pi+c; //累加每一項(xiàng) sum=sum+1; a=a+2.0f; //計(jì)算每一項(xiàng)的分母 b=-b; //分子變正負(fù)號(hào)

c=b/a; //計(jì)算每一項(xiàng) } //循環(huán)體結(jié)束 while(fabs(c)>1e-6); //當(dāng)c的絕對(duì)值大于10的-6次方時(shí)，繼續(xù) //執(zhí)行循環(huán)體，否則退出

pi=4.0f*pi; //得到最終結(jié)果 cout<<"pi="<<pi<<endl; //輸出pi值 cout<<"sum="<<sum<<endl; //輸出總項(xiàng)數(shù)}25do //直到型循環(huán) { //循環(huán)體，開始

pi=pi+c; //累加每一項(xiàng)

sum=sum+1;

a=a+2.0f; //計(jì)算每一項(xiàng)的分母

b=-b; //分子變正負(fù)號(hào)

c=b/a; //計(jì)算每一項(xiàng)} //循環(huán)體結(jié)束

while(fabs(c)>1e-6);26運(yùn)行結(jié)果

pi=3.14159，sum=500000答：會(huì)構(gòu)成死循環(huán)，即無休止地執(zhí)行循環(huán)體請(qǐng)實(shí)驗(yàn)：1.將b定義為int型看看執(zhí)行結(jié)果并分析為什么2.將1e-6變?yōu)?e-7或1e-4看看結(jié)果提問：這種循環(huán)當(dāng)表達(dá)式的值永遠(yuǎn)為真時(shí)，會(huì)如何？27下面還要介紹另一種循環(huán)“當(dāng)循環(huán)”一般形式： while(表達(dá)式) { 語句塊；(循環(huán)體) }28

while(表達(dá)式){

語句塊（循環(huán)體）;}29思考#defineN1while(N){cout<<“welcometoTsinghua\n“;}程序運(yùn)行后會(huì)出現(xiàn)什么情況?30思考#defineN1while(N-1){cout<<“welcometoTsinghua\n“;}程序運(yùn)行后會(huì)出現(xiàn)什么情況?31

作業(yè)比較3種循環(huán)語句各有什么特點(diǎn)?題目：某選手10000m跑的每400m用時(shí)記錄在名為RUN的數(shù)組中，請(qǐng)你計(jì)算平均用時(shí)（每400m的平均用時(shí)）,要求使用3種循環(huán)語句來編程。1.for2.do…while3.while32舉例求兩個(gè)整數(shù)的最小公倍數(shù)33分析：假定有x,y且x>y，設(shè)最小公倍數(shù)為z1.z一定會(huì)>=x2.z=kx,k=1,2,…3.z一定會(huì)被y整除用兩個(gè)最簡單的數(shù)試一下就可以找到算法.比如x=5,y=3.34第一步z=x=5 5%3!=0//z%y不能整除第二步z=z+x=10 10%3!=0//z%y

不能整除第三步z=z+x=15 15%3==0//z%y

能整除找到了z，15就是5和3的最小公倍數(shù)35//************************************//*程序名：5_3.cpp*//*作者：wuwh*//*編制時(shí)間：2002年9月20日*//*主要功能：求兩個(gè)數(shù)的最小共倍數(shù)*//************************************#include<iostream.h>#include<math.h>voidmain() //主函數(shù){ intx=0,y=0,z=0,w=0;//整型變量

cout<<“請(qǐng)輸入兩個(gè)整數(shù)，用空格隔開：”;//提示信息 cin>>x; //鍵盤輸入整數(shù)x cin>>y; //鍵盤輸入整數(shù)y if(x<y) //讓x表示兩者中的大數(shù)

{ w=x;x=y;y=w; } z=x; //將一個(gè)大數(shù)賦給z while(z%y!=0) //當(dāng)z不能被y整除時(shí)，就讓z累加x z=z+x; cout<<"最小公倍數(shù)為"<<z<<endl; //輸出最小公倍數(shù)}36cout<<“請(qǐng)輸入兩個(gè)整數(shù)，用空格隔開：”;//提示信息 cin>>x; //鍵盤輸入整數(shù)x cin>>y; //鍵盤輸入整數(shù)y if(x<y) //讓x表示兩者中的大數(shù)

{ w=x;x=y;y=w; }37

z=x; //將一個(gè)大數(shù)賦給z//當(dāng)z不能被y整除時(shí)，就讓z累加xwhile(z%y!=0) {z=z+x;}cout<<"最小公倍數(shù)為"<<z<<endl; 38 請(qǐng)同學(xué)們?nèi)ケ容^三種循環(huán)的異同之處1.for循環(huán)（計(jì)數(shù)型循環(huán)） 2.當(dāng)型循環(huán)（while循環(huán)）3.直到型循環(huán)（dowhile循環(huán)）上機(jī)將挑肥羊的程序和篩出素?cái)?shù)的程序完成自學(xué)與比較39排序問題40問題：將幾個(gè)數(shù)從大到小排序并輸出，介紹冒泡排序法4142從表中可以看出最小的一個(gè)數(shù)第一遍掃描就交換到a[6]中。如果將a[1]視為水底，a[6]視為水面：最輕的(最小的)一個(gè)數(shù)1最先浮到水面，交換到a[6];次輕的2第二遍掃描交換到a[5]；再輕的3第三遍掃描交換到a[4]； …依此類推，有6個(gè)數(shù)，前5個(gè)數(shù)到位需5遍掃描，第6個(gè)最重的數(shù)自然落在a[1]中。因此，6個(gè)數(shù)只需5遍掃描，即j=n-1,n=6。冒泡排序算法分析：43再看在每遍掃描中，相鄰兩數(shù)組元素的比較次數(shù)。當(dāng)j=1時(shí)，i=1,2,…,n-j。n=6時(shí)，比較5次之后a[6]中有一個(gè)最小數(shù)到達(dá)，這時(shí)a[6]不必再參與比較了。因此在第二遍搜索時(shí)，j=2,i=1,2,…,n-j，即i=1,2,3,4。比較4次之后次小的一個(gè)數(shù)到達(dá)了a[5]。這時(shí)a[5]不必再參與比較了。因此，j=3時(shí)，i=1,2,3；j=4時(shí)，i=1,2；j=5時(shí)，i=1。理出上述規(guī)律后，程序就不難編了44為了表述方便，定義以下3個(gè)變量：n——待排序的數(shù)的個(gè)數(shù)，這里n=6

j——掃描遍數(shù)，j=1,2,…,n-1

i——第j遍掃描待比較元素的下標(biāo)，i=1,2,…,n-j冒泡排序算法設(shè)計(jì)：45采用兩重計(jì)數(shù)型循環(huán)：步驟1：將待排序的數(shù)據(jù)放入數(shù)組中；步驟2：置j為1；步驟3：讓i從1到n-j，比較a[i]與a[i+1]， 如果a[i]>=a[i+1]，位置不動(dòng)； 如果a[i]<a[i+1]，位置交換， 步驟3結(jié)束后a[n-j+1]中的數(shù)為最小的數(shù)步驟4：讓j=j+1,只要j!=n就返回步驟3 當(dāng)j==n時(shí)執(zhí)行步驟5步驟5：輸出排序結(jié)果46//************************************//*程序名：5_4.cpp*//*作者：wuwh*//*編制時(shí)間：2002年9月22日*//*主要功能：冒泡排序*//************************************#include<iostream.h> //預(yù)編譯命令#include<memory.h> //預(yù)編譯命令voidmain() //主函數(shù){ inti=0,j=0,p=0,a[7]; //整型變量 memset(a,0,sizeof(a)); //整型數(shù)組初始化

for(i=1;i<=6;i++) //鍵入6個(gè)數(shù)，放入a數(shù)組中