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

2、逐個和平均分比較，把低于平均分的成績打印出來。如果，用簡單變量a1，a2,，a50存儲這些數據，要用50個變量保存輸入的數據，程序片斷如下：cina1a2a10;cina41a42a50;注意，如果真正要像上面這樣編寫程序，則上面的所有省略號必須用完整的語句寫出來。可以看出，這樣的程序是多么繁瑣。如果說處理的數據規模達到成千上萬，上面的例子單單讀入就會異常復雜，電腦的優勢沒有得到體現。從以上的討論可以看出，如果只使用簡單變量處理大量數據，就必須使用大量只能單獨處理的變量，即使是簡單問題也需要編寫冗長的程序。選手們可能已經看出，我們需要把一大批具有相同性質的數據組合成一個新類型的變量，可以用簡單

3、的程序（比如循環50次）對這個新變量的各個分量進行相同的處理，每個分量仍然保留單個變量的所有性質（在上面的例子中，各分量是整型變量或實型變量的性質）。如果能像數學中使用下標變量ai形式表示這50個數，則問題就容易實現。在C+語言中，具有下標性質的數據類型是數組。如果使用數組，上面的問題就變得十分簡單、清晰。例如，讀入50個學生的成績，只需寫如下語句即可： for (int i=1;iai;在這里引用了帶下標的變量（分量變量稱為數組元素）ai來代替a1,a2,a50,方括號中的i稱為下標，當循環變量i=1時ai就是a1；當i=2時ai就是a2；當i=50時ai就是a50。輸入的時候，讓i從1變化

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

5、個元素只帶有一個下標時，我們稱這樣的數組為一維數組。數組的定義格式如下：類型標識符 數組名常量表達式說明：數組名的命名規則與變量名的命名規則一致。常量表達式表示數組元素的個數。可以是常量和符號常量，但不能是變量。例如：int a10; /數組a定義是合法的 int bn; /數組b定義是非法的 其中，a是一維數組的數組名，該數組有10個元素，依次表示為：a0,a1,a2,a3,a4,a5，a6,a7,a8,a9。需要注意的是：a10不屬于該數組的空間范圍。當在說明部分定義了一個數組變量之后,C+編譯程序為所定義的數組在內存空間開辟一串連續的存儲單元，每個數組第一個元素的下標都是0，因此第一個元

6、素為第0個數組元素。例如：上例中的a數組在內存的存儲如表所示： a數組共有10個元素組成，在內存中10個數組元素共占10個連續的存儲單元。a數組最小下標為0，最大下標9。按定義a數組所有元素都是整型變量。a0a1a2a3a4a5a6a7a8a9三、一組數組的引用 通過給出的數組名稱和這個元素在數組中的位置編號(即下標)，程序可以引用這個數組中的任何一個元素。 一維數組元素的引用格式： 數組名下標例如：若i、j都是int型變量，則 a5 ai+j ai+ 都是合法的元素。說明： (1)下標可以是任意值為整型的表達式，該表達式里可以包含變量和函數調用。引用時，下標值應在數組定義的下標值范圍內。 (

7、2)數組的精妙在于下標可以是變量，通過對下標變量值的靈活控制，達到靈活處理數組元素的目的。 (3)C+語言只能逐個引用數組元素，而不能一次引用整個數組。(4)數組元素可以像同類型的普通變量那樣使用，對其進行賦值和運算的操作，和普通變量完全相同。例如： c10=34;實現了給c10賦值為34。四、一維數組的初始化 數組的初始化可以在定義時一并完成。格式： 類型標識符 數組名常量表達式=值1，值2，例如：int a5=1,2,3,4,5說明：(1)在初值列表中可以寫出全部數組元素的值，也可以寫出部分。例如，以下方式可以對數組進行初始化：int x10=0,1,2,3,4;該方法僅對數組的前5個元素

8、依次進行初始化，其余值為0。(2)對數組元素全部初始化為0，可以簡寫為：。例如： int a5=; 將數組a的5個元素都初始化為0。【說明】 程序1、程序2和程序3的區別在于數組定義在int main()之外與之內，程序1中數組定義放在int main()之外，其初始值是0值。程序2中數組定義放在int main()之內，其初始值是隨機的。程序2中數組定義放在int main()之內，只給a0、a1賦初值，但后面的a2a4元素自動賦0值。五、數組越界 C+語言規定，使用數組時，要注意： (1)、數組元素的下標值為非負整數。 (2)、在定義元素個數的下標范圍內使用。 然而，當在程序中把下標寫成負

9、數、大于數組元素的個數時，程序編譯的時候是不會出錯的。例如： int a10; a-3=5; a20=15; a10=20; int k=a30 這些語句的語法是正確的，能夠通過程序的編譯。然而，它們要訪問的數組元素并不在數組的存儲空間的，這種現象叫數組越界。例如下面程序：#includeusing namespace std; int main() int a5; for (int i=0;i=10;i+) ai=i; coutai ; return 0;【說明】 該程序能夠通過編譯，也能運行出結果，程序的問題是定義a5，使用時數組下標超過了4。C+語言中，數組越界訪問系統時不一定會給出任何

10、的提示，也就是說，程序可以超出數組邊界進行讀/寫，從而造成內存的混亂。 數組越界是實際編程中常見的錯誤，而且這類錯誤往往難以捕捉。因為越界語句本身并不一定導致程序立即出錯，可能在遇到某些數據時才導致錯誤，有時由于越界，意外地改變了變量或指令，導致在調試器里調試的時候，程序不按照應當的次序運行的怪現象。六、一維數組的應用例5.1 輸入n個數,要求程序按輸入時的逆序把這n個數打印出來，已知整數不超過100個。也就是說，按輸入相反順序打印這n個數。【分析】我們可定義一個數組a用以存放輸入的n個數, 然后將數組a中的內容逆序輸出。#includeint a100;int main() int x,n=

11、0; while(scanf(%d,&x)=1) an+=x; /相當an=x;n+; for (int i=n-1;i=1;-i) printf(%d ,ai); /注意%d后面有一個空格，保證行首行尾均無空格 printf(%dn,a0); return 0;【說明】： 語句int a100聲明了一個包含100個整型變量的數組，它們是：a0，a1，a2，a99。注意，沒有a100。在上述程序中，數組a被聲明在main函數的外面。只有放在外面時，數組a才可以開得很大；放在main函數內時，數組稍大就會異常退出。它的道理將在后面討論，只需要記住規則即可。 數組不能夠進行賦值操作：如果聲明的是i

12、nt aMAXN，bMAXN,是不能賦值b=a的(Pascal語言可以的)。如果要從數組a復制k個元素到數組b，可以這樣做：memcpy(b,a,sizeof(int)*k)。當然了，如果數組a和b都是浮點型的，復制時要寫成memcpy(b,a,sizeof(double)*k)。如果需要把數組a全部復制到數組b中，可以寫得簡單一些：memcpy(b,a,sizeof(a)。使用memcpy函數要包含頭文件cstring。 例5.2 將a數組中第一個元素移到數組末尾,其余數據依次往前平移一個位置。【分析】為完成題目所要求的操作，其算法應該包括以下幾個主要步驟： 把第一個元素的值取出放在一個臨時

13、單元 temp中； 通過 a2a1, a3a2, a4a3， anan-1,實現其余元素前移 將 temp值送入an. #include#include /調用setw函數需注明使用該庫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

14、函數控制輸出場寬return 0; 運行結果 : 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編了號。第一個服務員把所有的房間門都打開了，第二個服務員把所有編號是2的倍數的房間“相反處理”，第三個服務員把所有編號是3的倍數的房間作“相反處理”，以后每個服務員都是如此。當第100個服務員來過后，哪幾扇門是打開的。（所謂“相反處理”是：原來開著的門關上，原來關上的門打開。）【分析】此題較簡單，用a1,a2,an表示編號為1，2，3，,n的門是否開著。模擬這些操作即可，參考

15、程序如下：#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 i=1;i=100;+i) if (ai) if(first) first=0; else printf( ); printf(%d,i); printf(n);return 0;運行結果：14 9 16 25 36 49 64 81 100【說明】： me

16、mset(a,0,sizeof(a)的作用是把數組a清零，它在cstring中定義。雖然也能用for循環完成相同的任務，但是用memset又方便又快捷。另一個技巧在輸出：為了避免輸出多余空格，設置了一個標志變量first，可以表示當前要輸出是否為第一個。第一個變量前不應該有空格，但其他都有。例5.4 約瑟夫問題：N個人圍成一圈，從第一個人開始報數，數到M的人出圈；再由下一個人開始報數，數到M的人出圈；輸出依次出圈的人的編號。N，M由鍵盤輸入。【分析】 （1）由于對于每個人只有出圈和沒有圈兩種狀態，因此可以用布爾型標志數組存儲游戲 過程中每個人的狀態。不妨用true表示出圈，false 表示沒有

17、出圈。 （2）開始的時候，給標志數組賦初值為false，即全部在圈內。 （3）模擬報數游戲的過程，直到所有的人出圈為止。程序如下：#includeusing namespace std;int n,m,s,f,t;bool a101;/根據題意開出數組大小int main() cinnm;/共n人，報到m出圈 coutendl; for (t=1;t=n;+t) at=false; /等同于memset(a,0,sizeof(a),要調用cstring庫 f=0; t=0; s=0; /剛開始所有變量默認值也是0,或者用f=t=s=0; do +t;/逐個枚舉圈中的所有位置 if (t=n+1

18、) t=1;/數組模擬環狀，最后一個與第一個相連 if (at=false) +s;/第t個位置上有人則報數 if (s=m) /當前報的數是m s=0;/計數器清零 coutt ;/輸出出圈人的編號 at=true;/此處的人已出圈，設置為空 f+; /出圈的人數增加一個 while(f!=n);/直到所有的人都出圈為止 return 0;運行結果：輸入： 8 5輸出： 5 2 8 7 1 4 6 3這是一個在算法設計上很有名氣的經典約瑟夫（Josephu）問題，它有很多變例。如猴子選大王、持密碼報數、狐貍追兔子等（見上機練習）。例5.5 輸入n個整數,存放在數組a1至an中，輸出最大數所在

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

20、for(i=2;imaxa) /枚舉數組，找到最大數和位置 maxa=ai;k=i; coutk; /輸出最大數所在數組中的位置 return 0;例5.6 編程輸入十個正整數，然后自動按從大到小的順序輸出。（冒泡排序）【問題分析】 用循環把十個數輸入到A數組中； 從a1到a10，相鄰的兩個數兩兩相比較，即： a1與a2比，a2與a3比，a9與a10比。 只需知道兩個數中的前面那元素的標號，就能進行與后一個序號元素（相鄰數）比較，可寫成通用形式ai與ai+1比較，那么，比較的次數又可用1( n-i )循環進行控制(即循環次數與兩兩相比較時前面那個元素序號有關) ； 在每次的比較中，若較大的數在

21、后面，就把前后兩個對換，把較大的數調到前面，否則不需調換位置。下面例舉5個數來說明兩兩相比較和交換位置的具體情形： 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 經過（1（n-1）次比較后，將3調到了末尾。 經過第一輪的1 (N-1)次比較，就能把十個數中的最小數調到最末尾位置，第二輪比較1 (N-2)次進行同樣處理，又把這一輪所比較的“最小數”調到所比較范圍的“最末尾”位置；每進行一輪兩兩比較

22、后，其下一輪的比較范圍就減少一個。最后一輪僅有一次比較。在比較過程中，每次都有一個“最小數”往下“掉”，用這種方法排列順序，常被稱之為“冒泡法”排序。程序如下：#includeusing namespace std;const int n=10;int an+1;/定義數組int main() for (int i=1; iai;/輸入十個數 for (int i=1; i=n-1; +i)/冒泡法排序 for (int j=1; j=n-i; +j) /兩兩相比較 if (ajaj+1) swap(aj,aj+1);/比較與交換 for (int i=1; i=n; +i) cout ai;

23、 /輸出排序后的十個數 coutendl; return 0;運行結果：輸入： 2 5 8 6 12 34 65 22 16 55輸出： 65 55 34 22 16 12 8 6 5 2例5.7 用篩法求出100以內的全部素數，并按每行五個數顯示。【問題分析】質數篩法是這樣的：1開一個大的bool型數組prime，大小就是n+1就可以，先把所有的下標為true。2然后：for( i=2; i=sqrt(n);+i ) if(primei) for( j=2; jsqrt(30)算法結束。第 3 步把prime值為true的下標輸出來：結果是 2 3 5 7 11 13 17 19 23 29

24、程序如下：#include#include /在Dev C+中可調用數學函數庫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 (primei) for (int j=2; j=n/i; +j) primei*j=false; for (int i=2,t=0; i=n;

25、 +i) if (primei) coutsetw(5)i; +t; if (t%5=0) coutendl; return 0;【上機練習】1、與指定數字相同的數的個數【1.6編程基礎之一維數組01】 輸出一個整數序列中與指定數字相同的數的個數。輸入: 輸入包含三行： 第一行為N，表示整數序列的長度(N = 100)； 第二行為N個整數，整數之間以一個空格分開； 第三行包含一個整數，為指定的數字m。輸出: 輸出為N個數中與m相同的數的個數。樣例輸入: 3 2 3 2 2樣例輸出: 2【上機練習】2.陶陶摘蘋果【1.6編程基礎之一維數組02】Noip2005普及組第1題 陶陶家的院子里有一棵蘋

26、果樹，每到秋天樹上就會結出10個蘋果。蘋果成熟的時候，陶陶就會跑去摘蘋果。陶陶有個30厘米高的板凳，當她不能直接用手摘到蘋果的時候，就會踩到板凳上再試試。 現在已知10個蘋果到地面的高度，以及陶陶把手伸直的時候能夠達到的最大高度，請幫陶陶算一下她能夠摘到的蘋果的數目。假設她碰到蘋果，蘋果就會掉下來。 輸入: 包括兩行數據。第一行包含10個100到200之間(包括100和200)的整數(以厘米為單位)分別表示10個蘋果到地面的高度，兩個相鄰的整數之間用一個空格隔開。第二行只包括一個100到120之間(包含100和120)的整數(以厘米為單位)，表示陶陶把手伸直的時候能夠達到的最大高度。輸出: 包

27、括一行，這一行只包含一個整數，表示陶陶能夠摘到的蘋果的數目。樣例輸入: 100 200 150 140 129 134 167 198 200 111 110樣例輸出: 5【上機練習】3.計算書費【1.6編程基礎之一維數組03】 下面是一個圖書的單價表： 計算概論 28.9元/本 數據結構與算法 32.7元/本 數字邏輯 45.6元/本 C+程序設計教程 78元/本 人工智能 35 元/本 計算機體系結構 86.2元/本 編譯原理 27.8元/本 操作系統 43元/本 計算機網絡 56元/本 JAVA程序設計 65元/本 給定每種圖書購買的數量，編程計算應付的總費用。輸入: 輸入一行，包含10

28、個整數(大于等于0，小于等于100)，分別表示購買的計算概論、數據結構與算法、數字邏輯、C+程序設計教程、人工智能、計算機體系結構、編譯原理、操作系統、計算機網絡、JAVA程序設計的數量（以本為單位）。每兩個整數用一個空格分開。輸出: 輸出一行，包含一個浮點數f，表示應付的總費用。精確到小數點后一位。樣例輸入: 1 5 8 10 5 1 1 2 3 4樣例輸出: 2140.2【上機練習】4.數組逆序重【1.6編程基礎之一維數組04】 將一個數組中的值按逆序重新存放。例如，原來的順序為8,6,5,4,1。要求改為1,4,5,6,8。輸入: 輸入為兩行：第一行數組中元素的個數n（1n100)，第二

29、行是n個整數，每兩個整數之間用空格分隔。輸出: 輸出為一行：輸出逆序后數組的整數，每兩個整數之間用空格分隔。樣例輸入: 5 8 6 5 4 1樣例輸出: 1 4 5 6 8【上機練習】5.年齡與疾病【1.6編程基礎之一維數組05】 某醫院想統計一下某項疾病的獲得與否與年齡是否有關，需要對以前的診斷記錄進行整理，按照0-18、19-35、36-60、61以上（含61）四個年齡段統計的患病人數占總患病人數的比例。輸入: 共2行，第一行為過往病人的數目n（0n=100)，第二行為每個病人患病時的年齡。輸出: 按照0-18、19-35、36-60、61以上(含61)四個年齡段輸出該段患病人數占總患病人

