【公開(kāi)課課件】第5章數(shù)組(C版)

1、第五章第五章 數(shù)組數(shù)組 第一節(jié)第一節(jié) 一維數(shù)組一維數(shù)組第二節(jié)第二節(jié) 二維數(shù)組二維數(shù)組第三節(jié)第三節(jié) 字符數(shù)組和字符串類型字符數(shù)組和字符串類型第一節(jié)第一節(jié) 一維數(shù)組一維數(shù)組一、為什么要使用數(shù)組通過(guò)前面幾章的學(xué)習(xí)，我們已經(jīng)可以編寫(xiě)程序來(lái)解決各種相當(dāng)復(fù)雜的問(wèn)題了，但是當(dāng)需要處理的數(shù)據(jù)比較多時(shí)，僅依靠前面的知識(shí)是不夠的，即使簡(jiǎn)單的問(wèn)題也可能需要比較復(fù)雜的程序來(lái)處理。請(qǐng)看下面的例子：例題：輸入50個(gè)學(xué)生的某門(mén)課程的成績(jī)，打印出低于平均分的學(xué)生序號(hào)與成績(jī)。【分析】在解決這個(gè)問(wèn)題時(shí)，雖然可以通過(guò)一個(gè)變量來(lái)累加讀入的50個(gè)成績(jī)求出學(xué)生的總分，進(jìn)而求出平均分。但因?yàn)橹挥凶x入最后一個(gè)學(xué)生的分?jǐn)?shù)后才能求得平均分，并且

2、要求打印出低于平均分的學(xué)生序號(hào)和成績(jī)，故必須把50個(gè)學(xué)生的成績(jī)都保留起來(lái)，然后逐個(gè)和平均分比較，把低于平均分的成績(jī)打印出來(lái)。如果，用簡(jiǎn)單變量a1，a2,，a50存儲(chǔ)這些數(shù)據(jù)，要用50個(gè)變量保存輸入的數(shù)據(jù)，程序片斷如下：cina1a2a10;cina41a42a50;注意，如果真正要像上面這樣編寫(xiě)程序，則上面的所有省略號(hào)必須用完整的語(yǔ)句寫(xiě)出來(lái)?？梢钥闯觯@樣的程序是多么繁瑣。如果說(shuō)處理的數(shù)據(jù)規(guī)模達(dá)到成千上萬(wàn)，上面的例子單單讀入就會(huì)異常復(fù)雜，電腦的優(yōu)勢(shì)沒(méi)有得到體現(xiàn)。從以上的討論可以看出，如果只使用簡(jiǎn)單變量處理大量數(shù)據(jù)，就必須使用大量只能單獨(dú)處理的變量，即使是簡(jiǎn)單問(wèn)題也需要編寫(xiě)冗長(zhǎng)的程序。選手們可能

3、已經(jīng)看出，我們需要把一大批具有相同性質(zhì)的數(shù)據(jù)組合成一個(gè)新類型的變量，可以用簡(jiǎn)單的程序（比如循環(huán)50次）對(duì)這個(gè)新變量的各個(gè)分量進(jìn)行相同的處理，每個(gè)分量仍然保留單個(gè)變量的所有性質(zhì)（在上面的例子中，各分量是整型變量或?qū)嵭妥兞康男再|(zhì)）。如果能像數(shù)學(xué)中使用下標(biāo)變量ai形式表示這50個(gè)數(shù)，則問(wèn)題就容易實(shí)現(xiàn)。在C+語(yǔ)言中，具有下標(biāo)性質(zhì)的數(shù)據(jù)類型是數(shù)組。如果使用數(shù)組，上面的問(wèn)題就變得十分簡(jiǎn)單、清晰。例如，讀入50個(gè)學(xué)生的成績(jī)，只需寫(xiě)如下語(yǔ)句即可： for (int i=1;iai;在這里引用了帶下標(biāo)的變量（分量變量稱為數(shù)組元素）ai來(lái)代替a1,a2,a50,方括號(hào)中的i稱為下標(biāo)，當(dāng)循環(huán)變量i=1時(shí)ai就是a1

4、；當(dāng)i=2時(shí)ai就是a2；當(dāng)i=50時(shí)ai就是a50。輸入的時(shí)候，讓i從1變化到50，循環(huán)體內(nèi)輸入語(yǔ)句中的ai也就分別代表了a1,a2,a50這50個(gè)帶下標(biāo)的變量。這樣上述問(wèn)題的程序可寫(xiě)為：int tot = 0;/ tot存儲(chǔ)50個(gè)學(xué)生的總分for (int i=1;iai; tot+=ai;float ave= tot/50; /計(jì)算平均分for (int i=1;i=50;+i)if (aiave) coutNo. i ai;/如果第i個(gè)同學(xué)成績(jī)小于平均分，則將輸出這個(gè)學(xué)生的序號(hào)和成績(jī)。 要在程序中使用下標(biāo)變量，必須先說(shuō)明這些下標(biāo)變量的整體為數(shù)組，即數(shù)組是若干個(gè)同名（如上面的下標(biāo)變量的名

5、字都為a）下標(biāo)變量的集合，這些變量的類型全部一致。二、一維數(shù)組的定義當(dāng)數(shù)組中每個(gè)元素只帶有一個(gè)下標(biāo)時(shí)，我們稱這樣的數(shù)組為一維數(shù)組。數(shù)組的定義格式如下：類型標(biāo)識(shí)符 數(shù)組名常量表達(dá)式說(shuō)明：數(shù)組名的命名規(guī)則與變量名的命名規(guī)則一致。常量表達(dá)式表示數(shù)組元素的個(gè)數(shù)?？梢允浅Ａ亢头?hào)常量，但不能是變量。例如：int a10; /數(shù)組a定義是合法的 int bn; /數(shù)組b定義是非法的 其中，a是一維數(shù)組的數(shù)組名，該數(shù)組有10個(gè)元素，依次表示為：a0,a1,a2,a3,a4,a5，a6,a7,a8,a9。需要注意的是：a10不屬于該數(shù)組的空間范圍。當(dāng)在說(shuō)明部分定義了一個(gè)數(shù)組變量之后,C+編譯程序?yàn)樗x的數(shù)組

6、在內(nèi)存空間開(kāi)辟一串連續(xù)的存儲(chǔ)單元，每個(gè)數(shù)組第一個(gè)元素的下標(biāo)都是0，因此第一個(gè)元素為第0個(gè)數(shù)組元素。例如：上例中的a數(shù)組在內(nèi)存的存儲(chǔ)如表所示： a數(shù)組共有10個(gè)元素組成，在內(nèi)存中10個(gè)數(shù)組元素共占10個(gè)連續(xù)的存儲(chǔ)單元。a數(shù)組最小下標(biāo)為0，最大下標(biāo)9。按定義a數(shù)組所有元素都是整型變量。a0 a1 a2 a3 a4 a5 a6 a7 a8 a9三、一組數(shù)組的引用三、一組數(shù)組的引用 通過(guò)給出的數(shù)組名稱和這個(gè)元素在數(shù)組中的位置編號(hào)(即下標(biāo))，程序可以引用這個(gè)數(shù)組中的任何一個(gè)元素。 一維數(shù)組元素的引用格式：一維數(shù)組元素的引用格式： 數(shù)組名數(shù)組名下標(biāo)下標(biāo)例如：若i、j都是int型變量，則 a5 ai+j a

