第5章數(shù)組(C++版)

1、第五章第五章 數(shù)組數(shù)組 第一節(jié)第一節(jié) 一維數(shù)組一維數(shù)組第二節(jié)第二節(jié) 二維數(shù)組二維數(shù)組第三節(jié)第三節(jié) 字符數(shù)組和字符串類型字符數(shù)組和字符串類型第一節(jié)第一節(jié) 一維數(shù)組一維數(shù)組一、為什么要使用數(shù)組通過前面幾章的學習，我們已經(jīng)可以編寫程序來解決各種相當復雜的問題了，但是當需要處理的數(shù)據(jù)比較多時，僅依靠前面的知識是不夠的，即使簡單的問題也可能需要比較復雜的程序來處理。請看下面的例子：例題：輸入50個學生的某門課程的成績，打印出低于平均分的學生序號與成績?！痉治觥吭诮鉀Q這個問題時，雖然可以通過一個變量來累加讀入的50個成績求出學生的總分，進而求出平均分。但因為只有讀入最后一個學生的分數(shù)后才能求得平均分，并且

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

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

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

5、集合，這些變量的類型全部一致。二、一維數(shù)組的定義當數(shù)組中每個元素只帶有一個下標時，我們稱這樣的數(shù)組為一維數(shù)組。數(shù)組的定義格式如下：類型標識符 數(shù)組名常量表達式說明：數(shù)組名的命名規(guī)則與變量名的命名規(guī)則一致。常量表達式表示數(shù)組元素的個數(shù)?？梢允浅Ａ亢头柍Ａ?，但不能是變量。例如：int a10; /數(shù)組a定義是合法的 int bn; /數(shù)組b定義是非法的三、一組數(shù)組的引用通過給出的數(shù)組名稱和這個元素在數(shù)組中的位置編號(即下標)，程序可以引用這個數(shù)組中的任何一個元素。一維數(shù)組元素的引用格式：數(shù)組名下標例如：int a10; 其中，a是一維數(shù)組的數(shù)組名，該數(shù)組有10個元素，依次表示為： a0,a1,a

6、2,a3,a4,a5,a6,a7,a8,a9。 需要注意的是：a10不屬于該數(shù)組的空間范圍。 當在說明部分定義了一個數(shù)組變量之后,C+編譯程序為所定義的數(shù)組在內(nèi)存空間開辟一串連續(xù)的存儲單元。例如：上例中的a數(shù)組在內(nèi)存的存儲如表所示：a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a數(shù)組共有10個元素組成，在內(nèi)存中10個數(shù)組元素共占10個連續(xù)的存儲單元。a數(shù)組最小下標為0，最大下標9。按定義a數(shù)組所有元素都是整型變量。 再次提醒注意：類型和變量是兩個不同概念，不能混淆。就數(shù)組而言，程序的執(zhí)行部分使用的不是數(shù)組類型而是數(shù)組變量。說明： (1)下標可以是整型常量或整型表達式。如果使用表達

7、式作為下標，就要計算表達式的值以確定下標。(2)C+語言中，每個數(shù)組第一個元素的下標都是0，因此第一個元素為第0個數(shù)組元素。(3)C+語言只能逐個引用數(shù)組元素，而不能一次引用整個數(shù)組。例如：int a100,b100; a=b;這樣的寫法是非法的。(4)數(shù)組元素可以像同類型的普通變量那樣使用，對其進行賦值和運算的操作，和普通變量完全相同。例如： c10=34;實現(xiàn)了給c10賦值為34。四、一維數(shù)組的初始化 數(shù)組的初始化可以在定義時一并完成。格式： 類型標識符 數(shù)組名常量表達式=值1，值2，例如：int a5=1,2,3,4,5說明：(1)在初值列表中可以寫出全部數(shù)組元素的值，也可以寫出部分。例

8、如，以下方式可以對數(shù)組進行初始化：int x10=0,1,2,3,4;該方法一次僅對數(shù)組的前5個元素依次進行初始化。(2)對數(shù)組元素全部初始化為0，可以簡寫為：0。例如： int a5=0; 將數(shù)組a的5個元素都初始化為0。五、一維數(shù)組的應(yīng)用例5.1 輸入n個數(shù),要求程序按輸入時的逆序把這n個數(shù)打印出來，已知整數(shù)不超過100個。也就是說，按輸入相反順序打印這n個數(shù)?！痉治觥课覀兛啥x一個數(shù)組a用以存放輸入的n個數(shù), 然后將數(shù)組a中的內(nèi)容逆序輸出。#include#includeint a100;int a100;int main()int main() int x,n=0;int x,n=0;

9、 while(scanf(%d,&x)=1)while(scanf(%d,&x)=1) an+=x; an+=x; /相當相當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后面有一個空格，保證行首行尾均無空格后面有一個空格，保證行首行尾均無空格 printf(%dn,a0);printf(%dn,a0); return 0;return 0; 【說明】： 語句int a100聲明了一個包含100個整型變量的數(shù)組，它們是：

10、a0，a1，a2，a99。注意，沒有a100。在上述程序中，數(shù)組a被聲明在main函數(shù)的外面。只有放在外面時，數(shù)組a才可以開得很大；放在main函數(shù)內(nèi)時，數(shù)組稍大就會異常退出。它的道理將在后面討論，只需要記住規(guī)則即可。 數(shù)組不能夠進行賦值操作：如果聲明的是int aMAXN，bMAXN,是不能賦值b=a的(Pascal語言可以的)。如果要從數(shù)組a復制k個元素到數(shù)組b，可以這樣做：memcpy(b,a,sizeof(int)*k)。當然了，如果數(shù)組a和b都是浮點型的，復制時要寫成memcpy(b,a,sizeof(double)*k)。如果需要把數(shù)組a全部復制到數(shù)組b中，可以寫得簡單一些：mem