30、數的比例，以百分比的形式輸出，精確到小數點后兩位。每個年齡段占一行，共四行。樣例輸入: 10 1 11 21 31 41 51 61 71 81 91樣例輸出: 20.00% 20.00% 20.00% 40.00%【上機練習】6.校門外的樹【1.6編程基礎之一維數組06】Noip2005普及組第2題 某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米。我們可以把馬路看成一個數軸，馬路的一端在數軸0的位置，另一端在L的位置；數軸上的每個整數點，即0，1，2，L，都種有一棵樹。 由于馬路上有一些區域要用來建地鐵。這些區域用它們在數軸上的起始點和終止點表示。已知任一區域的起始點和

31、終止點的坐標都是整數，區域之間可能有重合的部分。現在要把這些區域中的樹（包括區域端點處的兩棵樹）移走。你的任務是計算將這些樹都移走后，馬路上還有多少棵樹。 輸入: 第一行有兩個整數L（1 = L = 10000）和 M（1 = M = 100），L代表馬路的長度，M代表區域的數目，L和M之間用一個空格隔開。接下來的M行每行包含兩個不同的整數，用一個空格隔開，表示一個區域的起始點和終止點的坐標。 對于20%的數據，區域之間沒有重合的部分；對于其它的數據，區域之間有重合的情況。輸出: 包括一行，這一行只包含一個整數，表示馬路上剩余的樹的數目。樣例輸入: 樣例輸出: 500 3 298 150 30

