-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathch07.html
12 lines (12 loc) · 8.47 KB
/
ch07.html
1
2
3
4
5
6
7
8
9
10
11
12
<!DOCTYPE html><html></html><head><meta charset="UTF-8"><meta content="text/html; charset=UTF-8" http-equiv="content-type"><link href="style.css" rel="stylesheet" type="text/css"><link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css"><script src="jquery/dist/jquery.min.js"></script><script type="text/javascript" src="./selectchapter.js"></script><script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js"></script><title>第七章 陣列</title></head><body><nav class="navbar navbar-default" role="navigation"><div class="container-fluid"><div class="navbar-header"><a class="navbar-brand" href="index.html">板中資訊社</a></div><div><ul class="nav navbar-nav"><li class="active"><a href="#">C++</a></li><li class="dropdown"><a class="dropdown-toggle" href="#" data-toggle="dropdown">課程<b class="caret"></b></a><ul class="dropdown-menu"><li><a href="ch01.html">第一章 立刻動手</a></li><li><a href="ch02.html">第二章 變數與指定運算子「=」</a></li><li><a href="ch03.html">第三章 比較運算子與 if 陳述式</a></li><li><a href="ch04.html">第四章 迴圈</a></li><li><a href="ch05.html">第五章 基礎資料型別</a></li><li><a href="ch06.html">第六章 字元與字串</a></li><li><a href="ch07.html">第七章 陣列</a></li><li><a href="ch08.html">第八章 自定義函數與資料型別</a></li><li><a href="ch09.html">第九章 排序</a></li></ul></li><li class="dropdown"><a class="dropdown-toggle" href="#" data-toggle="dropdown">附錄<b class="caret"></b></a><ul class="dropdown-menu"><li><a href="basic_type.html">A 基礎資料型別</a></li></ul></li></ul></div></div></nav><h1>第七章 陣列</h1><button id="button1">陣列</button><button id="button2">二維陣列</button><div class="para" id="para1" style="display:none;"><h2>7.1 陣列</h2><li><a href="https://zerojudge.tw/ShowProblem?problemid=b138">b138. NOIP2005 1.陶陶摘苹果</a></li><p>題目大意：先給你 10 顆蘋果的高度，再給你陶陶伸手能及的高度，問陶陶踩在 30 公分高的凳子上可以採到幾顆蘋果？</p><p>說明：</p><p>這題的測資很討厭，如果他先給你陶陶能及的高度，再給你 10 個蘋果的高度的話，那麼我們只要一個很簡單的迴圈就可以完成了：</p><script src="https://gist.github.com/allem40306/a64ebcc859bd6557a01bb8557bb469f4.js?file=ch07-01.cpp"></script><p>但是它卻先給你蘋果的高度，你得先把蘋果的高度全部輸入完後才能讀到陶陶的高度。當然你也可以很暴力地宣告 11
個變數把所給的數字全部輸入然後再算出可以摘到幾顆蘋果，如下：</p><script src="https://gist.github.com/allem40306/a64ebcc859bd6557a01bb8557bb469f4.js?file=ch07-02.cpp"></script><p>但是萬一題目是 100 個蘋果呢？甚至是 n 個蘋果呢？總得有個比較好的解決方式吧？</p><p>當我們用 int a; 宣告一個變數 a 時，這個變數同時只能儲存一個 32 位元的整數，當我們設定一個新的值給 a 時，原先在變數 a
內的值就會被覆蓋。但是如果我們的程式需要處理數以萬計的數字時，總不能定義幾萬個變數名稱來使用吧！為了這個目的，C++
提供了「陣列」這個資料型態。</p><p>在 C++ 中，下列的程式碼代表我們宣告了一個可以儲存 10 個整數的陣列 a。</p><script src="https://gist.github.com/allem40306/a64ebcc859bd6557a01bb8557bb469f4.js?file=ch07-03.cpp"></script><p>在這個陣列中，我們可以同時儲存 10 個整數，我們可以把 a 視為 10 個 int 的集合。為了方便存取這集合中的個別 int，C++ 將這
10 個整數依序編號為 0 到 9。當程式中要使用其中個別的 int 整數時，就必須要用「下標」運算子 [ ]
來指定它的編號。例如，我們要依序輸入 10 個蘋果的高度，我們可以這樣寫：</p><script src="https://gist.github.com/allem40306/a64ebcc859bd6557a01bb8557bb469f4.js?file=ch07-04.cpp"></script><p>也就是說，我們可以宣告一個 10 個 int 的陣列 a，然後用 a[0] 來代替原來的 a1、用 a[1] 代替原來的
a2、....。但是如果只是這樣替換而已反而會使程式碼變得更長，沒有任何好處。陣列的下標和字串的下標一樣，可以用變數來代入，如此一來，我們就可以
用迴圈來簡化程式了。</p><script src="https://gist.github.com/allem40306/a64ebcc859bd6557a01bb8557bb469f4.js?file=ch07-05.cpp"></script><p>你可能會覺得這個版本並沒有比之前「暴力版」短多少，那麼看看下面這題，暴力法就完全行不通了。</p><p>c067. Box of Bricks</p><p>題目大意：給你 n 疊立方塊的高度 hi，問最少要移動幾塊立方塊才能讓每疊都一樣高。</p><p>說明：</p><p>這題要先求出每疊立方塊的平均高度，然後把所有超出平均高度的部份加總就是答案了。</p><p>在求平均高度前，要先輸入每一疊的高度並加總。求出平均高度之後，又得回頭去和每疊的高度作比較。因此，這也是典型的陣列應用--我們得先把所有的高度輸
入、加總，並存入陣列之中。求出平均高度之後，再回頭和陣列中所儲存的每疊高度一一作比較並把超出的部份加總。</p><p>這其中有一個問題：測試資料中會有幾疊立方塊得等程式開始執行並輸入 n
之後才會知道，那麼我們解題時到底要開多大的陣列呢？開太大會浪費記憶體，開太小程式會爆掉。還好，像這一類的題目通常會明確指定 n
的範圍，我們程式中的陣列大小必須能處理範圍內所有的可能狀況。以本題來說，題目在輸入說明中明確地說明 1 ≤ n ≤
50，因此我們的陣列至少必需可以儲存 50 個整數。</p><script src="https://gist.github.com/allem40306/a64ebcc859bd6557a01bb8557bb469f4.js?file=ch07-06.cpp"></script><li><a href="http://contest.cc.ntu.edu.tw/npsc2007/2007jun.doc">2007 NPSC 國中組初賽 E. 白飯</a></li><p>題目大意：給你 n 個整數，問其中有幾個數小於平均值。</p><p>說明：上一題的類題，就自已試一下吧！</p><li><a href="http://contest.cc.ntu.edu.tw/npsc2006/2006senfinal.doc">2008 NPSC 高中組決賽H. PS3</a><p>題目大意：給定 n 個點的 x, y 座標，問哪兩點之間的距離最長。</p><p>說明：這題需要開兩個陣列，一個陣列用來存 x 座標，另一個陣列用來存 y 座標。</p><script src="https://gist.github.com/allem40306/a64ebcc859bd6557a01bb8557bb469f4.js?file=ch07-07.cpp"></script><p>接下來輸入 n 個點的座標。</p><script src="https://gist.github.com/allem40306/a64ebcc859bd6557a01bb8557bb469f4.js?file=ch07-08.cpp"></script><p>由於它只是要求出點的編號，所以只要算出兩點之間距離平方就可以比大小，並不需要去開根號。</p><script src="https://gist.github.com/allem40306/a64ebcc859bd6557a01bb8557bb469f4.js?file=ch07-09.cpp"></script><p>其中的 i 和 j 各需要一層的迴圈來處理。</p></li><li><a href="http://contest.cc.ntu.edu.tw/npsc2007/doc/2007junfinal.doc">b082. C. 國家寶藏</a></li><p>題目大意：給定 m 張骨牌，每張骨牌包含了這張骨牌的編號、所代表的字母、及下一張骨牌的編號，問所串連起來的骨牌所代表的文字。</p><p>說明：這題需要開兩個陣列，第一個陣列 (儲存每張骨牌所代表的字母，另一個陣列儲存下一張骨牌的編號。</p><li><a href="http://contest.cc.ntu.edu.tw/npsc2005/problem/2005jFinal.doc">2005 NPSC 國中組決賽 A. 收集凱蒂貓</a></li><h3>費氏數列</h3><li><a href="https://zerojudge.tw/ShowProblem?problemid=b127">b127. 會議中心（Room）</a></li><h3>排列(next_permutation)</h3><li><a href="https://zerojudge.tw/ShowProblem?problemid=d829">d829. 146 - ID Codes</a></li></div><div class="para" id="para2" style="display:none;"><h2>二維陣列</h2><p>int a[3][3];</p><table><tr><td align="center">a[0]<br><table><tr><td>a[0][0]</td><td>a[0][1]</td><td>a[0][2]</td></tr></table></td> <td align="center">a[1]<br><table><tr><td>a[1][0]</td><td>a[1][1]</td><td>a[1][2]</td></tr></table></td> <td align="center">a[2]<br><table><tr><td>a[2][0]</td><td>a[2][1]</td><td>a[2][2]</td></tr></table></td></tr></table><br><br><table><tr><td></td><th>0</th><th>1</th><th>2</th></tr> <tr><th>0</th><td>a[0][0]</td><td>a[0][1]</td><td>a[0][2]</td></tr> <tr><th>1</th><td>a[1][0]</td><td>a[1][1]</td><td>a[1][2]</td></tr> <tr><th>2</th><td>a[2][0]</td><td>a[2][1]</td><td>a[2][2]</td></tr></table> <br><br><br><p></p></div></body>