11、cpy(b,a,sizeof(a)。使用memcpy函數(shù)要包含頭文件cstring。 例5.2 將a數(shù)組中第一個元素移到數(shù)組末尾,其余數(shù)據(jù)依次往前平移一個位置?！痉治觥繛橥瓿深}目所要求的操作，其算法應(yīng)該包括以下幾個主要步驟： 把第一個元素的值取出放在一個臨時單元 temp中； 通過 a2a1, a3a2, a4a3， anan-1,實現(xiàn)其余元素前移 將 temp值送入an. #include#include /調(diào)用setw函數(shù)需注明使用該庫const int n=10;using namespace std; int an,temp; int main() coutread n datasen

12、dl;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ù)控制輸出場寬return 0; 運行結(jié)果 : read 10 datas: 1 2 3 4 5 6 7 8 9 10 Result: 2 3 4 5 6 7 8 9 10 1 例5.3 賓館里有一百個房間，從1-100編了號。第一個服務(wù)員把所有的房間門都打開了，第二個服務(wù)員把所有編號是2的倍數(shù)的房間“相反處理”，第三個服務(wù)員把所有編號是

13、3的倍數(shù)的房間作“相反處理”，以后每個服務(wù)員都是如此。當?shù)?00個服務(wù)員來過后，哪幾扇門是打開的。（所謂“相反處理”是：原來開著的門關(guān)上，原來關(guān)上的門打開。）【分析】此題較簡單，用a1,a2,an表示編號為1，2，3，,n的門是否開著。模擬這些操作即可，參考程序如下：#include#include#define MAXN 100+10int aMAXN;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