32、0 100 200 470 471 【上機練習】7.向量點積計算【1.6編程基礎之一維數組07】 在線性代數、計算幾何中，向量點積是一種十分重要的運算。給定兩個n維向量a=(a1,a2,.,an)和b=(b1,b2,.,bn)，求點積ab=a1b1+a2b2+.+anbn。輸入: 第一行是一個整數n(1=n=1000)。 第二行包含n個整數a1,a2,.,an。 第三行包含n個整數b1,b2,.,bn。 相鄰整數之間用單個空格隔開。每個整數的絕對值都不超過1000。輸出: 一個整數，即兩個向量的點積結果。樣例輸入: 3 1 4 6 2 1 5樣例輸出: 36【上機練習】8.開關燈【1.5編程基

33、礎之循環控制28】 假設有N盞燈(N為不大于5000的正整數)，從1到N按順序依次編號，初始時全部處于開啟狀態；有M個人(M為不大于N的正整數)也從1到M依次編號。 第一個人(1號)將燈全部關閉，第二個人(2號)將編號為2的倍數的燈打開，第三個人(3號)將編號為3的倍數的燈做相反處理（即將打開的燈關閉，將關閉的燈打開）。依照編號遞增順序，以后的人都和3號一樣，將凡是自己編號倍數的燈做相反處理。 請問：當第M個人操作之后，哪幾盞燈是關閉的，按從小到大輸出其編號，其間用逗號間隔。輸入: 輸入正整數N和M，以單個空格隔開。輸出: 順次輸出關閉的燈的編號，其間用逗號間隔。樣例輸入: 10 10樣例輸出

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

