第七章 陣列

7.1 陣列

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

說明：

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

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

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

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

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

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

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

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

c067. Box of Bricks

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

說明：

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

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

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

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

說明：上一題的類題，就自已試一下吧！

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

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

費氏數列

排列(next_permutation)

二維陣列

int a[3][3];