14、i=1;i=100;+i) if (ai) if(first) first=0; else printf( ); printf(%d,i); printf(n);return 0;運行結(jié)果：14 9 16 25 36 49 64 81 100【說明】： memset(a,0,sizeof(a)的作用是把數(shù)組a清零，它在cstring中定義。雖然也能用for循環(huán)完成相同的任務(wù)，但是用memset又方便又快捷。另一個技巧在輸出：為了避免輸出多余空格，設(shè)置了一個標志變量first，可以表示當前要輸出是否為第一個。第一個變量前不應(yīng)該有空格，但其他都有。例5.4 約瑟夫問題：N個人圍成一圈，從第一個人開

15、始報數(shù)，數(shù)到M的人出圈；再由下一個人開始報數(shù)，數(shù)到M的人出圈；輸出依次出圈的人的編號。N，M由鍵盤輸入。【分析】 （1）由于對于每個人只有出圈和沒有圈兩種狀態(tài)，因此可以用布爾型標志數(shù)組存儲游戲 過程中每個人的狀態(tài)。不妨用true表示出圈，false 表示沒有出圈。 （2）開始的時候，給標志數(shù)組賦初值為false，即全部在圈內(nèi)。 （3）模擬報數(shù)游戲的過程，直到所有的人出圈為止。程序如下：#includeusing namespace std;int n,m,s,f,t;bool a101;/根據(jù)題意開出數(shù)組大小int main() cinnm;/共n人，報到m出圈 coutendl; for (

16、t=1;t=n;+t) at=false; /等同于memset(a,0,sizeof(a),要調(diào)用cstring庫 f=0; t=0; s=0; /剛開始所有變量默認值也是0,或者用f=t=s=0; do +t;/逐個枚舉圈中的所有位置 if (t=n+1) t=1;/數(shù)組模擬環(huán)狀，最后一個與第一個相連 if (at=false) +s;/第t個位置上有人則報數(shù) if (s=m) /當前報的數(shù)是m s=0;/計數(shù)器清零 coutt ;/輸出出圈人的編號 at=true;/此處的人已出圈，設(shè)置為空 f+; /出圈的人數(shù)增加一個 while(f!=n);/直到所有的人都出圈為止 return 0

17、;運行結(jié)果：輸入： 8 5輸出： 5 2 8 7 1 4 6 3這是一個在算法設(shè)計上很有名氣的經(jīng)典約瑟夫（Josephu）問題，它有很多變例。如猴子選大王、持密碼報數(shù)、狐貍追兔子等（見上機練習）。例5.5 輸入十個正整數(shù),把這十個數(shù)按由大到小的順序排列。（選擇排序 ）將數(shù)據(jù)按一定順序排列稱為排序，排序的算法有很多，其中選擇排序是一種較簡單的方法。【問題分析】要把十個數(shù)按從大到小順序排列，則排完后，第一個數(shù)最大，第二個數(shù)次大，。因此，我們第一步可將第一個數(shù)與其后的各個數(shù)依次比較，若發(fā)現(xiàn)，比它大的，則與之交換，比較結(jié)束后，則第一個數(shù)已是最大的數(shù)。同理，第二步，將第二個數(shù)與其后各個數(shù)再依次比較，又可

18、得出次大的數(shù)。如此方法進行比較，最后一次，將第九個數(shù)與第十個數(shù)比較，以決定次小的數(shù)。于是十個數(shù)的順序排列結(jié)束。如對5個進行排序，這個五個數(shù)分別為829105。按選擇排序方法，過程如下：初始數(shù)據(jù)：829105第一次排序：829105928105102895102895第二次排序：108295109285109285第三次排序：109825109825第四次排序：109852對于十個數(shù)，則排序要進行9次。程序如下：#include#includeusing namespace std;int t,a11;int main()coutInput 10 intergers:endl; /讀入10個初始

19、數(shù)據(jù) for (int i=1; iai;coutendl; for (int i=1; i=9; +i) /進行9次排序 for (int j=i+1; j=10; +j) /將第i個數(shù)與其后所有數(shù)比較 if (aiaj) t=ai; ai=aj; aj=t; /若有比ai大,則與之交換 for (int i=1;i=10;+i) coutsetw(5)ai; return 0;運行結(jié)果：輸入： 8 67 52 189 74 5 58 9 23 41輸出： 189 74 67 58 52 41 23 9 8 5例5.6 編程輸入十個正整數(shù)，然后自動按從大到小的順序輸出。（冒泡排序）【問題分析

20、】用循環(huán)把十個數(shù)輸入到A數(shù)組中；從A1到A10，相鄰的兩個數(shù)兩兩相比較，即： A1與A2比，A2與A3比，A9與A10比。只需知道兩個數(shù)中的前面那元素的標號，就能進行與后一個序號元素（相鄰數(shù)）比較，可寫成通用形式Ai與Ai+1比較，那么，比較的次數(shù)又可用1( n-i )循環(huán)進行控制(即循環(huán)次數(shù)與兩兩相比較時前面那個元素序號有關(guān)) ；在每次的比較中，若較大的數(shù)在后面，就把前后兩個對換，把較大的數(shù)調(diào)到前面，否則不需調(diào)換位置。下面例舉5個數(shù)來說明兩兩相比較和交換位置的具體情形： 5 6 4 3 7 5和6比較，交換位置，排成下行的順序； 6 5 4 3 7 5和4比較，不交換，維持同樣的順序； 6

21、5 4 3 7 4和3比較，不交換，順序不變 6 5 4 3 7 3和7比較，交換位置，排成下行的順序； 6 5 4 7 3 經(jīng)過（1（n-1）次比較后，將3調(diào)到了末尾經(jīng)過第一輪的1 (N-1)次比較，就能把十個數(shù)中的最小數(shù)調(diào)到最末尾位置，第二輪比較1 (N-2)次進行同樣處理，又把這一輪所比較的“最小數(shù)”調(diào)到所比較范圍的“最末尾”位置；每進行一輪兩兩比較后，其下一輪的比較范圍就減少一個。最后一輪僅有一次比較。在比較過程中，每次都有一個“最小數(shù)”往下“掉”，用這種方法排列順序，常被稱之為“冒泡法”排序。程序如下：#include#includeusing namespace std;const

22、 int n=10;int t,an+1; /定義數(shù)組int main() for (int i=1; iai; /輸入十個數(shù) for (int j=1; j=n-1; +j) /冒泡法排序 for (int i=1; i=n-j; +i) /兩兩相比較 if (aiai+1) /比較與交換 t=ai; ai=ai+1; ai+1=t; for (int i=1; i=n; +i) coutsetw(5)ai; /輸出排序后的十個數(shù) coutfloor(sqrt(N) 為止； 打印輸出a數(shù)組中留下來、未被篩掉的各元素值，并按每行五個數(shù)顯示。用篩法求素數(shù)的過程示意如下（圖中用下劃線作刪去標志）：

23、 2 3 4 5 6 7 8 9 10 11 12 13 14 1598 99 100 /置數(shù) 2 3 4 5 6 7 8 9 10 11 12 13 14 1598 99 100 /篩去被2整除的數(shù) 2 3 4 5 6 7 8 9 10 11 12 13 14 1598 99 100 /篩去被3整除的數(shù) 2 3 4 5 6 7 8 9 10 11 12 13 14 1598 99 100 /篩去被整除的數(shù)程序如下：#include#include /在Dev C+中可調(diào)用數(shù)學函數(shù)庫cmath#includeusing namespace std;const int n=100;int t;b

24、ool an+1;int main() for (int i=0; i=n; +i) ai=true; /等同于memset(a,1,sizeof(a) , 要調(diào)用cstrin庫 a1=false; for (int i=2; i=sqrt(n); +i) if (ai) for (int j=2; j=n/i; +j) ai*j=false; t=0; for (int i=2; i=n; +i) if (ai) coutsetw(5)i; t+; if (t%5=0) coutendl; return 0;【上機練習】1、與指定數(shù)字相同的數(shù)的個數(shù)【1.6編程基礎(chǔ)之一維數(shù)組01】 輸出一個整

25、數(shù)序列中與指定數(shù)字相同的數(shù)的個數(shù)。輸入: 輸入包含三行： 第一行為N，表示整數(shù)序列的長度(N = 100)； 第二行為N個整數(shù)，整數(shù)之間以一個空格分開； 第三行包含一個整數(shù)，為指定的數(shù)字m。輸出: 輸出為N個數(shù)中與m相同的數(shù)的個數(shù)。樣例輸入: 3 2 3 2 2樣例輸出: 2【上機練習】2.陶陶摘蘋果【1.6編程基礎(chǔ)之一維數(shù)組02】Noip2005普及組第1題 陶陶家的院子里有一棵蘋果樹，每到秋天樹上就會結(jié)出10個蘋果。蘋果成熟的時候，陶陶就會跑去摘蘋果。陶陶有個30厘米高的板凳，當她不能直接用手摘到蘋果的時候，就會踩到板凳上再試試。 現(xiàn)在已知10個蘋果到地面的高度，以及陶陶把手伸直的時候能夠

26、達到的最大高度，請幫陶陶算一下她能夠摘到的蘋果的數(shù)目。假設(shè)她碰到蘋果，蘋果就會掉下來。 輸入: 包括兩行數(shù)據(jù)。第一行包含10個100到200之間(包括100和200)的整數(shù)(以厘米為單位)分別表示10個蘋果到地面的高度，兩個相鄰的整數(shù)之間用一個空格隔開。第二行只包括一個100到120之間(包含100和120)的整數(shù)(以厘米為單位)，表示陶陶把手伸直的時候能夠達到的最大高度。輸出: 包括一行，這一行只包含一個整數(shù)，表示陶陶能夠摘到的蘋果的數(shù)目。樣例輸入: 100 200 150 140 129 134 167 198 200 111 110樣例輸出: 5【上機練習】3.計算書費【1.6編程基礎(chǔ)之

27、一維數(shù)組03】 下面是一個圖書的單價表： 計算概論 28.9元/本 數(shù)據(jù)結(jié)構(gòu)與算法 32.7元/本 數(shù)字邏輯 45.6元/本 C+程序設(shè)計教程 78元/本 人工智能 35 元/本 計算機體系結(jié)構(gòu) 86.2元/本 編譯原理 27.8元/本 操作系統(tǒng) 43元/本 計算機網(wǎng)絡(luò) 56元/本 JAVA程序設(shè)計 65元/本 給定每種圖書購買的數(shù)量，編程計算應(yīng)付的總費用。輸入: 輸入一行，包含10個整數(shù)(大于等于0，小于等于100)，分別表示購買的計算概論、數(shù)據(jù)結(jié)構(gòu)與算法、數(shù)字邏輯、C+程序設(shè)計教程、人工智能、計算機體系結(jié)構(gòu)、編譯原理、操作系統(tǒng)、計算機網(wǎng)絡(luò)、JAVA程序設(shè)計的數(shù)量（以本為單位）。每兩個整數(shù)用

28、一個空格分開。輸出: 輸出一行，包含一個浮點數(shù)f，表示應(yīng)付的總費用。精確到小數(shù)點后一位。樣例輸入: 1 5 8 10 5 1 1 2 3 4樣例輸出: 2140.2【上機練習】4.數(shù)組逆序重【1.6編程基礎(chǔ)之一維數(shù)組04】 將一個數(shù)組中的值按逆序重新存放。例如，原來的順序為8,6,5,4,1。要求改為1,4,5,6,8。輸入: 輸入為兩行：第一行數(shù)組中元素的個數(shù)n（1n100)，第二行是n個整數(shù)，每兩個整數(shù)之間用空格分隔。輸出: 輸出為一行：輸出逆序后數(shù)組的整數(shù)，每兩個整數(shù)之間用空格分隔。樣例輸入: 5 8 6 5 4 1樣例輸出: 1 4 5 6 8【上機練習】5.年齡與疾病【1.6編程基礎(chǔ)

29、之一維數(shù)組05】 某醫(yī)院想統(tǒng)計一下某項疾病的獲得與否與年齡是否有關(guān)，需要對以前的診斷記錄進行整理，按照0-18、19-35、36-60、61以上（含61）四個年齡段統(tǒng)計的患病人數(shù)占總患病人數(shù)的比例。輸入: 共2行，第一行為過往病人的數(shù)目n（0n=100)，第二行為每個病人患病時的年齡。輸出: 按照0-18、19-35、36-60、61以上(含61)四個年齡段輸出該段患病人數(shù)占總患病人數(shù)的比例，以百分比的形式輸出，精確到小數(shù)點后兩位。每個年齡段占一行，共四行。樣例輸入: 10 1 11 21 31 41 51 61 71 81 91樣例輸出: 20.00% 20.00% 20.00% 40.00

30、%【上機練習】6.校門外的樹【1.6編程基礎(chǔ)之一維數(shù)組06】Noip2005普及組第2題 某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米。我們可以把馬路看成一個數(shù)軸，馬路的一端在數(shù)軸0的位置，另一端在L的位置；數(shù)軸上的每個整數(shù)點，即0，1，2，L，都種有一棵樹。 由于馬路上有一些區(qū)域要用來建地鐵。這些區(qū)域用它們在數(shù)軸上的起始點和終止點表示。已知任一區(qū)域的起始點和終止點的坐標都是整數(shù)，區(qū)域之間可能有重合的部分。現(xiàn)在要把這些區(qū)域中的樹（包括區(qū)域端點處的兩棵樹）移走。你的任務(wù)是計算將這些樹都移走后，馬路上還有多少棵樹。 輸入: 第一行有兩個整數(shù)L（1 = L = 10000）和

31、 M（1 = M = 100），L代表馬路的長度，M代表區(qū)域的數(shù)目，L和M之間用一個空格隔開。接下來的M行每行包含兩個不同的整數(shù)，用一個空格隔開，表示一個區(qū)域的起始點和終止點的坐標。 對于20%的數(shù)據(jù)，區(qū)域之間沒有重合的部分；對于其它的數(shù)據(jù)，區(qū)域之間有重合的情況。輸出: 包括一行，這一行只包含一個整數(shù)，表示馬路上剩余的樹的數(shù)目。樣例輸入: 樣例輸出: 500 3 298 150 300 100 200 470 471 【上機練習】7.向量點積計算【1.6編程基礎(chǔ)之一維數(shù)組07】 在線性代數(shù)、計算幾何中，向量點積是一種十分重要的運算。給定兩個n維向量a=(a1,a2,.,an)和b=(b1,b2

32、,.,bn)，求點積ab=a1b1+a2b2+.+anbn。輸入: 第一行是一個整數(shù)n(1=n=1000)。 第二行包含n個整數(shù)a1,a2,.,an。 第三行包含n個整數(shù)b1,b2,.,bn。 相鄰整數(shù)之間用單個空格隔開。每個整數(shù)的絕對值都不超過1000。輸出: 一個整數(shù)，即兩個向量的點積結(jié)果。樣例輸入: 3 1 4 6 2 1 5樣例輸出: 36【上機練習】8.開關(guān)燈【1.5編程基礎(chǔ)之循環(huán)控制28】 假設(shè)有N盞燈(N為不大于5000的正整數(shù))，從1到N按順序依次編號，初始時全部處于開啟狀態(tài)；有M個人(M為不大于N的正整數(shù))也從1到M依次編號。 第一個人(1號)將燈全部關(guān)閉，第二個人(2號)將

33、編號為2的倍數(shù)的燈打開，第三個人(3號)將編號為3的倍數(shù)的燈做相反處理（即將打開的燈關(guān)閉，將關(guān)閉的燈打開）。依照編號遞增順序，以后的人都和3號一樣，將凡是自己編號倍數(shù)的燈做相反處理。 請問：當?shù)贛個人操作之后，哪幾盞燈是關(guān)閉的，按從小到大輸出其編號，其間用逗號間隔。輸入: 輸入正整數(shù)N和M，以單個空格隔開。輸出: 順次輸出關(guān)閉的燈的編號，其間用逗號間隔。樣例輸入: 10 10樣例輸出: 1,4,9【上機練習】9. 查找特定的值【1.9編程基礎(chǔ)之順序查找01】 在一個序列(下標從1開始)中查找一個給定的值，輸出第一次出現(xiàn)的位置。輸入: 第一行包含一個正整數(shù)n，表示序列中元素個數(shù)。1 =n= 10

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

35、不超過10000。 第三行包含一個整數(shù)x，為需要查找的特定值。x的絕對值不超過10000。輸出: 若序列中存在x，輸出x第一次出現(xiàn)的下標；否則輸出-1。樣例輸入: 5 2 3 6 7 3 3樣例輸出: 2【上機練習】10.不高興的津津【1.9編程基礎(chǔ)之順序查找03】Noip2004普及組第1題 津津上初中了。媽媽認為津津應(yīng)該更加用功學習，所以津津除了上學之外，還要參加媽媽為她報名的各科復習班。另外每周媽媽還會送她去學習朗誦、舞蹈和鋼琴。但是津津如果一天上課超過八個小時就會不高興，而且上得越久就會越不高興。假設(shè)津津不會因為其它事不高興，并且她的不高興不會持續(xù)到第二天。請你幫忙檢查一下津津下周的日

36、程安排，看看下周她會不會不高興；如果會的話，哪天最不高興。 輸入: 包括七行數(shù)據(jù)，分別表示周一到周日的日程安排。每行包括兩個小于10的非負整數(shù)，用空格隔開，分別表示津津在學校上課的時間和媽媽安排她上課的時間。輸出:包括一行，這一行只包含一個數(shù)字。如果不會不高興則輸出0，如果會則輸出最不高興的是周幾（用1, 2, 3, 4, 5, 6, 7分別表示周一，周二，周三，周四，周五，周六，周日）。如果有兩天或兩天以上不高興的程度相當，則輸出時間最靠前的一天。樣例輸入: 樣例輸出: 5 3 3 6 2 7 2 5 3 5 4 0 4 0 6 【上機練習】11.最大值和最小值的差【1.9編程基礎(chǔ)之順序查找

37、05】 輸出一個整數(shù)序列中最大的數(shù)和最小的數(shù)的差。輸入: 第一行為M，表示整數(shù)個數(shù)，整數(shù)個數(shù)不會大于10000； 第二行為M個整數(shù)，以空格隔開，每個整數(shù)的絕對值不會大于10000。輸出: 輸出M個數(shù)中最大值和最小值的差。樣例輸入: 5 2 5 7 4 2樣例輸出: 5 【上機練習】12.不與最大數(shù)相同的數(shù)字之和【1.9編程基礎(chǔ)之順序查找07】 輸出一個整數(shù)數(shù)列中不與最大數(shù)相同的數(shù)字之和。輸入: 輸入分為兩行： 第一行為N(N為接下來數(shù)的個數(shù)，N = 100)； 第二行N個整數(shù)，數(shù)與數(shù)之間以一個空格分開，每個整數(shù)的范圍是-1000,000到1000,000。輸出: 輸出為N個數(shù)中除去最大數(shù)其余數(shù)

38、字之和。樣例輸入: 3 1 2 3樣例輸出: 3 【上機練習】13.白細胞計數(shù)【1.9編程基礎(chǔ)之順序查找08】 醫(yī)院采樣了某臨床病例治療期間的白細胞數(shù)量樣本n份，用于分析某種新抗生素對該病例的治療效果。為了降低分析誤差，要先從這n份樣本中去除一個數(shù)值最大的樣本和一個數(shù)值最小的樣本，然后將剩余n-2個有效樣本的平均值作為分析指標。同時，為了觀察該抗生素的療效是否穩(wěn)定，還要給出該平均值的誤差，即所有有效樣本（即不包括已扣除的兩個樣本）與該平均值之差的絕對值的最大值。 現(xiàn)在請你編寫程序，根據(jù)提供的n個樣本值，計算出該病例的平均白細胞數(shù)量和對應(yīng)的誤差。輸入: 輸入的第一行是一個正整數(shù)n（2 n= 30

39、0），表明共有n個樣本。 以下共有n行，每行為一個浮點數(shù)，為對應(yīng)的白細胞數(shù)量，其單位為109/L。數(shù)與數(shù)之間以一個空格分開。輸出: 輸出為兩個浮點數(shù)，中間以一個空格分開。分別為平均白細胞數(shù)量和對應(yīng)的誤差，單位也是109/L。計算結(jié)果需保留到小數(shù)點后2位。樣例輸入: 樣例輸出: 5 11.00 1.00 12.0 13.0 11.0 9.0 10.0 【上機練習】14.直方圖【1.9編程基礎(chǔ)之順序查找09】 給定一個非負整數(shù)數(shù)組，統(tǒng)計里面每一個數(shù)的出現(xiàn)次數(shù)。我們只統(tǒng)計到數(shù)組里最大的數(shù)。 假設(shè) Fmax（Fmax10000）是數(shù)組里最大的數(shù)，那么我們只統(tǒng)計0,1,2.Fmax里每個數(shù)出現(xiàn)的次數(shù)。輸

40、入: 第一行n是數(shù)組的大小。1 = n = 10000。 緊接著一行是數(shù)組的n個元素。輸出: 按順序輸出每個數(shù)的出現(xiàn)次數(shù)，一行一個數(shù)。如果沒有出現(xiàn)過，則輸出0。 對于例子中的數(shù)組，最大的數(shù)是3，因此我們只統(tǒng)計0,1,2,3的出現(xiàn)頻數(shù)。樣例輸入: 5 1 1 2 3 1樣例輸出: 0 3 1 1 【上機練習】15.最長平臺【1.9編程基礎(chǔ)之順序查找12】 已知一個已經(jīng)從小到大排序的數(shù)組，這個數(shù)組的一個平臺（Plateau）就是連續(xù)的一串值相同的元素，并且這一串元素不能再延伸。例如，在 1，2，2，3，3，3，4，5，5，6中1，2-2，3-3-3，4，5-5，6都是平臺。試編寫一個程序，接收一個

41、數(shù)組，把這個數(shù)組最長的平臺找出 來。在上面的例子中3-3-3就是最長的平臺。輸入: 第一行有一個整數(shù)n，為數(shù)組元素的個數(shù)。第二行有n個整數(shù)，整數(shù)之間以一個空格分開。輸出: 輸出最長平臺的長度。樣例輸入: 10 1 2 2 3 3 3 4 5 5 6樣例輸出: 3 【上機練習】16.整數(shù)去重【1.9編程基礎(chǔ)之順序查找13】 給定含有n個整數(shù)的序列，要求對這個序列進行去重操作。所謂去重，是指對這個序列中每個重復出現(xiàn)的數(shù)，只保留該數(shù)第一次出現(xiàn)的位置，刪除其余位置。輸入: 輸入包含兩行： 第一行包含一個正整數(shù)n（1 = n = 20000），表示第二行序列中數(shù)字的個數(shù)； 第二行包含n個整數(shù)，整數(shù)之間以

42、一個空格分開。每個整數(shù)大于等于10、小于等于100。輸出: 輸出只有一行，按照輸入的順序輸出其中不重復的數(shù)字，整數(shù)之間用一個空格分開。樣例輸入: 5 10 12 93 12 75樣例輸出: 10 12 93 75【上機練習】17.鋪地毯【1.9編程基礎(chǔ)之順序查找14】Noip2011提高組第1題 為了準備一個獨特的頒獎典禮，組織者在會場的一片矩形區(qū)域（可看做是平面直角坐標系的第一象限）鋪上一些矩形地毯。一共有n張地毯，編號從1到n。現(xiàn)在將這些地毯按照編號從小到大的順序平行于坐標軸先后鋪設(shè)，后鋪的地毯覆蓋在前面已經(jīng)鋪好的地毯之上。地毯鋪設(shè)完成后，組織者想知道覆蓋地面某個點的最上面的那張地毯的編號

43、。注意：在矩形地毯邊界和四個頂點上的點也算被地毯覆蓋。 輸入輸出樣例1說明：如下圖，1號地毯用實線表示，2號地毯用虛線表示，3號用雙實線表示，覆蓋點（2，2）的最上面一張地毯是3號地毯。 輸入輸出樣例2說明：如下圖，1號地毯用實線表示，2號地毯用虛線表示，3號用雙實線表示，覆蓋點（4，5）的最上面一張地毯是3號地毯。【上機練習】輸入: 第一行，一個整數(shù)n，表示總共有n張地毯。 接下來的n行中，第i+1行表示編號i的地毯的信息，包含四個正整數(shù)a，b，g，k，每兩個整數(shù)之間用一個空格隔開，分別表示鋪設(shè)地毯的左下角的坐標（a，b）以及地毯在x軸和y軸方向的長度。 第n+2行包含兩個正整數(shù)x和y，表示

44、所求的地面的點的坐標（x，y）。輸出: 輸出共1行，一個整數(shù)，表示所求的地毯的編號；若此處沒有被地毯覆蓋則輸出-1。樣例輸入: 樣例輸出:樣例 #1： 樣例 #1：3 31 0 2 30 2 3 32 1 3 32 2樣例 #2： 樣例 #2：3 -11 0 2 30 2 3 32 1 3 34 5第二節(jié)第二節(jié) 二維數(shù)組二維數(shù)組一、二維數(shù)組的定義當一維數(shù)組元素的類型也是一維數(shù)組時，便構(gòu)成了“數(shù)組的數(shù)組”，即二維數(shù)組。二維數(shù)組定義的一般格式：數(shù)據(jù)類型 數(shù)組名常量表達式1 常量表達式2 ；例如：int a410;a數(shù)組實質(zhì)上是一個有4行、10列的表格，表格中可儲存40個元素。第1行第1列對應(yīng)a數(shù)組

45、的a00，第n行第m列對應(yīng)數(shù)組元素an-1m-1。說明：當定義的數(shù)組下標有多個時，我們稱為多維數(shù)組，下標的個數(shù)并不局限在一個或二個，可以任意多個，如定義一個三維數(shù)組a和四維數(shù)組b：int a10035;int b10010035;多維的數(shù)組引用賦值等操作與二維數(shù)組類似。二、二維數(shù)組元素的引用二維數(shù)組的數(shù)組元素引用與一維數(shù)組元素引用類似，區(qū)別在于二維數(shù)組元素的引用必須給出兩個下標。引用的格式為： 下標1下標2說明：顯然，每個下標表達式取值不應(yīng)超出下標所指定的范圍，否則會導致致命的越界錯誤。例如,設(shè)有定義：int a35;則表示a是二維數(shù)組（相當于一個3*5的表格），共有3*5=15個元素，它們是

46、：a00 a01 a02 a03 a04a10 a11 a12 a13 a14a20 a21 a22 a23 a24因此可以看成一個矩陣（表格），a23即表示第3行第4列的元素。三、二維數(shù)組的初始化二維數(shù)組的初始化和一維數(shù)組類似?？梢詫⒚恳恍蟹珠_來寫在各自的括號里，也可以把所有數(shù)據(jù)寫在一個括號里。例如：int direct42 = 1,0,0,1,-1,0,0,-1 int direct42 = 1,0,0,1,-1,0,0,-1 /盡量不要用四、二維數(shù)組程序設(shè)計例5.8 設(shè)有一程序#include#include#includeconst int n=3;using namespace st

47、d;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(5)aji; coutendl; return 0;程序的輸入:2 1 33 3 11 2 1程序的輸出:2 3 11 3 23 1 1例5.9 已知一個6*6的矩陣（方陣），把矩陣二條對角線上的元素值加上10，然后輸出這個新矩陣?！痉治觥?矩陣即表格，是一個二維數(shù)組，有6行6列共36個元素，每個矩陣都有二條對角線，本題難點在于對角線的元素怎么確定。#

48、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; +i) /更改對角線上元素的值 for (int j=1; j=6; +j) if (i=j)|(i+j=7) aij+=10; /尋找對角線的特征 for (int i=1; i=6; +i) /輸出6行6列的矩陣元素 for (int j=1; j=6; +j) coutsetw(5)aij; coutendl; return 0;例5.10 大

49、部分元素是0的矩陣稱為稀疏矩陣，假設(shè)有k個非0元素，則可把稀疏矩陣用K*3的矩陣簡記之，其中第一列是行號，第二列是列號，第三列是該行、該列下的非元素的值。如：0 0 0 5 寫簡記成： 1 4 5 /第1行第4列有個數(shù)是50 2 0 0 2 2 2 /第2行第2列有個數(shù)是20 1 0 0 3 2 1 /第3行第2列有個數(shù)是1試編程讀入一稀疏矩陣，轉(zhuǎn)換成簡記形式，并輸出?！痉治觥?本題中需要解決的主要問題是查找非零元素并記憶位置。將原始矩陣存于數(shù)組a。轉(zhuǎn)換后的矩陣存于數(shù)組b，當然b數(shù)組的行數(shù)可以控制在一個小范圍內(nèi)。#include#includeconst int n=3,m=5;using n

50、amespace 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 (int j=1; j=m; +j) if (aij!=0) /找到非零值，存儲 +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;運行結(jié)果：輸入： 0 0 0 0 5 0 0 4

51、 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 6 4 1 圖5-1 圖5-2【問題分析】觀察圖5-1，大家不容易找到規(guī)律，但是如果將它轉(zhuǎn)化為圖5-2，不難發(fā)現(xiàn)楊輝三角形其實就是一個二維表的小三角形部分，假設(shè)通過二維數(shù)組yh存儲，每行首尾元素為1，且其中任意一個非首位元素yhij的值其實就是yhi-1j-1與yhi-1j的和，另外每一行的元素個數(shù)剛好等于行數(shù)。有了數(shù)組元素的值，要打印楊輝三角形，只需

52、要控制好輸出起始位置就行了。#include#includeusing namespace std;int main() int a1111; a11=1;/設(shè)定第一行的值 for (int i=2; i=10; +i)/從第二行開始推 ai1=1; aii=1;/設(shè)定每一行的首尾值為1 for (int j=2; j=i-1; +j)/當前行非首尾的數(shù) aij=ai-1j-1+ai-1j; /每個數(shù)等于上一行的二個數(shù)之和 for (int i=1; i=10; i+) if (i!=10) coutsetw(30-3*i) ;/控制每行的起始位置，即空格數(shù)量 for (int j=1; j=

53、i; j+) coutsetw(6)aij; coutendl; return 0; 例5.12 輸入一串字符,字符個數(shù)不超過100,且以“.”結(jié)束。 判斷它們是否構(gòu)成回文?！痉治觥克^回文指從左到右和從右到左讀一串字符的值是一樣的，如12321,ABCBA,AA等。先讀入要判斷的一串字符（放入數(shù)組letter中），并記住這串字符的長度，然后首尾字符比較，并不斷向中間靠攏，就可以判斷出是否為回文。程序如下：#includeusing namespace std;int main() char ch,letter101; int i=0,j=1; coutch; while (ch!=.)/讀入