35、開始)中查找一個給定的值，輸出第一次出現的位置。輸入: 第一行包含一個正整數n，表示序列中元素個數。1 =n= 10000。 第二行包含n個整數，依次給出序列的每個元素，相鄰兩個整數之間用單個空格隔開。元素的絕對值不超過10000。 第三行包含一個整數x，為需要查找的特定值。x的絕對值不超過10000。輸出: 若序列中存在x，輸出x第一次出現的下標；否則輸出-1。樣例輸入: 5 2 3 6 7 3 3樣例輸出: 2【上機練習】10.不高興的津津【1.9編程基礎之順序查找03】Noip2004普及組第1題 津津上初中了。媽媽認為津津應該更加用功學習，所以津津除了上學之外，還要參加媽媽為她報名的各

36、科復習班。另外每周媽媽還會送她去學習朗誦、舞蹈和鋼琴。但是津津如果一天上課超過八個小時就會不高興，而且上得越久就會越不高興。假設津津不會因為其它事不高興，并且她的不高興不會持續到第二天。請你幫忙檢查一下津津下周的日程安排，看看下周她會不會不高興；如果會的話，哪天最不高興。 輸入: 包括七行數據，分別表示周一到周日的日程安排。每行包括兩個小于10的非負整數，用空格隔開，分別表示津津在學校上課的時間和媽媽安排她上課的時間。輸出:包括一行，這一行只包含一個數字。如果不會不高興則輸出0，如果會則輸出最不高興的是周幾（用1, 2, 3, 4, 5, 6, 7分別表示周一，周二，周三，周四，周五，周六，周