7、i+ 都是合法的元素。說(shuō)明：說(shuō)明： (1)下標(biāo)可以是任意值為整型的表達(dá)式，該表達(dá)式里可以包含變量和函數(shù)調(diào)用。引用時(shí)，下標(biāo)值應(yīng)在數(shù)組定義的下標(biāo)值范圍內(nèi)。 (2)數(shù)組的精妙在于下標(biāo)可以是變量，通過(guò)對(duì)下標(biāo)變量值的靈活控制，達(dá)到靈活處理數(shù)組元素的目的。 (3)C+語(yǔ)言只能逐個(gè)引用數(shù)組元素，而不能一次引用整個(gè)數(shù)組。(4)數(shù)組元素可以像同類型的普通變量那樣使用，對(duì)其進(jìn)行賦值和運(yùn)算的操作，和普通變量完全相同。例如： c10=34;實(shí)現(xiàn)了給c10賦值為34。四、一維數(shù)組的初始化 數(shù)組的初始化可以在定義時(shí)一并完成。格式： 類型標(biāo)識(shí)符 數(shù)組名常量表達(dá)式=值1，值2，例如：int a5=1,2,3,4,5說(shuō)明：(1

8、)在初值列表中可以寫(xiě)出全部數(shù)組元素的值，也可以寫(xiě)出部分。例如，以下方式可以對(duì)數(shù)組進(jìn)行初始化：int x10=0,1,2,3,4;該方法僅對(duì)數(shù)組的前5個(gè)元素依次進(jìn)行初始化，其余值為0。(2)對(duì)數(shù)組元素全部初始化為0，可以簡(jiǎn)寫(xiě)為：。例如： int a5=; 將數(shù)組a的5個(gè)元素都初始化為0?！菊f(shuō)明說(shuō)明】 程序1、程序2和程序3的區(qū)別在于數(shù)組定義在int main()之外與之內(nèi)，程序1中數(shù)組定義放在int main()之外，其初始值是0值。程序2中數(shù)組定義放在int main()之內(nèi)，其初始值是隨機(jī)的。程序2中數(shù)組定義放在int main()之內(nèi)，只給a0、a1賦初值，但后面的a2a4元素自動(dòng)賦0值。

9、五、數(shù)組越界五、數(shù)組越界 C+語(yǔ)言規(guī)定，使用數(shù)組時(shí)，要注意： (1)、數(shù)組元素的下標(biāo)值為非負(fù)整數(shù)。 (2)、在定義元素個(gè)數(shù)的下標(biāo)范圍內(nèi)使用。 然而，當(dāng)在程序中把下標(biāo)寫(xiě)成負(fù)數(shù)、大于數(shù)組元素的個(gè)數(shù)時(shí)，程序編譯的時(shí)候是不會(huì)出錯(cuò)的。例如： int a10; a-3=5; a20=15; a10=20; int k=a30 這些語(yǔ)句的語(yǔ)法是正確的，能夠通過(guò)程序的編譯。然而，它們要訪問(wèn)的數(shù)組元素并不在數(shù)組的存儲(chǔ)空間的，這種現(xiàn)象叫數(shù)組越界。例如下面程序：#includeusing namespace std; int main() int a5; for (int i=0;i=10;i+) ai=i; co

10、utai ; return 0;【說(shuō)明說(shuō)明】 該程序能夠通過(guò)編譯，也能運(yùn)行出結(jié)果，程序的問(wèn)題是定義a5，使用時(shí)數(shù)組下標(biāo)超過(guò)了4。C+語(yǔ)言中，數(shù)組越界訪問(wèn)系統(tǒng)時(shí)不一定會(huì)給出任何的提示，也就是說(shuō)，程序可以超出數(shù)組邊界進(jìn)行讀/寫(xiě)，從而造成內(nèi)存的混亂。 數(shù)組越界是實(shí)際編程中常見(jiàn)的錯(cuò)誤，而且這類錯(cuò)誤往往難以捕捉。因?yàn)樵浇缯Z(yǔ)句本身并不一定導(dǎo)致程序立即出錯(cuò)，可能在遇到某些數(shù)據(jù)時(shí)才導(dǎo)致錯(cuò)誤，有時(shí)由于越界，意外地改變了變量或指令，導(dǎo)致在調(diào)試器里調(diào)試的時(shí)候，程序不按照應(yīng)當(dāng)?shù)拇涡蜻\(yùn)行的怪現(xiàn)象。六、一維數(shù)組的應(yīng)用例5.1 輸入n個(gè)數(shù),要求程序按輸入時(shí)的逆序把這n個(gè)數(shù)打印出來(lái)，已知整數(shù)不超過(guò)100個(gè)。也就是說(shuō)，按輸入相

11、反順序打印這n個(gè)數(shù)?！痉治觥课覀兛啥x一個(gè)數(shù)組a用以存放輸入的n個(gè)數(shù), 然后將數(shù)組a中的內(nèi)容逆序輸出。#include#includeint a100;int a100;int main()int main() int x,n=0;int x,n=0; while(scanf(%d,&x)=1)while(scanf(%d,&x)=1) an+=x; an+=x; /相當(dāng)相當(dāng)an=x;n+;an=x;n+; for (int i=n-1;i=1;-i)for (int i=n-1;i=1;-i) printf(%d ,ai); printf(%d ,ai); /注意注意%d%d

12、后面有一個(gè)空格，保證行首行尾均無(wú)空格后面有一個(gè)空格，保證行首行尾均無(wú)空格 printf(%dn,a0);printf(%dn,a0); return 0;return 0; 【說(shuō)明】： 語(yǔ)句int a100聲明了一個(gè)包含100個(gè)整型變量的數(shù)組，它們是：a0，a1，a2，a99。注意，沒(méi)有a100。在上述程序中，數(shù)組a被聲明在main函數(shù)的外面。只有放在外面時(shí)，數(shù)組a才可以開(kāi)得很大；放在main函數(shù)內(nèi)時(shí)，數(shù)組稍大就會(huì)異常退出。它的道理將在后面討論，只需要記住規(guī)則即可。 數(shù)組不能夠進(jìn)行賦值操作：如果聲明的是int aMAXN，bMAXN,是不能賦值b=a的(Pascal語(yǔ)言可以的)。如果要從數(shù)組a

13、復(fù)制k個(gè)元素到數(shù)組b，可以這樣做：memcpy(b,a,sizeof(int)*k)。當(dāng)然了，如果數(shù)組a和b都是浮點(diǎn)型的，復(fù)制時(shí)要寫(xiě)成memcpy(b,a,sizeof(double)*k)。如果需要把數(shù)組a全部復(fù)制到數(shù)組b中，可以寫(xiě)得簡(jiǎn)單一些：memcpy(b,a,sizeof(a)。使用memcpy函數(shù)要包含頭文件cstring。 例5.2 將a數(shù)組中第一個(gè)元素移到數(shù)組末尾,其余數(shù)據(jù)依次往前平移一個(gè)位置?！痉治觥繛橥瓿深}目所要求的操作，其算法應(yīng)該包括以下幾個(gè)主要步驟： 把第一個(gè)元素的值取出放在一個(gè)臨時(shí)單元 temp中； 通過(guò) a2a1, a3a2, a4a3， anan-1,實(shí)現(xiàn)其余元素前

14、移 將 temp值送入an. #include#include /調(diào)用setw函數(shù)需注明使用該庫(kù)const int n=10;using namespace std; int an,temp; int main() coutread n datasendl;for (int i=0; iai;temp=a0;for (int i=0; in-1; +i) ai=ai+1;an-1=temp;coutResult:endl;for (int i=0; in; +i) coutsetw(3)ai; /setw函數(shù)控制輸出場(chǎng)寬return 0; 運(yùn)行結(jié)果 : read 10 datas: 1 2 3