54、一個字符串以.號結(jié)束 +i; letteri=ch; cinch; while (j=i) coutYesendl; else coutNoendl; return 0;例5.13 蛇形填數(shù) 在n*n方陣里填入1,2,3,n*n，要求填成蛇形。例如n=4時方陣為： 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 上面的方陣中，多余的空格只是為了便于觀察規(guī)律，不必嚴格輸出，n=8?！痉治觥浚?類比數(shù)學中的矩陣，我們可以用一個所謂的二維數(shù)組來儲存題目中的方陣。只需聲明一個int aMAXNMAXN，就可以獲得一個大小為MAXNMAXN的方陣。在聲明時，兩維的大小不必相

55、同，因此也可以聲明int a3050這樣的數(shù)組，第一維下標范圍是0,1,2,29，第二維下標范圍是0,1,2,49。 讓我們從1開始依次填寫。設(shè)“筆”的坐標為(x,y)，則一開始x=0，y=n-1，即第0行，第n-1列（別忘了行列的范圍是0到n-1，沒有第n列）?！肮P”的移動軌跡是：下，下，下，左，左，左，上，上，上，右，右，下，下，左，上?？傊?，先是下，到不能填了為止，然后是左，接著是上，最后是右?！安荒芴睢笔侵冈僮呔统鼋纾ɡ?5），或者再走就要走到以前填過的格子（例如1213）。如果我們把所有格子初始為0，就能很方便地加以判斷。#include#include#define MAXN 1

