C++第八課一維數(shù)組.ppt

1、一維數(shù)組,第8課,怎樣用以學(xué)過知識(shí)解決下列問題,輸入N個(gè)數(shù),要求反向輸出這N個(gè)數(shù). 例如:輸入 5 4 5 3 9 1 輸出 1 9 3 5 4,分析,在解決這個(gè)問題時(shí)，要把很多數(shù)據(jù)保存下來，如果用以前的方法定義變量很麻煩，我們可以批量定義變量。最常用的方法是定義數(shù)組來解決。 int a10; a是數(shù)組名，10表示有10個(gè)變量，分別是 a0、a1、a9,且每個(gè)值取整型。,例1:輸入N(N10)個(gè)數(shù),要求反向輸出這N個(gè)數(shù). 例如:輸入 5 4 5 3 9 1 輸出 1 9 3 5 4,定義數(shù)組:int a10;,輸入: cinn; for (i=0;iai;,輸出: for (i=n-1;i=0

2、;i-) coutai;,一維數(shù)組的初始化,在定義數(shù)組時(shí)對(duì)數(shù)組元素賦以初值。例如： int a10=0,1,2,3,4,5,6,7,8,9; 可以只給一部分元素賦初值。例如： int a10=0,1,2,3,4; 在對(duì)全部數(shù)組元素賦初值時(shí)，可以不指定數(shù)組長(zhǎng)度。例如： int a=1,2,3,4,5 兩個(gè)數(shù)組轉(zhuǎn)存，要用循環(huán)一一導(dǎo)入，不能直接賦值。 for (i=0;in;i+) ai=bi;,例2求不達(dá)均分的人數(shù) （P1057） 輸入n個(gè)(n=10)學(xué)生的成績(jī)，統(tǒng)計(jì)有多少人的分?jǐn)?shù)低于平均分。 樣例：輸入：4 n=4,表示有4個(gè)人的成績(jī) 80 88 44 90 輸出： 1 只有1個(gè)人的分?jǐn)?shù)低于平均

3、分,1、先定義數(shù)組ai用來存放n個(gè)人的分?jǐn)?shù)。 存入總分、均分的變量。 2、輸入部分：在輸入的過程中可以順便統(tǒng)計(jì)一下總分。 3、計(jì)算均分 4、統(tǒng)計(jì)低于均分的人數(shù)。 5、輸出。,P1072陶陶摘蘋果,第一個(gè)應(yīng)用：進(jìn)制轉(zhuǎn)換,例3將一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)化為二進(jìn)制數(shù). 分析:例如將十進(jìn)制數(shù)12轉(zhuǎn)化為二進(jìn)制數(shù),方法如下:,把十進(jìn)制數(shù)除以2, 用一個(gè)數(shù)組a來存放余數(shù),將商作為新的數(shù)繼續(xù)除以2,反復(fù)進(jìn)行,一直除到商為0時(shí)停止。 輸出：將a組數(shù)反向輸出,cinx; k=0; while ( ) k=k+1; /K是數(shù)組的下標(biāo)指針 ak=x% 2; x=x / 2; for ( ) coutai;,P1098 十六進(jìn)

4、制中10用A表示，11用B. P1099,第二個(gè)應(yīng)用：選擇排序例4：選擇排序:將n個(gè)整數(shù)按由小到大的順序輸出。樣例：輸入：6 表示有6個(gè)數(shù) 5 7 4 3 8 6 輸出: 3 4 5 6 7 8,假設(shè)6個(gè)數(shù)據(jù)是：a=5 7 4 3 8 6 ，我們把1號(hào)位放最小數(shù)，就從2號(hào)位開始，一一與1號(hào)位比較，如果比它小，則交換，這樣做到6號(hào)位，就使得1號(hào)位存放一個(gè)最小的數(shù)，下面再把2號(hào)位放次小的數(shù)，從3號(hào)位開始比較，以此類推，直至n-1號(hào)位。如： a1 a2 a3 a4 a5 a6 5 7 4 3 8 6 5 7 4 3 8 6 a1與a2比較，不交換 5 7 4 3 8 6 a1與a3比較，交換 4 7