15、 4 5 6 7 8 9 10 Result: 2 3 4 5 6 7 8 9 10 1 例5.3 賓館里有一百個(gè)房間，從1-100編了號(hào)。第一個(gè)服務(wù)員把所有的房間門(mén)都打開(kāi)了，第二個(gè)服務(wù)員把所有編號(hào)是2的倍數(shù)的房間“相反處理”，第三個(gè)服務(wù)員把所有編號(hào)是3的倍數(shù)的房間作“相反處理”，以后每個(gè)服務(wù)員都是如此。當(dāng)?shù)?00個(gè)服務(wù)員來(lái)過(guò)后，哪幾扇門(mén)是打開(kāi)的。（所謂“相反處理”是：原來(lái)開(kāi)著的門(mén)關(guān)上，原來(lái)關(guān)上的門(mén)打開(kāi)。）【分析】此題較簡(jiǎn)單，用a1,a2,an表示編號(hào)為1，2，3，,n的門(mén)是否開(kāi)著。模擬這些操作即可，參考程序如下：#include#include#define MAXN 100+10int a

16、MAXN;int main()int n,k,first=1;memset(a,0,sizeof(a); for (int i=1;i=100;+i) for (int j=1;j=100;+j) if (j%i=0) aj=!aj;for (int i=1;i=100;+i) if (ai) if(first) first=0; else printf( ); printf(%d,i); printf(n);return 0;運(yùn)行結(jié)果：14 9 16 25 36 49 64 81 100【說(shuō)明】： memset(a,0,sizeof(a)的作用是把數(shù)組a清零，它在cstring中定義。雖然也

17、能用for循環(huán)完成相同的任務(wù)，但是用memset又方便又快捷。另一個(gè)技巧在輸出：為了避免輸出多余空格，設(shè)置了一個(gè)標(biāo)志變量first，可以表示當(dāng)前要輸出是否為第一個(gè)。第一個(gè)變量前不應(yīng)該有空格，但其他都有。例5.4 約瑟夫問(wèn)題：N個(gè)人圍成一圈，從第一個(gè)人開(kāi)始報(bào)數(shù)，數(shù)到M的人出圈；再由下一個(gè)人開(kāi)始報(bào)數(shù)，數(shù)到M的人出圈；輸出依次出圈的人的編號(hào)。N，M由鍵盤(pán)輸入?！痉治觥?（1）由于對(duì)于每個(gè)人只有出圈和沒(méi)有圈兩種狀態(tài)，因此可以用布爾型標(biāo)志數(shù)組存儲(chǔ)游戲 過(guò)程中每個(gè)人的狀態(tài)。不妨用true表示出圈，false 表示沒(méi)有出圈。 （2）開(kāi)始的時(shí)候，給標(biāo)志數(shù)組賦初值為false，即全部在圈內(nèi)。 （3）模擬報(bào)數(shù)游戲

18、的過(guò)程，直到所有的人出圈為止。程序如下：#includeusing namespace std;int n,m,s,f,t;bool a101;/根據(jù)題意開(kāi)出數(shù)組大小int main() cinnm;/共n人，報(bào)到m出圈 coutendl; for (t=1;t=n;+t) at=false; /等同于memset(a,0,sizeof(a),要調(diào)用cstring庫(kù) f=0; t=0; s=0; /剛開(kāi)始所有變量默認(rèn)值也是0,或者用f=t=s=0; do +t;/逐個(gè)枚舉圈中的所有位置 if (t=n+1) t=1;/數(shù)組模擬環(huán)狀，最后一個(gè)與第一個(gè)相連 if (at=false) +s;/第t

19、個(gè)位置上有人則報(bào)數(shù) if (s=m) /當(dāng)前報(bào)的數(shù)是m s=0;/計(jì)數(shù)器清零 coutt ;/輸出出圈人的編號(hào) at=true;/此處的人已出圈，設(shè)置為空 f+; /出圈的人數(shù)增加一個(gè) while(f!=n);/直到所有的人都出圈為止 return 0;運(yùn)行結(jié)果：輸入： 8 5輸出： 5 2 8 7 1 4 6 3這是一個(gè)在算法設(shè)計(jì)上很有名氣的經(jīng)典約瑟夫（Josephu）問(wèn)題，它有很多變例。如猴子選大王、持密碼報(bào)數(shù)、狐貍追兔子等（見(jiàn)上機(jī)練習(xí)）。例例5.5 5.5 輸入輸入n n個(gè)整數(shù)個(gè)整數(shù), ,存放在數(shù)組存放在數(shù)組a1a1至至anan 中，輸出最大數(shù)中，輸出最大數(shù)所在位置所在位置(n=1000

20、0)(n=10000)。輸入樣例：輸入樣例： 5 67 43 90 78 32輸出樣例：輸出樣例： 3 【分析分析】設(shè)maxa存放最大值，k存放對(duì)應(yīng)最大值所在的數(shù)組位置，maxa的初值為a1，k的初值對(duì)應(yīng)為1，枚舉數(shù)組元素，找到比當(dāng)前maxa大的數(shù)成為maxa的新值，k值為對(duì)應(yīng)位置，輸出最后的k值。程序如下程序如下：#include using namespace std;const int MAXN=10001;int main()int aMAXN; /定義10001個(gè)數(shù)組 int i,n,maxa,k;cinn;for (i=1;iai; /讀入n個(gè)存到a1-an中 maxa=a1;k=

21、1; /賦最大值初值和初始位置 for(i=2;imaxa) /枚舉數(shù)組，找到最大數(shù)和位置 maxa=ai;k=i; coutk; /輸出最大數(shù)所在數(shù)組中的位置 return 0;例例5.6 編程輸入十個(gè)正整數(shù)，然后自動(dòng)按從大到小的順序輸出。（冒泡排序）編程輸入十個(gè)正整數(shù)，然后自動(dòng)按從大到小的順序輸出。（冒泡排序）【問(wèn)題分析問(wèn)題分析】 用循環(huán)把十個(gè)數(shù)輸入到A數(shù)組中； 從a1到a10，相鄰的兩個(gè)數(shù)兩兩相比較，即： a1與a2比，a2與a3比，a9與a10比。 只需知道兩個(gè)數(shù)中的前面那元素的標(biāo)號(hào)，就能進(jìn)行與后一個(gè)序號(hào)元素（相鄰數(shù)）比較，可寫(xiě)成通用形式ai與ai+1比較，那么，比較的次數(shù)又可用1(

22、n-i )循環(huán)進(jìn)行控制(即循環(huán)次數(shù)與兩兩相比較時(shí)前面那個(gè)元素序號(hào)有關(guān)) ； 在每次的比較中，若較大的數(shù)在后面，就把前后兩個(gè)對(duì)換，把較大的數(shù)調(diào)到前面，否則不需調(diào)換位置。下面例舉5個(gè)數(shù)來(lái)說(shuō)明兩兩相比較和交換位置的具體情形： 5 6 4 3 7 5和6比較，交換位置，排成下行的順序； 6 5 4 3 7 5和4比較，不交換，維持同樣的順序； 6 5 4 3 7 4和3比較，不交換，順序不變 6 5 4 3 7 3和7比較，交換位置，排成下行的順序； 6 5 4 7 3 經(jīng)過(guò)（1（n-1）次比較后，將3調(diào)到了末尾。 經(jīng)過(guò)第一輪的1 (N-1)次比較，就能把十個(gè)數(shù)中的最小數(shù)調(diào)到最末尾位置，第二輪比較1

23、(N-2)次進(jìn)行同樣處理，又把這一輪所比較的“最小數(shù)”調(diào)到所比較范圍的“最末尾”位置；每進(jìn)行一輪兩兩比較后，其下一輪的比較范圍就減少一個(gè)。最后一輪僅有一次比較。在比較過(guò)程中，每次都有一個(gè)“最小數(shù)”往下“掉”，用這種方法排列順序，常被稱之為“冒泡法”排序。程序如下程序如下：#includeusing namespace std;const int n=10;int an+1;/定義數(shù)組int main() for (int i=1; iai;/輸入十個(gè)數(shù) for (int i=1; i=n-1; +i)/冒泡法排序 for (int j=1; j=n-i; +j) /兩兩相比較 if (ajaj

24、+1) swap(aj,aj+1); /比較與交換 for (int i=1; i=n; +i) cout ai; /輸出排序后的十個(gè)數(shù) coutendl; return 0;運(yùn)行結(jié)果：運(yùn)行結(jié)果：輸入： 2 5 8 6 12 34 65 22 16 55輸出： 65 55 34 22 16 12 8 6 5 2例5.7 用篩法求出100以內(nèi)的全部素?cái)?shù)，并按每行五個(gè)數(shù)顯示?！締?wèn)題分析】質(zhì)數(shù)篩法是這樣的：質(zhì)數(shù)篩法是這樣的：1開(kāi)一個(gè)大的bool型數(shù)組prime，大小就是n+1就可以，先把所有的下標(biāo)為true。2然后：for( i=2; i=sqrt(n);+i ) if(primei) for( j

25、=2; jsqrt(30)算法結(jié)束。第 3 步把prime值為true的下標(biāo)輸出來(lái)：結(jié)果是 2 3 5 7 11 13 17 19 23 29程序如下：#include#include /在Dev C+中可調(diào)用數(shù)學(xué)函數(shù)庫(kù)cmath#includeusing namespace std;const int n=100;bool primen+1;int main() for (int i=0; i=n; +i) primei=true; /等同于memset(prime,1,sizeof(prime) prime1=false; for (int i=2; i=sqrt(n); +i) if (

26、primei) for (int j=2; j=n/i; +j) primei*j=false; for (int i=2,t=0; i=n; +i) if (primei) coutsetw(5)i; +t; if (t%5=0) coutendl; return 0;【上機(jī)練習(xí)】1、與指定數(shù)字相同的數(shù)的個(gè)數(shù)【1.6編程基礎(chǔ)之一維數(shù)組01】 輸出一個(gè)整數(shù)序列中與指定數(shù)字相同的數(shù)的個(gè)數(shù)。輸入: 輸入包含三行： 第一行為N，表示整數(shù)序列的長(zhǎng)度(N = 100)； 第二行為N個(gè)整數(shù)，整數(shù)之間以一個(gè)空格分開(kāi)； 第三行包含一個(gè)整數(shù)，為指定的數(shù)字m。輸出: 輸出為N個(gè)數(shù)中與m相同的數(shù)的個(gè)數(shù)。樣例輸入:

27、3 2 3 2 2樣例輸出: 2【上機(jī)練習(xí)】2.陶陶摘蘋(píng)果【1.6編程基礎(chǔ)之一維數(shù)組02】Noip2005普及組第1題 陶陶家的院子里有一棵蘋(píng)果樹(shù)，每到秋天樹(shù)上就會(huì)結(jié)出10個(gè)蘋(píng)果。蘋(píng)果成熟的時(shí)候，陶陶就會(huì)跑去摘蘋(píng)果。陶陶有個(gè)30厘米高的板凳，當(dāng)她不能直接用手摘到蘋(píng)果的時(shí)候，就會(huì)踩到板凳上再試試。 現(xiàn)在已知10個(gè)蘋(píng)果到地面的高度，以及陶陶把手伸直的時(shí)候能夠達(dá)到的最大高度，請(qǐng)幫陶陶算一下她能夠摘到的蘋(píng)果的數(shù)目。假設(shè)她碰到蘋(píng)果，蘋(píng)果就會(huì)掉下來(lái)。 輸入: 包括兩行數(shù)據(jù)。第一行包含10個(gè)100到200之間(包括100和200)的整數(shù)(以厘米為單位)分別表示10個(gè)蘋(píng)果到地面的高度，兩個(gè)相鄰的整數(shù)之間用一個(gè)

28、空格隔開(kāi)。第二行只包括一個(gè)100到120之間(包含100和120)的整數(shù)(以厘米為單位)，表示陶陶把手伸直的時(shí)候能夠達(dá)到的最大高度。輸出: 包括一行，這一行只包含一個(gè)整數(shù)，表示陶陶能夠摘到的蘋(píng)果的數(shù)目。樣例輸入: 100 200 150 140 129 134 167 198 200 111 110樣例輸出: 5【上機(jī)練習(xí)】3.計(jì)算書(shū)費(fèi)【1.6編程基礎(chǔ)之一維數(shù)組03】 下面是一個(gè)圖書(shū)的單價(jià)表： 計(jì)算概論 28.9元/本 數(shù)據(jù)結(jié)構(gòu)與算法 32.7元/本 數(shù)字邏輯 45.6元/本 C+程序設(shè)計(jì)教程 78元/本 人工智能 35 元/本 計(jì)算機(jī)體系結(jié)構(gòu) 86.2元/本 編譯原理 27.8元/本 操作系

29、統(tǒng) 43元/本 計(jì)算機(jī)網(wǎng)絡(luò) 56元/本 JAVA程序設(shè)計(jì) 65元/本 給定每種圖書(shū)購(gòu)買(mǎi)的數(shù)量，編程計(jì)算應(yīng)付的總費(fèi)用。輸入: 輸入一行，包含10個(gè)整數(shù)(大于等于0，小于等于100)，分別表示購(gòu)買(mǎi)的計(jì)算概論、數(shù)據(jù)結(jié)構(gòu)與算法、數(shù)字邏輯、C+程序設(shè)計(jì)教程、人工智能、計(jì)算機(jī)體系結(jié)構(gòu)、編譯原理、操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)、JAVA程序設(shè)計(jì)的數(shù)量（以本為單位）。每?jī)蓚€(gè)整數(shù)用一個(gè)空格分開(kāi)。輸出: 輸出一行，包含一個(gè)浮點(diǎn)數(shù)f，表示應(yīng)付的總費(fèi)用。精確到小數(shù)點(diǎn)后一位。樣例輸入: 1 5 8 10 5 1 1 2 3 4樣例輸出: 2140.2【上機(jī)練習(xí)】4.數(shù)組逆序重【1.6編程基礎(chǔ)之一維數(shù)組04】 將一個(gè)數(shù)組中的值按逆

30、序重新存放。例如，原來(lái)的順序?yàn)?,6,5,4,1。要求改為1,4,5,6,8。輸入: 輸入為兩行：第一行數(shù)組中元素的個(gè)數(shù)n（1n100)，第二行是n個(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用空格分隔。輸出: 輸出為一行：輸出逆序后數(shù)組的整數(shù)，每?jī)蓚€(gè)整數(shù)之間用空格分隔。樣例輸入: 5 8 6 5 4 1樣例輸出: 1 4 5 6 8【上機(jī)練習(xí)】5.年齡與疾病【1.6編程基礎(chǔ)之一維數(shù)組05】 某醫(yī)院想統(tǒng)計(jì)一下某項(xiàng)疾病的獲得與否與年齡是否有關(guān)，需要對(duì)以前的診斷記錄進(jìn)行整理，按照0-18、19-35、36-60、61以上（含61）四個(gè)年齡段統(tǒng)計(jì)的患病人數(shù)占總患病人數(shù)的比例。輸入: 共2行，第一行為過(guò)往病人的數(shù)目n（0n