37、日）。如果有兩天或兩天以上不高興的程度相當，則輸出時間最靠前的一天。樣例輸入: 樣例輸出: 5 3 3 6 2 7 2 5 3 5 4 0 4 0 6 【上機練習】11.最大值和最小值的差【1.9編程基礎之順序查找05】 輸出一個整數序列中最大的數和最小的數的差。輸入: 第一行為M，表示整數個數，整數個數不會大于10000； 第二行為M個整數，以空格隔開，每個整數的絕對值不會大于10000。輸出: 輸出M個數中最大值和最小值的差。樣例輸入: 5 2 5 7 4 2樣例輸出: 5 【上機練習】12.不與最大數相同的數字之和【1.9編程基礎之順序查找07】 輸出一個整數數列中不與最大數相同的數字之

38、和。輸入: 輸入分為兩行： 第一行為N(N為接下來數的個數，N = 100)； 第二行N個整數，數與數之間以一個空格分開，每個整數的范圍是-1000,000到1000,000。輸出: 輸出為N個數中除去最大數其余數字之和。樣例輸入: 3 1 2 3樣例輸出: 3 【上機練習】13.白細胞計數【1.9編程基礎之順序查找08】 醫院采樣了某臨床病例治療期間的白細胞數量樣本n份，用于分析某種新抗生素對該病例的治療效果。為了降低分析誤差，要先從這n份樣本中去除一個數值最大的樣本和一個數值最小的樣本，然后將剩余n-2個有效樣本的平均值作為分析指標。同時，為了觀察該抗生素的療效是否穩定，還要給出該平均值的