56、0int 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 & !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;【說明】： 這段程序

57、充分利用了C+語言簡潔的優(yōu)勢。首先，賦值x=0和y=n-1后馬上要把它們作為a數(shù)組的下標，因此可以合并完成；tot和a0n-1都要賦值1，也可以合并完成。這樣，我們用一條語句完成了多件事情，而且并沒有犧牲程序的可讀性，這段代碼的含義顯而易見。 那4條while語句有些難懂，不過十分相似，因此只需介紹其中的第一條：不斷向下走，并且填數(shù)。我們的原則是：先判斷，再移動，而不是走一步以后發(fā)現(xiàn)越界了再退回來。這樣，我們需要進行“預(yù)判”，即是否越界，以及如果繼續(xù)往下走會不會到達一個已經(jīng)填過的格子。越界只需判斷x+1n，因為y值并沒有修改；下一個格子是(x+1,y)，因此只需ax+1y=0，簡寫成!ax+1

58、y（其中!是“邏輯非”運算符）。 細心的讀者也許會發(fā)現(xiàn)這里的一個“潛在bug”；如果越界，x+1會等于n，ax+1y將訪問非法內(nèi)存！幸運的是，這樣的擔心是不必要的。&是短路運算符。如果x+1n為假，將不會計算!ax+1y，也就不會越界了。 至于為什么是+tot而不是tot+，留給讀者思考?！旧蠙C練習】1.矩陣交換行【1.8編程基礎(chǔ)之多維數(shù)組01】 給定一個5*5的矩陣(數(shù)學上，一個rc的矩陣是一個由r行c列元素排列成的矩形陣列)，將第n行和第m行交換，輸出交換后的結(jié)果。輸入: 輸入共6行，前5行為矩陣的每一行元素,元素與元素之間以一個空格分開。 第6行包含兩個整數(shù)m、n，以一個空格分開