31、=100)，第二行為每個(gè)病人患病時(shí)的年齡。輸出: 按照0-18、19-35、36-60、61以上(含61)四個(gè)年齡段輸出該段患病人數(shù)占總患病人數(shù)的比例，以百分比的形式輸出，精確到小數(shù)點(diǎn)后兩位。每個(gè)年齡段占一行，共四行。樣例輸入: 10 1 11 21 31 41 51 61 71 81 91樣例輸出: 20.00% 20.00% 20.00% 40.00%【上機(jī)練習(xí)】6.校門(mén)外的樹(shù)【1.6編程基礎(chǔ)之一維數(shù)組06】Noip2005普及組第2題 某校大門(mén)外長(zhǎng)度為L(zhǎng)的馬路上有一排樹(shù)，每?jī)煽孟噜彽臉?shù)之間的間隔都是1米。我們可以把馬路看成一個(gè)數(shù)軸，馬路的一端在數(shù)軸0的位置，另一端在L的位置；數(shù)軸上的每個(gè)

32、整數(shù)點(diǎn)，即0，1，2，L，都種有一棵樹(shù)。 由于馬路上有一些區(qū)域要用來(lái)建地鐵。這些區(qū)域用它們?cè)跀?shù)軸上的起始點(diǎn)和終止點(diǎn)表示。已知任一區(qū)域的起始點(diǎn)和終止點(diǎn)的坐標(biāo)都是整數(shù)，區(qū)域之間可能有重合的部分。現(xiàn)在要把這些區(qū)域中的樹(shù)（包括區(qū)域端點(diǎn)處的兩棵樹(shù)）移走。你的任務(wù)是計(jì)算將這些樹(shù)都移走后，馬路上還有多少棵樹(shù)。 輸入: 第一行有兩個(gè)整數(shù)L（1 = L = 10000）和 M（1 = M = 100），L代表馬路的長(zhǎng)度，M代表區(qū)域的數(shù)目，L和M之間用一個(gè)空格隔開(kāi)。接下來(lái)的M行每行包含兩個(gè)不同的整數(shù)，用一個(gè)空格隔開(kāi)，表示一個(gè)區(qū)域的起始點(diǎn)和終止點(diǎn)的坐標(biāo)。 對(duì)于20%的數(shù)據(jù)，區(qū)域之間沒(méi)有重合的部分；對(duì)于其它的數(shù)據(jù)，區(qū)

33、域之間有重合的情況。輸出: 包括一行，這一行只包含一個(gè)整數(shù)，表示馬路上剩余的樹(shù)的數(shù)目。樣例輸入: 樣例輸出: 500 3 298 150 300 100 200 470 471 【上機(jī)練習(xí)】7.向量點(diǎn)積計(jì)算【1.6編程基礎(chǔ)之一維數(shù)組07】 在線性代數(shù)、計(jì)算幾何中，向量點(diǎn)積是一種十分重要的運(yùn)算。給定兩個(gè)n維向量a=(a1,a2,.,an)和b=(b1,b2,.,bn)，求點(diǎn)積ab=a1b1+a2b2+.+anbn。輸入: 第一行是一個(gè)整數(shù)n(1=n=1000)。 第二行包含n個(gè)整數(shù)a1,a2,.,an。 第三行包含n個(gè)整數(shù)b1,b2,.,bn。 相鄰整數(shù)之間用單個(gè)空格隔開(kāi)。每個(gè)整數(shù)的絕對(duì)值都不超

34、過(guò)1000。輸出: 一個(gè)整數(shù)，即兩個(gè)向量的點(diǎn)積結(jié)果。樣例輸入: 3 1 4 6 2 1 5樣例輸出: 36【上機(jī)練習(xí)】8.開(kāi)關(guān)燈【1.5編程基礎(chǔ)之循環(huán)控制28】 假設(shè)有N盞燈(N為不大于5000的正整數(shù))，從1到N按順序依次編號(hào)，初始時(shí)全部處于開(kāi)啟狀態(tài)；有M個(gè)人(M為不大于N的正整數(shù))也從1到M依次編號(hào)。 第一個(gè)人(1號(hào))將燈全部關(guān)閉，第二個(gè)人(2號(hào))將編號(hào)為2的倍數(shù)的燈打開(kāi)，第三個(gè)人(3號(hào))將編號(hào)為3的倍數(shù)的燈做相反處理（即將打開(kāi)的燈關(guān)閉，將關(guān)閉的燈打開(kāi)）。依照編號(hào)遞增順序，以后的人都和3號(hào)一樣，將凡是自己編號(hào)倍數(shù)的燈做相反處理。 請(qǐng)問(wèn)：當(dāng)?shù)贛個(gè)人操作之后，哪幾盞燈是關(guān)閉的，按從小到大輸出其

35、編號(hào)，其間用逗號(hào)間隔。輸入: 輸入正整數(shù)N和M，以單個(gè)空格隔開(kāi)。輸出: 順次輸出關(guān)閉的燈的編號(hào)，其間用逗號(hào)間隔。樣例輸入: 10 10樣例輸出: 1,4,9【上機(jī)練習(xí)】9. 查找特定的值【1.9編程基礎(chǔ)之順序查找01】 在一個(gè)序列(下標(biāo)從1開(kāi)始)中查找一個(gè)給定的值，輸出第一次出現(xiàn)的位置。輸入: 第一行包含一個(gè)正整數(shù)n，表示序列中元素個(gè)數(shù)。1 =n= 10000。 第二行包含n個(gè)整數(shù)，依次給出序列的每個(gè)元素，相鄰兩個(gè)整數(shù)之間用單個(gè)空格隔開(kāi)。元素的絕對(duì)值不超過(guò)10000。 第三行包含一個(gè)整數(shù)x，為需要查找的特定值。x的絕對(duì)值不超過(guò)10000。輸出: 若序列中存在x，輸出x第一次出現(xiàn)的下標(biāo)；否則輸出

36、-1。樣例輸入: 5 2 3 6 7 3 3樣例輸出: 2【上機(jī)練習(xí)】9. 查找特定的值【1.9編程基礎(chǔ)之順序查找01】 在一個(gè)序列(下標(biāo)從1開(kāi)始)中查找一個(gè)給定的值，輸出第一次出現(xiàn)的位置。輸入: 第一行包含一個(gè)正整數(shù)n，表示序列中元素個(gè)數(shù)。1 =n= 10000。 第二行包含n個(gè)整數(shù)，依次給出序列的每個(gè)元素，相鄰兩個(gè)整數(shù)之間用單個(gè)空格隔開(kāi)。元素的絕對(duì)值不超過(guò)10000。 第三行包含一個(gè)整數(shù)x，為需要查找的特定值。x的絕對(duì)值不超過(guò)10000。輸出: 若序列中存在x，輸出x第一次出現(xiàn)的下標(biāo)；否則輸出-1。樣例輸入: 5 2 3 6 7 3 3樣例輸出: 2【上機(jī)練習(xí)】10.不高興的津津【1.9編