39、誤差，即所有有效樣本（即不包括已扣除的兩個樣本）與該平均值之差的絕對值的最大值。 現在請你編寫程序，根據提供的n個樣本值，計算出該病例的平均白細胞數量和對應的誤差。輸入: 輸入的第一行是一個正整數n（2 n= 300），表明共有n個樣本。 以下共有n行，每行為一個浮點數，為對應的白細胞數量，其單位為109/L。數與數之間以一個空格分開。輸出: 輸出為兩個浮點數，中間以一個空格分開。分別為平均白細胞數量和對應的誤差，單位也是109/L。計算結果需保留到小數點后2位。樣例輸入: 樣例輸出: 5 11.00 1.00 12.0 13.0 11.0 9.0 10.0 【上機練習】14.直方圖【1.9編

40、程基礎之順序查找09】 給定一個非負整數數組，統計里面每一個數的出現次數。我們只統計到數組里最大的數。 假設 Fmax（Fmax10000）是數組里最大的數，那么我們只統計0,1,2.Fmax里每個數出現的次數。輸入: 第一行n是數組的大小。1 = n = 10000。 緊接著一行是數組的n個元素。輸出: 按順序輸出每個數的出現次數，一行一個數。如果沒有出現過，則輸出0。 對于例子中的數組，最大的數是3，因此我們只統計0,1,2,3的出現頻數。樣例輸入: 5 1 1 2 3 1樣例輸出: 0 3 1 1 【上機練習】15.最長平臺【1.9編程基礎之順序查找12】 已知一個已經從小到大排序的數組

41、，這個數組的一個平臺（Plateau）就是連續的一串值相同的元素，并且這一串元素不能再延伸。例如，在 1，2，2，3，3，3，4，5，5，6中1，2-2，3-3-3，4，5-5，6都是平臺。試編寫一個程序，接收一個數組，把這個數組最長的平臺找出 來。在上面的例子中3-3-3就是最長的平臺。輸入: 第一行有一個整數n，為數組元素的個數。第二行有n個整數，整數之間以一個空格分開。輸出: 輸出最長平臺的長度。樣例輸入: 10 1 2 2 3 3 3 4 5 5 6樣例輸出: 3 【上機練習】16.整數去重【1.9編程基礎之順序查找13】 給定含有n個整數的序列，要求對這個序列進行去重操作。所謂去重，

42、是指對這個序列中每個重復出現的數，只保留該數第一次出現的位置，刪除其余位置。輸入: 輸入包含兩行： 第一行包含一個正整數n（1 = n = 20000），表示第二行序列中數字的個數； 第二行包含n個整數，整數之間以一個空格分開。每個整數大于等于10、小于等于100。輸出: 輸出只有一行，按照輸入的順序輸出其中不重復的數字，整數之間用一個空格分開。樣例輸入: 5 10 12 93 12 75樣例輸出: 10 12 93 75【上機練習】17.鋪地毯【1.9編程基礎之順序查找14】Noip2011提高組第1題 為了準備一個獨特的頒獎典禮，組織者在會場的一片矩形區域（可看做是平面直角坐標系的第一象限

43、）鋪上一些矩形地毯。一共有n張地毯，編號從1到n。現在將這些地毯按照編號從小到大的順序平行于坐標軸先后鋪設，后鋪的地毯覆蓋在前面已經鋪好的地毯之上。地毯鋪設完成后，組織者想知道覆蓋地面某個點的最上面的那張地毯的編號。注意：在矩形地毯邊界和四個頂點上的點也算被地毯覆蓋。 輸入輸出樣例1說明：如下圖，1號地毯用實線表示，2號地毯用虛線表示，3號用雙實線表示，覆蓋點（2，2）的最上面一張地毯是3號地毯。 輸入輸出樣例2說明：如下圖，1號地毯用實線表示，2號地毯用虛線表示，3號用雙實線表示，覆蓋點（4，5）的最上面一張地毯是3號地毯。【上機練習】輸入: 第一行，一個整數n，表示總共有n張地毯。 接下來

