回目錄

第七章 陣列

原 Google Sites 連結:/cppzero/di-qi-zhang-zhen-lie

目錄

b138. NOIP2005 1.陶陶摘苹果

題目大意:先給你 10 顆蘋果的高度,再給你陶陶伸手能及的高度,問陶陶踩在 30 公分高的凳子上可以採到幾顆蘋果?

說明:

這題的測資很討厭,如果他先給你陶陶能及的高度,再給你 10 個蘋果的高度的話,那麼我們只要一個很簡單的迴圈就可以完成了:

int a, h, c=0, i;
cin >> h;
for (i=1; i<=10; i++) {
    cin >> a;
    c += (a <= h + 30);
}
cout << c << endl;

但是它卻先給你蘋果的高度,你得先把蘋果的高度全部輸入完後才能讀到陶陶的高度。當然你也可以很暴力地宣告 11 個變數把所給的數字全部輸入然後再算出可以摘到幾顆蘋果,如下:

int a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, h, c;
cin >> a1 >> a2 >> a3 >> a4 >> a5 >> a6 >> a7 >> a8 >> a9 >> a10;
cin >> h;
h += 30;
c = (a1<=h) + (a2<=h) + (a3<=h) + (a4<=h) + (a5<=h) +
    (a6<=h) + (a7<=h) + (a8<=h) + (a9<=h) + (a10<=h);
cout << c << endl;

但是萬一題目是 100 個蘋果呢?甚至是 n 個蘋果呢?總得有個比較好的解決方式吧?

7.1 陣列

當我們用 int a; 宣告一個變數 a 時,這個變數同時只能儲存一個 32 位元的整數,當我們設定一個新的值給 a 時,原先在變數 a 內的值就會被覆蓋。但是如果我們的程式需要處理數以萬計的數字時,總不能定義幾萬個變數名稱來使用吧!為了這個目的,C++ 提供了「陣列」這個資料型態。

在 C++ 中,下列的程式碼代表我們宣告了一個可以儲存 10 個整數的陣列 a。

int a[10];

在這個陣列中,我們可以同時儲存 10 個整數,我們可以把 a 視為 10 個 int 的集合。為了方便存取這集合中的個別 int,C++ 將這 10 個整數依序編號為 0 到 9。當程式中要使用其中個別的 int 整數時,就必須要用「下標」運算子 [ ] 來指定它的編號。例如,我們要依序輸入 10 個蘋果的高度,我們可以這樣寫:

cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4] >> a[5] >> a[6] >> a[7] >> a[8] >> a[9];

也就是說,我們可以宣告一個 10 個 int 的陣列 a,然後用 a[0] 來代替原來的 a1、用 a[1] 代替原來的 a2、….。但是如果只是這樣替換而已反而會使程式碼變得更長,沒有任何好處。陣列的下標和字串的下標一樣,可以用變數來代入,如此一來,我們就可以用迴圈來簡化程式了。

int a[10], h, c=0, i;
for (i=0; i<10; i++)                        // 將蘋果高度輸入陣列
    cin >> a[i];
cin >> h;                                   // 輸入陶陶高度
for (i=0; i<10; i++)                        // 計算採得到幾顆蘋果
    c += (a[i] <= h + 30);                  // c(ount) -- 計數
cout << c << endl;

你可能會覺得這個版本並沒有比之前「暴力版」短多少,那麼看看下面這題,暴力法就完全行不通了。

c067. Box of Bricks

題目大意:給你 n 疊立方塊的高度 hi,問最少要移動幾塊立方塊才能讓每疊都一樣高。

說明:

這題要先求出每疊立方塊的平均高度,然後把所有超出平均高度的部份加總就是答案了。

在求平均高度前,要先輸入每一疊的高度並加總。求出平均高度之後,又得回頭去和每疊的高度作比較。因此,這也是典型的陣列應用 – 我們得先把所有的高度輸入、加總,並存入陣列之中。求出平均高度之後,再回頭和陣列中所儲存的每疊高度一一作比較並把超出的部份加總。

這其中有一個問題:測試資料中會有幾疊立方塊得等程式開始執行並輸入 n 之後才會知道,那麼我們解題時到底要開多大的陣列呢?開太大會浪費記憶體,開太小程式會爆掉。還好,像這一類的題目通常會明確指定 n 的範圍,我們程式中的陣列大小必須能處理範圍內所有的可能狀況。以本題來說,題目在輸入說明中明確地說明 1 ≤ n ≤ 50,因此我們的陣列至少必需可以儲存 50 個整數。

//591 - Box of Bricks (by Snail)
#include <iostream>
using namespace std;

int main () {
    int n, i, h[50], a, m, tc=1;                // 陣列 h 要有 50 個元素
    while (cin >> n, n) {
        a = 0;
        for (i=0; i<n; i++) {
            cin >> h[i];                        // 輸入高度
            a += h[i];                          // 並加總
        }
        a /= n;                                 // 求平均高度
        m = 0;                                  // m(oves) -- 移動個數
        for (i=0; i<n; i++)
            m += max (0, h[i] - a);             // 超出平均高度的個數
        cout << "Set #" << tc++ << endl;        // 依題意要求輸出
        cout << "The minimum number of moves is" << m << ".\n\n";
    }
}

b078. E. 白飯

題目大意:給你 n 個整數,問其中有幾個數小於平均值。

說明:上一題的類題,就自已試一下吧!

b026. H. PS3

題目大意:給定 n 個點的 x, y 座標,問哪兩點之間的距離最長。

說明:這題需要開兩個陣列,一個陣列用來存 x 座標,另一個陣列用來存 y 座標。

int x[3000], y[3000];

接下來輸入 n 個點的座標。

for (i=0; i<n; i++)
    cin >> x[i] >> y[i];

由於它只是要求出點的編號,所以只要算出兩點之間距離平方就可以比大小,並不需要去開根號。

d2 = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);

其中的 i 和 j 各需要一層的迴圈來處理。

b082. C. 國家寶藏

題目大意:給定 m 張骨牌,每張骨牌包含了這張骨牌的編號、所代表的字母、及下一張骨牌的編號,問所串連起來的骨牌所代表的文字。

說明:這題需要開兩個陣列,第一個陣列儲存每張骨牌所代表的字母,另一個陣列儲存下一張骨牌的編號。

b101. A. 收集凱蒂貓

b127. 會議中心(Room)

費氏數列

排列

d829. 146 - ID Codes

next_permutation

二維陣列

int a[3][3];
/*
 *      /----- a[0] -----\       /----- a[1] -----\       /----- a[2] -----\
 *    a[0][0] a[0][1] a[0][2]  a[1][0] a[1][1] a[1][2]  a[2][0] a[2][1] a[2][2]
 */
a[0] = { a[0][0], a[0][1], a[0][2] };
a[1] = { a[1][0], a[1][1], a[1][2] };
a[2] = { a[2][0], a[2][1], a[2][2] };