37、程基礎(chǔ)之順序查找03】Noip2004普及組第1題 津津上初中了。媽媽認(rèn)為津津應(yīng)該更加用功學(xué)習(xí)，所以津津除了上學(xué)之外，還要參加?jì)寢尀樗龍?bào)名的各科復(fù)習(xí)班。另外每周媽媽還會(huì)送她去學(xué)習(xí)朗誦、舞蹈和鋼琴。但是津津如果一天上課超過(guò)八個(gè)小時(shí)就會(huì)不高興，而且上得越久就會(huì)越不高興。假設(shè)津津不會(huì)因?yàn)槠渌虏桓吲d，并且她的不高興不會(huì)持續(xù)到第二天。請(qǐng)你幫忙檢查一下津津下周的日程安排，看看下周她會(huì)不會(huì)不高興；如果會(huì)的話，哪天最不高興。 輸入: 包括七行數(shù)據(jù)，分別表示周一到周日的日程安排。每行包括兩個(gè)小于10的非負(fù)整數(shù)，用空格隔開(kāi)，分別表示津津在學(xué)校上課的時(shí)間和媽媽安排她上課的時(shí)間。輸出:包括一行，這一行只包含一個(gè)數(shù)字

38、。如果不會(huì)不高興則輸出0，如果會(huì)則輸出最不高興的是周幾（用1, 2, 3, 4, 5, 6, 7分別表示周一，周二，周三，周四，周五，周六，周日）。如果有兩天或兩天以上不高興的程度相當(dāng)，則輸出時(shí)間最靠前的一天。樣例輸入: 樣例輸出: 5 3 3 6 2 7 2 5 3 5 4 0 4 0 6 【上機(jī)練習(xí)】11.最大值和最小值的差【1.9編程基礎(chǔ)之順序查找05】 輸出一個(gè)整數(shù)序列中最大的數(shù)和最小的數(shù)的差。輸入: 第一行為M，表示整數(shù)個(gè)數(shù)，整數(shù)個(gè)數(shù)不會(huì)大于10000； 第二行為M個(gè)整數(shù)，以空格隔開(kāi)，每個(gè)整數(shù)的絕對(duì)值不會(huì)大于10000。輸出: 輸出M個(gè)數(shù)中最大值和最小值的差。樣例輸入: 5 2 5

39、7 4 2樣例輸出: 5 【上機(jī)練習(xí)】12.不與最大數(shù)相同的數(shù)字之和【1.9編程基礎(chǔ)之順序查找07】 輸出一個(gè)整數(shù)數(shù)列中不與最大數(shù)相同的數(shù)字之和。輸入: 輸入分為兩行： 第一行為N(N為接下來(lái)數(shù)的個(gè)數(shù)，N = 100)； 第二行N個(gè)整數(shù)，數(shù)與數(shù)之間以一個(gè)空格分開(kāi)，每個(gè)整數(shù)的范圍是-1000,000到1000,000。輸出: 輸出為N個(gè)數(shù)中除去最大數(shù)其余數(shù)字之和。樣例輸入: 3 1 2 3樣例輸出: 3 【上機(jī)練習(xí)】13.白細(xì)胞計(jì)數(shù)【1.9編程基礎(chǔ)之順序查找08】 醫(yī)院采樣了某臨床病例治療期間的白細(xì)胞數(shù)量樣本n份，用于分析某種新抗生素對(duì)該病例的治療效果。為了降低分析誤差，要先從這n份樣本中去除一

40、個(gè)數(shù)值最大的樣本和一個(gè)數(shù)值最小的樣本，然后將剩余n-2個(gè)有效樣本的平均值作為分析指標(biāo)。同時(shí)，為了觀察該抗生素的療效是否穩(wěn)定，還要給出該平均值的誤差，即所有有效樣本（即不包括已扣除的兩個(gè)樣本）與該平均值之差的絕對(duì)值的最大值。 現(xiàn)在請(qǐng)你編寫(xiě)程序，根據(jù)提供的n個(gè)樣本值，計(jì)算出該病例的平均白細(xì)胞數(shù)量和對(duì)應(yīng)的誤差。輸入: 輸入的第一行是一個(gè)正整數(shù)n（2 n= 300），表明共有n個(gè)樣本。 以下共有n行，每行為一個(gè)浮點(diǎn)數(shù)，為對(duì)應(yīng)的白細(xì)胞數(shù)量，其單位為109/L。數(shù)與數(shù)之間以一個(gè)空格分開(kāi)。輸出: 輸出為兩個(gè)浮點(diǎn)數(shù)，中間以一個(gè)空格分開(kāi)。分別為平均白細(xì)胞數(shù)量和對(duì)應(yīng)的誤差，單位也是109/L。計(jì)算結(jié)果需保留到小數(shù)

41、點(diǎn)后2位。樣例輸入: 樣例輸出: 5 11.00 1.00 12.0 13.0 11.0 9.0 10.0 【上機(jī)練習(xí)】14.直方圖【1.9編程基礎(chǔ)之順序查找09】 給定一個(gè)非負(fù)整數(shù)數(shù)組，統(tǒng)計(jì)里面每一個(gè)數(shù)的出現(xiàn)次數(shù)。我們只統(tǒng)計(jì)到數(shù)組里最大的數(shù)。 假設(shè) Fmax（Fmax10000）是數(shù)組里最大的數(shù)，那么我們只統(tǒng)計(jì)0,1,2.Fmax里每個(gè)數(shù)出現(xiàn)的次數(shù)。輸入: 第一行n是數(shù)組的大小。1 = n = 10000。 緊接著一行是數(shù)組的n個(gè)元素。輸出: 按順序輸出每個(gè)數(shù)的出現(xiàn)次數(shù)，一行一個(gè)數(shù)。如果沒(méi)有出現(xiàn)過(guò)，則輸出0。 對(duì)于例子中的數(shù)組，最大的數(shù)是3，因此我們只統(tǒng)計(jì)0,1,2,3的出現(xiàn)頻數(shù)。樣例輸入:

42、 5 1 1 2 3 1樣例輸出: 0 3 1 1 【上機(jī)練習(xí)】15.最長(zhǎng)平臺(tái)【1.9編程基礎(chǔ)之順序查找12】 已知一個(gè)已經(jīng)從小到大排序的數(shù)組，這個(gè)數(shù)組的一個(gè)平臺(tái)（Plateau）就是連續(xù)的一串值相同的元素，并且這一串元素不能再延伸。例如，在 1，2，2，3，3，3，4，5，5，6中1，2-2，3-3-3，4，5-5，6都是平臺(tái)。試編寫(xiě)一個(gè)程序，接收一個(gè)數(shù)組，把這個(gè)數(shù)組最長(zhǎng)的平臺(tái)找出 來(lái)。在上面的例子中3-3-3就是最長(zhǎng)的平臺(tái)。輸入: 第一行有一個(gè)整數(shù)n，為數(shù)組元素的個(gè)數(shù)。第二行有n個(gè)整數(shù)，整數(shù)之間以一個(gè)空格分開(kāi)。輸出: 輸出最長(zhǎng)平臺(tái)的長(zhǎng)度。樣例輸入: 10 1 2 2 3 3 3 4 5 5

43、 6樣例輸出: 3 【上機(jī)練習(xí)】16.整數(shù)去重【1.9編程基礎(chǔ)之順序查找13】 給定含有n個(gè)整數(shù)的序列，要求對(duì)這個(gè)序列進(jìn)行去重操作。所謂去重，是指對(duì)這個(gè)序列中每個(gè)重復(fù)出現(xiàn)的數(shù)，只保留該數(shù)第一次出現(xiàn)的位置，刪除其余位置。輸入: 輸入包含兩行： 第一行包含一個(gè)正整數(shù)n（1 = n = 20000），表示第二行序列中數(shù)字的個(gè)數(shù)； 第二行包含n個(gè)整數(shù)，整數(shù)之間以一個(gè)空格分開(kāi)。每個(gè)整數(shù)大于等于10、小于等于100。輸出: 輸出只有一行，按照輸入的順序輸出其中不重復(fù)的數(shù)字，整數(shù)之間用一個(gè)空格分開(kāi)。樣例輸入: 5 10 12 93 12 75樣例輸出: 10 12 93 75【上機(jī)練習(xí)】17.鋪地毯【1.9