44、的n行中，第i+1行表示編號i的地毯的信息，包含四個正整數a，b，g，k，每兩個整數之間用一個空格隔開，分別表示鋪設地毯的左下角的坐標（a，b）以及地毯在x軸和y軸方向的長度。 第n+2行包含兩個正整數x和y，表示所求的地面的點的坐標（x，y）。輸出: 輸出共1行，一個整數，表示所求的地毯的編號；若此處沒有被地毯覆蓋則輸出-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第二節 二維數組一、二維數組的定義當一維數組元素的類型也是一維數組時，便構成了“數組的

45、數組”，即二維數組。二維數組定義的一般格式：數據類型 數組名常量表達式1 常量表達式2 ；例如：int a410;a數組實質上是一個有4行、10列的表格，表格中可儲存40個元素。第1行第1列對應a數組的a00，第n行第m列對應數組元素an-1m-1。說明：當定義的數組下標有多個時，我們稱為多維數組，下標的個數并不局限在一個或二個，可以任意多個，如定義一個三維數組a和四維數組b：int a10035;int b10010035;多維的數組引用賦值等操作與二維數組類似。二、二維數組元素的引用二維數組的數組元素引用與一維數組元素引用類似，區別在于二維數組元素的引用必須給出兩個下標。引用的格式為： 下

46、標1下標2說明：顯然，每個下標表達式取值不應超出下標所指定的范圍，否則會導致致命的越界錯誤。例如,設有定義：int a35;則表示a是二維數組（相當于一個3*5的表格），共有3*5=15個元素，它們是：a00 a01 a02 a03 a04a10 a11 a12 a13 a14a20 a21 a22 a23 a24因此可以看成一個矩陣（表格），a23即表示第3行第4列的元素。三、二維數組的初始化二維數組的初始化和一維數組類似。可以將每一行分開來寫在各自的括號里，也可以把所有數據寫在一個括號里。例如：int direct42 = 1,0,0,1,-1,0,0,-1 int direct42 =

47、1,0,0,1,-1,0,0,-1 /盡量不要用四、二維數組程序設計例5.8 設有一程序#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(5)aji; coutendl; return 0;程序的輸入:2 1 33 3 11 2 1程序的輸出:2 3 11 3 23 1 1例5.9 已知一個

48、6*6的矩陣（方陣），把矩陣二條對角線上的元素值加上10，然后輸出這個新矩陣。【分析】 矩陣即表格，是一個二維數組，有6行6列共36個元素，每個矩陣都有二條對角線，本題難點在于對角線的元素怎么確定。#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; /尋找對角線的特征 f

49、or (int i=1; i=6; +i) /輸出6行6列的矩陣元素 for (int j=1; j=6; +j) coutsetw(5)aij; coutendl; return 0;例5.10 大部分元素是0的矩陣稱為稀疏矩陣，假設有k個非0元素，則可把稀疏矩陣用K*3的矩陣簡記之，其中第一列是行號，第二列是列號，第三列是該行、該列下的非元素的值。如：0 0 0 5 寫簡記成： 1 4 5 /第1行第4列有個數是50 2 0 0 2 2 2 /第2行第2列有個數是20 1 0 0 3 2 1 /第3行第2列有個數是1試編程讀入一稀疏矩陣，轉換成簡記形式，并輸出。【分析】 本題中需要解決的主

50、要問題是查找非零元素并記憶位置。將原始矩陣存于數組a。轉換后的矩陣存于數組b，當然b數組的行數可以控制在一個小范圍內。#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 (int j=1; j=m; +j) if (aij!=0) /找到非零值，存儲 +k; bk1=i; bk2=j; bk3=aij; for (int

51、i=1; i=k; +i) /輸出 for (int j=1; j=3; +j) coutsetw(3)bij; coutendl; return 0;運行結果：輸入： 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 6 4 1 圖5-1 圖5-2【問題分析】觀察圖5-1，大家不容易找到規律，但是如果將它轉化為圖5-2，不難發現楊輝三角形其實就是一個二維表的小三角形部分

52、，假設通過二維數組a存儲，每行首尾元素為1，且其中任意一個非首位元素aij的值其實就是ai-1j-1與ai-1j的和，另外每一行的元素個數剛好等于行數。有了數組元素的值，要打印楊輝三角形，只需要控制好輸出起始位置就行了。#include#includeusing namespace std;int main() int a1111; a11=1;/設定第一行的值 for (int i=2; i=10; +i)/從第二行開始推 ai1=1; aii=1;/設定每一行的首尾值為1 for (int j=2; j=i-1; +j)/當前行非首尾的數 aij=ai-1j-1+ai-1j; /每個數等于