5、 5 3 8 6 a1與a4比較，交換 3 7 5 4 8 6 a1與a5比較，不交換 a1與a6比較，不交換 這時(shí)，a1就是最小的一個(gè)數(shù)，下面再進(jìn)行確定a2，方法同樣，最后確定a5，a6不必確定。,參考程序如下:,cinn; int an+5; /多定義幾個(gè) for (i=1;iai; for (i=1;iaj) swap(ai,aj); for (i=1; i=n;i+) coutai“ “;,使用swap交換函數(shù)必須使用頭文件#include 使用sort max min count函數(shù)也要使用這個(gè)頭文件。 直接用sort 函數(shù)排序 如果數(shù)組a0-an-1 sort(a,a+n) 如果數(shù)

6、組a1-an sort(a+1,a+n+1),sort(a+1,a+n+1),排序練習(xí),P1102 排序默認(rèn)的是由小到大排序，查名次的時(shí)候應(yīng)該從后往前。 for (i=n;i=1;i-) if (ai=x) break; cout?;,P1124 最好不使用sort 排序，選擇排序比較的時(shí)候要注意兩種情況都交換： a數(shù)組存編號(hào) b數(shù)組存值，比較的時(shí)候： if (biaj) 輸出的時(shí)候，每行要輸出三個(gè)數(shù)。,基數(shù)排序,例7：將n個(gè)小于100的不同的正整數(shù)進(jìn)行從小到大排序。 樣例：輸入： 5 4 3 5 6 1 輸出：1 3 4 5 6 采用選擇排序的運(yùn)算次數(shù)是n2，可以采用另外一種方法： cinn

7、; for (i=1;ix; ax=1; for (i=1;i0) couti“ “;,如果有相同的，則做一些改動(dòng)：ax+;在輸出的時(shí)候當(dāng)ai1 的時(shí)候，必須全部輸出。 優(yōu)點(diǎn)：時(shí)間復(fù)雜度O(n)。 弱點(diǎn)：必須要知道數(shù)據(jù)的范圍，且是整數(shù)。,練習(xí) P1097 明明的隨機(jī)數(shù) 分析：如果采用一般的模擬方法來做，很麻煩，直接使用基數(shù)排序法。 P1096 用上述類似的方法。 數(shù)組的值開始都是0； 移走的，將數(shù)組的值變成1。 最后統(tǒng)計(jì)還有多少個(gè)值是0。,基數(shù)排序的運(yùn)用,P1101 P1096 數(shù)組定義在函數(shù)外，默認(rèn)值為0 讀一對(duì)數(shù)，將數(shù)組中的這一部分變?yōu)? 最后統(tǒng)計(jì)數(shù)組中還有多少個(gè)數(shù)是0.,P1129 十個(gè)

8、數(shù)的操作 a x輸入 三種情況：(1)輸出NO: if (x=a10) else for (i=1;i=x) break; /第i位數(shù)有可能等于或大于 if (ai=x) 第（2）種情況 else 第（3）種情況 ,第（2）種情況： 將第i位刪除 方法：從i位到n-1位，前面一位取后面一位的值。 for (j=i;j=i+1;j-) aj=aj-1; for (i=1;i=11;i+) coutai ;,約瑟夫問題：設(shè)有N個(gè)人依次圍成一圈, 從第1個(gè)人起開始報(bào)數(shù), 報(bào)到M的人出列,下一個(gè)人再?gòu)?起報(bào)數(shù),報(bào)到M的人出列, 下一個(gè)人再?gòu)?起報(bào)數(shù),如此繼續(xù), 直到所有人均出列為止. 設(shè)N個(gè)人的編號(hào)為

9、1,2,.,N, 打印出出列的次序。例如：輸入：N=6，M=3，則輸出出列的順序是：3 6 4 2 5 1,int i=0; ai初始化為1；/ai=1表示i在圈上。 for (j=1;jn) i=1; p=p+ai; while (p!=m); /報(bào)一輪的模擬 ai=0; couti“ “; /輸出，同時(shí)將這個(gè)人出圈 ,P1125,高精度算法 P1870,a100=1; b100=1；a數(shù)組作為1！，b數(shù)組存放和 for (i=2; i=n;i+) 求i的階乘:a *i,結(jié)果用a數(shù)組存放； 求a +b ，結(jié)果用b數(shù)組存放； 輸出：b數(shù)組的結(jié)果。,1 2 3 95 96 97 98 99 100,+,1,1,1,0,0,加法過程 g=0; 進(jìn)率初始為0 for(i=maxn; i=1;i-) s=ai+bi+g; ai=s % 10; g=s / 10; ,0,a,s,g,輸出部分： i=1; while （ai=0 ,高精度*單精度,輸入時(shí)的第一個(gè)數(shù)用數(shù)組存放，而第二個(gè)數(shù)直接用一個(gè)整型變量存放。,1 2 97 98 99 100,a,b,*,S,乘法過程 g=0; 進(jìn)率初始為