44、編程基礎(chǔ)之順序查找14】Noip2011提高組第1題 為了準(zhǔn)備一個(gè)獨(dú)特的頒獎(jiǎng)典禮，組織者在會(huì)場(chǎng)的一片矩形區(qū)域（可看做是平面直角坐標(biāo)系的第一象限）鋪上一些矩形地毯。一共有n張地毯，編號(hào)從1到n?，F(xiàn)在將這些地毯按照編號(hào)從小到大的順序平行于坐標(biāo)軸先后鋪設(shè)，后鋪的地毯覆蓋在前面已經(jīng)鋪好的地毯之上。地毯鋪設(shè)完成后，組織者想知道覆蓋地面某個(gè)點(diǎn)的最上面的那張地毯的編號(hào)。注意：在矩形地毯邊界和四個(gè)頂點(diǎn)上的點(diǎn)也算被地毯覆蓋。 輸入輸出樣例1說(shuō)明：如下圖，1號(hào)地毯用實(shí)線表示，2號(hào)地毯用虛線表示，3號(hào)用雙實(shí)線表示，覆蓋點(diǎn)（2，2）的最上面一張地毯是3號(hào)地毯。 輸入輸出樣例2說(shuō)明：如下圖，1號(hào)地毯用實(shí)線表示，2號(hào)地毯

45、用虛線表示，3號(hào)用雙實(shí)線表示，覆蓋點(diǎn)（4，5）的最上面一張地毯是3號(hào)地毯?！旧蠙C(jī)練習(xí)】輸入: 第一行，一個(gè)整數(shù)n，表示總共有n張地毯。 接下來(lái)的n行中，第i+1行表示編號(hào)i的地毯的信息，包含四個(gè)正整數(shù)a，b，g，k，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，分別表示鋪設(shè)地毯的左下角的坐標(biāo)（a，b）以及地毯在x軸和y軸方向的長(zhǎng)度。 第n+2行包含兩個(gè)正整數(shù)x和y，表示所求的地面的點(diǎn)的坐標(biāo)（x，y）。輸出: 輸出共1行，一個(gè)整數(shù)，表示所求的地毯的編號(hào)；若此處沒(méi)有被地毯覆蓋則輸出-1。樣例輸入: 樣例輸出:樣例 #1： 樣例 #1：3 31 0 2 30 2 3 32 1 3 32 2樣例 #2： 樣例 #2：

46、3 -11 0 2 30 2 3 32 1 3 34 5第二節(jié)第二節(jié) 二維數(shù)組二維數(shù)組一、二維數(shù)組的定義當(dāng)一維數(shù)組元素的類型也是一維數(shù)組時(shí)，便構(gòu)成了“數(shù)組的數(shù)組”，即二維數(shù)組。二維數(shù)組定義的一般格式：數(shù)據(jù)類型 數(shù)組名常量表達(dá)式1 常量表達(dá)式2 ；例如：int a410;a數(shù)組實(shí)質(zhì)上是一個(gè)有4行、10列的表格，表格中可儲(chǔ)存40個(gè)元素。第1行第1列對(duì)應(yīng)a數(shù)組的a00，第n行第m列對(duì)應(yīng)數(shù)組元素an-1m-1。說(shuō)明：當(dāng)定義的數(shù)組下標(biāo)有多個(gè)時(shí)，我們稱為多維數(shù)組，下標(biāo)的個(gè)數(shù)并不局限在一個(gè)或二個(gè)，可以任意多個(gè)，如定義一個(gè)三維數(shù)組a和四維數(shù)組b：int a10035;int b10010035;多維的數(shù)組引用

47、賦值等操作與二維數(shù)組類似。二、二維數(shù)組元素的引用二維數(shù)組的數(shù)組元素引用與一維數(shù)組元素引用類似，區(qū)別在于二維數(shù)組元素的引用必須給出兩個(gè)下標(biāo)。引用的格式為： 下標(biāo)1下標(biāo)2說(shuō)明：顯然，每個(gè)下標(biāo)表達(dá)式取值不應(yīng)超出下標(biāo)所指定的范圍，否則會(huì)導(dǎo)致致命的越界錯(cuò)誤。例如,設(shè)有定義：int a35;則表示a是二維數(shù)組（相當(dāng)于一個(gè)3*5的表格），共有3*5=15個(gè)元素，它們是：a00 a01 a02 a03 a04a10 a11 a12 a13 a14a20 a21 a22 a23 a24因此可以看成一個(gè)矩陣（表格），a23即表示第3行第4列的元素。三、二維數(shù)組的初始化二維數(shù)組的初始化和一維數(shù)組類似。可以將每一行分

48、開(kāi)來(lái)寫(xiě)在各自的括號(hào)里，也可以把所有數(shù)據(jù)寫(xiě)在一個(gè)括號(hào)里。例如：int direct42 = 1,0,0,1,-1,0,0,-1 int direct42 = 1,0,0,1,-1,0,0,-1 /盡量不要用四、二維數(shù)組程序設(shè)計(jì)例5.8 設(shè)有一程序#include#include#includeconst int n=3;using namespace std;int an+1n+1;int main() for (int i=1; i=n; +i) for (int j=1; jaij; for (int i=1; i=n; +i) for (int j=1; j=n; +j) coutsetw

49、(5)aji; coutendl; return 0;程序的輸入:2 1 33 3 11 2 1程序的輸出:2 3 11 3 23 1 1例5.9 已知一個(gè)6*6的矩陣（方陣），把矩陣二條對(duì)角線上的元素值加上10，然后輸出這個(gè)新矩陣?！痉治觥?矩陣即表格，是一個(gè)二維數(shù)組，有6行6列共36個(gè)元素，每個(gè)矩陣都有二條對(duì)角線，本題難點(diǎn)在于對(duì)角線的元素怎么確定。#include#includeusing namespace std;int a77;int main() for (int i=1; i=6; +i) /輸入矩陣元素 for (int j=1; jaij; for (int i=1; i=6

50、; +i) /更改對(duì)角線上元素的值 for (int j=1; j=6; +j) if (i=j)|(i+j=7) aij+=10; /尋找對(duì)角線的特征 for (int i=1; i=6; +i) /輸出6行6列的矩陣元素 for (int j=1; j=6; +j) coutsetw(5)aij; coutendl; return 0;例5.10 大部分元素是0的矩陣稱為稀疏矩陣，假設(shè)有k個(gè)非0元素，則可把稀疏矩陣用K*3的矩陣簡(jiǎn)記之，其中第一列是行號(hào)，第二列是列號(hào)，第三列是該行、該列下的非元素的值。如：0 0 0 5 寫(xiě)簡(jiǎn)記成： 1 4 5 /第1行第4列有個(gè)數(shù)是50 2 0 0 2 2

51、 2 /第2行第2列有個(gè)數(shù)是20 1 0 0 3 2 1 /第3行第2列有個(gè)數(shù)是1試編程讀入一稀疏矩陣，轉(zhuǎn)換成簡(jiǎn)記形式，并輸出?！痉治觥?本題中需要解決的主要問(wèn)題是查找非零元素并記憶位置。將原始矩陣存于數(shù)組a。轉(zhuǎn)換后的矩陣存于數(shù)組b，當(dāng)然b數(shù)組的行數(shù)可以控制在一個(gè)小范圍內(nèi)。#include#includeconst int n=3,m=5;using namespace std;int main() int an+1m+1,b1014,k=0; for (int i=1; i=n; +i) /矩陣初始 for (int j=1; jaij; for (int i=1; i=n; +i) for