59、（1 = m,n = 5）。輸出: 輸出交換之后的矩陣，矩陣的每一行元素占一行，元素之間以一個空格分開。樣例輸入: 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 4 6 1 2 2 1 2【上機練習】2.同行列對角線的格【1.8編程基礎(chǔ)之多維數(shù)組02】 輸入三個自然數(shù)N，i，j（1=i=n，1=j=n），輸出在一個N*N格的棋盤中(行列均從1開始編號)，與格子(i，j)同行、同列、同一對角線的所有格子的位置。如：n=4，i=2，j=3表示了棋盤中的第二

60、行第三列的格子，如下圖：當n=4，i=2，j=3時，輸出的結(jié)果是：(2,1) (2,2) (2,3) (2,4) 同一行上格子的位置(1,3) (2,3) (3,3) (4,3) 同一列上格子的位置(1,2) (2,3) (3,4) 左上到右下對角線上的格子的位置(4,1) (3,2) (2,3) (1,4) 左下到右上對角線上的格子的位置【上機練習】輸入: 一行，三個自然數(shù)N，i，j，相鄰兩個數(shù)之間用單個空格隔開(1=N=10)。輸出: 第一行：從左到右輸出同一行格子位置； 第二行：從上到下輸出同一列格子位置； 第三行：從左上到右下輸出同一對角線格子位置； 第四行：從左下到右上輸出同一對角線格子位置。 其中每個格子位置用如下格式輸出：(x,y