53、上一行的二個數之和 for (int i=1; i=10; i+) if (i!=10) coutsetw(30-3*i) ;/控制每行的起始位置，即空格數量 for (int j=1; j=i; j+) coutsetw(6)aij; coutendl; return 0; 例5.12 輸入一串字符,字符個數不超過100,且以“.”結束。 判斷它們是否構成回文。【分析】所謂回文指從左到右和從右到左讀一串字符的值是一樣的，如12321,ABCBA,AA等。先讀入要判斷的一串字符（放入數組letter中），并記住這串字符的長度，然后首尾字符比較，并不斷向中間靠攏，就可以判斷出是否為回文。程序如下

54、：#includeusing namespace std;int main() char ch,letter101; int i=0,j=1; coutch; while (ch!=.)/讀入一個字符串以.號結束 +i; letteri=ch; cinch; while (j=i) coutYesendl; else coutNoendl; return 0;例5.13 蛇形填數 在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 上面的方陣中，多余的空格只是為了便于觀察規律，不必嚴格輸出，n=

55、8。【分析】： 類比數學中的矩陣，我們可以用一個所謂的二維數組來儲存題目中的方陣。只需聲明一個int aMAXNMAXN，就可以獲得一個大小為MAXNMAXN的方陣。在聲明時，兩維的大小不必相同，因此也可以聲明int a3050這樣的數組，第一維下標范圍是0,1,2,29，第二維下標范圍是0,1,2,49。 讓我們從1開始依次填寫。設“筆”的坐標為(x,y)，則一開始x=0，y=n-1，即第0行，第n-1列（別忘了行列的范圍是0到n-1，沒有第n列）。“筆”的移動軌跡是：下，下，下，左，左，左，上，上，上，右，右，下，下，左，上。總之，先是下，到不能填了為止，然后是左，接著是上，最后是右。“不

56、能填”是指再走就出界（例如45），或者再走就要走到以前填過的格子（例如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 & !axy-1) ax-y=+tot; while (x-1=0 & !ax-1y) a-xy=+tot; while (y+1n & !axy+1) ax+y=+to

57、t; for(x=0;xn;+x) for (y=0;yn;+y) printf(%3d,axy);printf(n); return 0;【說明】： 這段程序充分利用了C+語言簡潔的優勢。首先，賦值x=0和y=n-1后馬上要把它們作為a數組的下標，因此可以合并完成；tot和a0n-1都要賦值1，也可以合并完成。這樣，我們用一條語句完成了多件事情，而且并沒有犧牲程序的可讀性，這段代碼的含義顯而易見。 那4條while語句有些難懂，不過十分相似，因此只需介紹其中的第一條：不斷向下走，并且填數。我們的原則是：先判斷，再移動，而不是走一步以后發現越界了再退回來。這樣，我們需要進行“預判”，即是否越界

58、，以及如果繼續往下走會不會到達一個已經填過的格子。越界只需判斷x+1n，因為y值并沒有修改；下一個格子是(x+1,y)，因此只需ax+1y=0，簡寫成!ax+1y（其中!是“邏輯非”運算符）。 細心的讀者也許會發現這里的一個“潛在bug”；如果越界，x+1會等于n，ax+1y將訪問非法內存！幸運的是，這樣的擔心是不必要的。&是短路運算符。如果x+1n為假，將不會計算!ax+1y，也就不會越界了。 至于為什么是+tot而不是tot+，留給讀者思考。【上機練習】1.矩陣交換行【1.8編程基礎之多維數組01】 給定一個5*5的矩陣(數學上，一個rc的矩陣是一個由r行c列元素排列成的矩形陣列)，將第n

59、行和第m行交換，輸出交換后的結果。輸入: 輸入共6行，前5行為矩陣的每一行元素,元素與元素之間以一個空格分開。 第6行包含兩個整數m、n，以一個空格分開（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編程基礎之多維數組02】 輸入三個自然數N，i，j（1=i=n，1=j=n）

60、，輸出在一個N*N格的棋盤中(行列均從1開始編號)，與格子(i，j)同行、同列、同一對角線的所有格子的位置。如：n=4，i=2，j=3表示了棋盤中的第二行第三列的格子，如下圖：當n=4，i=2，j=3時，輸出的結果是：(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) 左下到右上對角線上的格子的位置【上機練習】輸入: 一行，三個自然數N，i，j，相鄰兩個數之間用單個空格隔開(1=N=10)。輸出: 第一