52、 (int j=1; j=m; +j) if (aij!=0) /找到非零值，存儲(chǔ) +k; bk1=i; bk2=j; bk3=aij; for (int i=1; i=k; +i) /輸出 for (int j=1; j=3; +j) coutsetw(3)bij; coutendl; return 0;運(yùn)行結(jié)果：輸入： 0 0 0 0 5 0 0 4 0 0 1 0 0 0 1輸出： 1 5 5 2 3 4 3 1 1 3 5 1例5.11 打印楊輝三角形的前10行。楊輝三角形如下圖： 1 1 1 1 1 1 1 2 1 1 2 1 1 3 3 1 1 3 3 11 4 6 4 1 1 4

53、 6 4 1 圖5-1 圖5-2【問(wèn)題分析】觀察圖5-1，大家不容易找到規(guī)律，但是如果將它轉(zhuǎn)化為圖5-2，不難發(fā)現(xiàn)楊輝三角形其實(shí)就是一個(gè)二維表的小三角形部分，假設(shè)通過(guò)二維數(shù)組a存儲(chǔ)，每行首尾元素為1，且其中任意一個(gè)非首位元素aij的值其實(shí)就是ai-1j-1與ai-1j的和，另外每一行的元素個(gè)數(shù)剛好等于行數(shù)。有了數(shù)組元素的值，要打印楊輝三角形，只需要控制好輸出起始位置就行了。#include#includeusing namespace std;int main() int a1111; a11=1;/設(shè)定第一行的值 for (int i=2; i=10; +i)/從第二行開(kāi)始推 ai1=1;

54、aii=1;/設(shè)定每一行的首尾值為1 for (int j=2; j=i-1; +j)/當(dāng)前行非首尾的數(shù) aij=ai-1j-1+ai-1j; /每個(gè)數(shù)等于上一行的二個(gè)數(shù)之和 for (int i=1; i=10; i+) if (i!=10) coutsetw(30-3*i) ;/控制每行的起始位置，即空格數(shù)量 for (int j=1; j=i; j+) coutsetw(6)aij; coutendl; return 0; 例5.12 輸入一串字符,字符個(gè)數(shù)不超過(guò)100,且以“.”結(jié)束。 判斷它們是否構(gòu)成回文。【分析】所謂回文指從左到右和從右到左讀一串字符的值是一樣的，如12321,AB

55、CBA,AA等。先讀入要判斷的一串字符（放入數(shù)組letter中），并記住這串字符的長(zhǎng)度，然后首尾字符比較，并不斷向中間靠攏，就可以判斷出是否為回文。程序如下：#includeusing namespace std;int main() char ch,letter101; int i=0,j=1; coutch; while (ch!=.)/讀入一個(gè)字符串以.號(hào)結(jié)束 +i; letteri=ch; cinch; while (j=i) coutYesendl; else coutNoendl; return 0;例5.13 蛇形填數(shù) 在n*n方陣?yán)锾钊?,2,3,n*n，要求填成蛇形。例如n=

56、4時(shí)方陣為： 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 上面的方陣中，多余的空格只是為了便于觀察規(guī)律，不必嚴(yán)格輸出，n=8?！痉治觥浚?類比數(shù)學(xué)中的矩陣，我們可以用一個(gè)所謂的二維數(shù)組來(lái)儲(chǔ)存題目中的方陣。只需聲明一個(gè)int aMAXNMAXN，就可以獲得一個(gè)大小為MAXNMAXN的方陣。在聲明時(shí)，兩維的大小不必相同，因此也可以聲明int a3050這樣的數(shù)組，第一維下標(biāo)范圍是0,1,2,29，第二維下標(biāo)范圍是0,1,2,49。 讓我們從1開(kāi)始依次填寫(xiě)。設(shè)“筆”的坐標(biāo)為(x,y)，則一開(kāi)始x=0，y=n-1，即第0行，第n-1列（別忘了行列的范圍是0到n-1，沒(méi)

57、有第n列）?！肮P”的移動(dòng)軌跡是：下，下，下，左，左，左，上，上，上，右，右，下，下，左，上?？傊仁窍?，到不能填了為止，然后是左，接著是上，最后是右?！安荒芴睢笔侵冈僮呔统鼋纾ɡ?5），或者再走就要走到以前填過(guò)的格子（例如1213）。如果我們把所有格子初始為0，就能很方便地加以判斷。#include#include#define MAXN 10int aMAXNMAXN;int main()int n,x,y,tot=0;scanf(%d,&n);memset(a,0,sizeof(a);tot=ax=0y=n-1=1;while (totn*n) while (x+1=0 &am

58、p; !axy-1) ax-y=+tot; while (x-1=0 & !ax-1y) a-xy=+tot; while (y+1n & !axy+1) ax+y=+tot; for(x=0;xn;+x) for (y=0;yn;+y) printf(%3d,axy);printf(n); return 0;【說(shuō)明】： 這段程序充分利用了C+語(yǔ)言簡(jiǎn)潔的優(yōu)勢(shì)。首先，賦值x=0和y=n-1后馬上要把它們作為a數(shù)組的下標(biāo)，因此可以合并完成；tot和a0n-1都要賦值1，也可以合并完成。這樣，我們用一條語(yǔ)句完成了多件事情，而且并沒(méi)有犧牲程序的可讀性，這段代碼的含義顯而易見(jiàn)。 那4條w

59、hile語(yǔ)句有些難懂，不過(guò)十分相似，因此只需介紹其中的第一條：不斷向下走，并且填數(shù)。我們的原則是：先判斷，再移動(dòng)，而不是走一步以后發(fā)現(xiàn)越界了再退回來(lái)。這樣，我們需要進(jìn)行“預(yù)判”，即是否越界，以及如果繼續(xù)往下走會(huì)不會(huì)到達(dá)一個(gè)已經(jīng)填過(guò)的格子。越界只需判斷x+1n，因?yàn)閥值并沒(méi)有修改；下一個(gè)格子是(x+1,y)，因此只需ax+1y=0，簡(jiǎn)寫(xiě)成!ax+1y（其中!是“邏輯非”運(yùn)算符）。 細(xì)心的讀者也許會(huì)發(fā)現(xiàn)這里的一個(gè)“潛在bug”；如果越界，x+1會(huì)等于n，ax+1y將訪問(wèn)非法內(nèi)存！幸運(yùn)的是，這樣的擔(dān)心是不必要的。&是短路運(yùn)算符。如果x+1n為假，將不會(huì)計(jì)算!ax+1y，也就不會(huì)越界了。 至于

60、為什么是+tot而不是tot+，留給讀者思考。【上機(jī)練習(xí)】1.矩陣交換行【1.8編程基礎(chǔ)之多維數(shù)組01】 給定一個(gè)5*5的矩陣(數(shù)學(xué)上，一個(gè)rc的矩陣是一個(gè)由r行c列元素排列成的矩形陣列)，將第n行和第m行交換，輸出交換后的結(jié)果。輸入: 輸入共6行，前5行為矩陣的每一行元素,元素與元素之間以一個(gè)空格分開(kāi)。 第6行包含兩個(gè)整數(shù)m、n，以一個(gè)空格分開(kāi)（1 = m,n = 5）。輸出: 輸出交換之后的矩陣，矩陣的每一行元素占一行，元素之間以一個(gè)空格分開(kāi)。樣例輸入: 1 2 2 1 2 5 6 7 8 3 9 3 0 5 3 7 2 1 4 6 3 0 8 2 4 1 5樣例輸出: 3 0 8 2 4 5 6 7 8 3 9 3 0 5 3 7 2 1