第六章  陣列

範例6-1a

假如有資料如下

1, 2, 3, 4, 5, 6, 7, 8

(1)    選用適當資料結構儲存以上資料，使得以下資料處理省時。

(2)    輸出以上資料。

(3)計算以上資料的總和。

(4)請將以上資料乘以2。

(5)輸出以上資料。

 

自我練習

1、程式設計的進階課程有一門是資料結構，資料結構裡最簡單的資料結構是單一變數，其次是串列、結構、堆疊、佇列、鏈串列、樹狀結構，請同學可使用一般變數重做此題，計算8個數字的總和，將每一個數字通通乘以2再輸出。

2、設有資料如下：

22, 33, 44, 55, 66

(1)  請選用適當資料結構儲存以上資料。

(2)  計算以上資料不及格的個數。

3、假設資料如下：

3,7,2,1,5

請寫一個程式，可以輸入一個數字，並判斷此數字是否在以上資料內。例如，輸入1，得到『是』，輸入『8』，得到『否』。（請問您的資料結構、演算法）

範例6-1b

請寫一程式讀入5位學生的國文成績，並可由使用者輸入座號來查詢成績。

 

自我練習

1. 簽到程式。假設班上共有 12 人，請寫一程式，可以由使用者進入教室時依序輸入座號來簽到，每輸入一個座號，電腦也輸出未到者的座號。（提示：可用串列的值表示到與未到，例如1表示到，0表示未到）

 

 

範例6-1c設有資料如下

77, 66, 99, 44, 55

請寫一個程式，可以計算平均、最高分及最低分。

 

自我練習

1、設有資料如下：

-1, 0, 3, 4, -5, 8

(1)統計正數、0、負數的個數。

(2)請問您的資料結構為何？

 

查表

 

範例6-1d請寫一程式，可將任意十進位數轉為 N 進位數。（2<=N<=16）

 

自我練習

1、假設有一個大富翁遊戲，共有10個位置，每個位置的獎罰如下表，遊戲一開始假設有10000元，請寫程式讓2個使用者輪流玩，每次擲一顆骰子，決定其行走距離與落腳位置，以其位置增減金額，且記錄每人剩餘金額。

0

1

2

3

4

5

6

7

8

9

中發票得200元

闖紅燈罰200元

中樂透得10000元

任意停車，罰1000元

繳汽車稅2000元

繳房屋稅3000元

停玩一次

得到股息1000元

抽獎得到3000元

繳停車費30元

 

範例 6_1e假設2月永遠是28天，請寫一程式，可以輸入一個日期，且轉為今年第幾天。例如，輸入2,1代表2月1日，那就是第32天，輸出32。

範例6_1f 同上題，假設1月1日是星期二，那所輸入月份的第1天是星期幾？

 

自我練習

1、同上範例，但可輸入一個日期，且得到當天是星期幾。

 

範例6_1g 同上題，假設1月1日是星期二，那輸出指定月份的月曆。

2、同上題，但考慮閏年，例如，輸入2000/3/1則輸出61。

3、同上題，可以輸入兩個日期，計算其相差的天數。例如，輸入

2018 9 30

2018 10 1

則輸出1 。（此為國內高中生程式解題系統(https://zerojudge.tw/)基礎題。

提示：這題要先界定年份的最小值當成一個參考起點，本例就設為2018 1 1 ，然後大家都先求到起點的日期，再相減就可以。

 

4、同上題，但可比較兩個日期的先後。例如，應該還書日期是2018 9 30，但是2018 10 1來還，表示逾期。

提示：

這題要先界定年份的最小值當成一個參考起點，本例就設為2018 1 1 ，然後大家都先求到起點的日期，再比較大小就可以。

5、假設不考慮閏年，可寫一程式先指派1月1日是星期幾，然後輸出每個月1日是星期幾。

 

範例6_1h可以輸入天數，但轉為日期輸出，例如輸入32，能得到2月1日。（本例先簡化題目，假設2月通通28天）

自我練習

1、同上範例，但考慮閏年。

2. 請寫程式完成以下條件。

(1) 可以擲20 次骰子。

 (2) 計算並輸出共有多少個3。

 

2. 請寫程式完成以下條件。

(1) 可以擲20 次骰子。

 (2) 統計所有數字出現次數。

 

4. 請寫程式完成以下條件。

(1) 產生50 個1 到100 的亂數。

(2) 以串列儲存以上資料。

(3) 輸出以上資料。

(4) 統計與輸出0~9,10~19,20~29,30~39,40~49,50~59,60~69,70~79,80~89,90~100 等區間的人數。

5.假設有兩筆資料如下：

        3,4,7,9,12

        1,5,6,8,15,

請幫忙合併。（請問您的資料結構、您的演算法）

6.假設有兩筆資料如下：（每筆資料都已經是由小而大排列）

        3,4,7,9,12

        1,5,6,8,15,

請幫忙合併，且合併後還是由小而大。（請問您的資料結構、您的演算法）

 

※7. 假如有兩筆資料如下

3,1,4,5,6,7

5,1,7,4,3

(1) 請以兩個串列儲存。

(2) 請比較與分析有哪些資料重複。

(3) 將重複的資料放到第三個串列。（交集）

（4）將兩筆資料合併，放到第四個串列，但資料不可重複。（聯集）

※8. 假如有兩筆資料如下

3,1,4,5,6,7

5,1,7,4,3

(1) 請以兩個串列儲存。

 (2) 將以上資料遞除重複資料再合併，且放到第三個串列。

 

※9. 假如有資料如下

3,1,4,5,6,7,1,1,3

請將重複的資料去掉。

※10假設有兩筆資料如下

          3,1,4,7,6,3,5,6,8,9,2,1,1,3,4,7

          ,7,6,3

請問第二筆資料是否為第一筆資料的連續子字串？(本例是，7,2,3,5就不是)

※11找出以下資料的週長，例如，第一筆測資是3，第二筆測資是4。本例假設資料長度1000以下，週長10以下。

          6,1,2,6,1,2,6(週長是3)

          3,1,4,7,3,1,4,7,3,1(週長是4)

         

 

範例6-1i

假設有兩個矩陣如下:

 


     1    2    3               1    2    0

     4    5    6               2    1    3

 
（1）、請求其相加的結果如下：
               2             4             3
               6             6             9
（2）計算矩陣一所有元素和。
（3）請問要使用何種資料結構較省事。
 

自我練習

1. 假設有矩陣如下：
                               1             2             0
                               0             5             6
                               7             8             9
                               10           11           0
 
（1）    請檢查幾個0。
（2）    再將每一元素乘以2後輸出。
（3）    請問以何種資料結構才會省事。

 

 

範例6-1j

假設有學生成績如下：

 

座號

國文

英文

數學

平均

不及格科數

1

50

60

70

 

 

2

30

40

50

 

 

3

70

80

90

 

 

4

66

77

88

 

 

5

22

33

44

 

 

平均

 

 

 

 

 

 

1.     請選用適當資料結構儲存以上資料。

2.     計算每人平均。

3.     統計每人不及格科數。

4.     統計各科平均。

自我練習

1.     假設某一公司有三個業務員，其每季的業績如下：

 

編號

第一季

第二季

第三季

第四季

和

零的個數

1

0

2

4

6

 

 

2

8

0

2

1

 

 

3

7

0

0

9

 

 

和

 

 

 

 

 

 

零的個數

 

 

 

 

 

 

(1)計算每一個人的業績總和及零的個數。

(2)計算每一季的業績總和及零的個數。

(3)請問資料結構為何？

 

範例 6_1k以下是某一汽車進場與離場時間a1='03:20'，a2='04:10'請問其停車時間。

自我練習

1、假設日期格式為'2000/3/1 '則輸出其為2000年的第61天。

2、同上題，可以輸入兩個日期，計算其相差的天數。例如，輸入

a= '2018/9/30 '

b= '2018/10/1 '

則輸出1 。

3、同上題，但可比較兩個日期的先後。例如，還書日期是2018 9 30，但是2018 10 1來還，表示逾期。

4、請寫一程式，處理停車的時間計算。例如，

        a1= '2018/3/2 08:20 '

        a2= '2018/3/3 16:10 '

範例6_1l編碼（APCS106/10試題）

1、輸入。

第一列為取碼長度l(len)。例如，

1

第二列輸入若干數字，以0結束。例如，

252 373 28 0

2、處理

將第二列數字從左邊取長度l的數字，取極大值輸出。

將第二列數字從右邊取長度l的數字，取極小值輸出。

 

3、範例

資料編號

輸入

輸出

1

1     (取碼長度)

252 373 28 0

2 3 2 max=3

2 3 8 min=2

3 2

2

2      (取碼長度)

258 0

25 max=25

58 min=58

25 58

3

2     (取碼長度)

123 58 612 0

12 58 61 max=61

23 58 12 min=12

61 12

 

自我練習

1、 請設計一個程式，可以執行中英文名詞的翻譯。例如，輸入『book』得到『書』，輸入『書』，得到『book』。

2、 請設計一個程式，可輸入一個車牌號碼，得到客戶資料。

 

範例6_3a密碼解碼（APCS107試題）

1、定義密碼如下：

0101

0111

0010

1101

1000

1100

A

B

C

D

E

F

2、輸入、輸出如下：

輸入

1

0101

2

0010

1101

4

1000

1100

0101

0111

備註

輸入的值只有以上6種

輸出

A

CD

EFAB

 

 

範例6_3b 停車場計費。請寫一個程式，可以寫一個程式，以輸入車牌號碼管理與計算其停留時間，當此車牌第一次輸入時，記住其入場時間，第二次輸入時，輸出其入場時間、出場時間與停留時間。

自我練習

1、 請寫一個門禁管理程式，只有輸入指定的帳號，才可進入，且記錄每位進入與離開時間。本例假設帳號只有aa,bb,cc,dd四個人。

 

 

 

範例6_4a孤獨字串（APCS107/10月考題）

當一個字串，使用字母(A ~ Z)的個數最少,則他就是一個孤獨字串。例如，

        “HELLO”

字串長度5，但是使用四個字母組成，但是

        “ABBBAA”

字串長度6，僅使用2個字母組成，那就比上一個字串『HELLO』孤獨，本例請於所輸入字串中，找出最孤獨字串，也就是含字母種類最少者。其次，若孤獨字串有兩個以上，請繼續將這些孤獨字串按照字母順序排列，找出排在最前面的字串。例如，『ABBBAA』與『AAAABB』均謹含兩個字母，那還要繼續比較，找出字母順序最前面的字串，所以是『AAAABB』，以下是參考的測資：

        5

        HELLO

        ABBBAA

        AAAABB

        GOODBYE

        ABCDEFGHIJKL

表示5個測資，則輸出

        AAAABB

 

範例6_4b卡通部隊(APCS 108/06月試題)

給定卡通部隊成員個數與隊伍組數。例如，以下代表有10個成員，5個隊伍，10個成員分別是ABCDEFGHIJ

10 5

AJBA

HCEFGGC

BIJDAIJ

EFCDHGI

HCEFGA

JAJB

若任兩組沒有相同成員，且含全部成員，那稱此兩對互補，請找出以上有幾組互補成員。但是AKB,KAKB,BAK視為相同隊伍。例如，本例1,4互補，2,3也互補，所以答案是2組。

 

 

範例6_4c完美彩帶。(APCS 108/06試題)

給定顏色個數m與彩帶長度n，例如，

4 10 #4代表有4種不同顏色，10代表有10種測資

1 7 6 4 4 6 1 7 4 7

又例如，

3 7

1 2 2 0 1 2 1

若有連續m個元素同時包含m個顏色，則稱此段為完美彩帶。例如第1筆測資的1 7 6 4、4 6 1 7 與6 1 7 4都是連續4個元素，且這4個元素就包含四種顏色，所以通通是完美彩帶，所以答案是3。第2筆測資的2 0 1與0 1 2 也是完美彩帶，所以答案是2。

 

 

6-5排序

 

範例6-5a

示範氣泡排序法。

 

自我練習

１．同上範例，但每階次均尋找一個最大值，且逐次與第n,n-1,n-2筆資料交換即可。

範例6_5b假設有資料如下：

座號

姓名

國文

數學

缺課時數

總分

1

aa

8

10

1

18

2

bb

9

9

2

18

3

cc

7

10

0

17

4

dd

10

9

1

19

5

ee

9

8

2

17

(1)請以適當資料結構儲存。

(2)以總分為依據，從小而大輸出。

自我練習

1、同範例，但總分相同時，請以數學為排序依據。

提示：將（總分＊10+數學）當作排序依據就可以。

2、同上自我練習，當數學再同分，那再以國文為排序依據。

3、同上自我練習，當國文再同分，那再以缺課時數少者為排序依據。

 

計數排序法

 

範例6-5c示範計數排序法。

 

 

範例6_5d假設有資料如下：

座號

姓名

國文

數學

缺課時數

總分

1

aa

8

10

1

18

2

bb

9

9

2

18

3

cc

7

10

0

17

4

dd

10

9

1

19

5

ee

9

8

2

17

(1)請以適當資料結構儲存。

(2)以總分為依據，計算其名次，輸出以座號小者先輸出。

 

補充說明

1、以上程式沒有考慮同分的處理，請自行思考如何處理同分同名次，也就是18分應該並列第2，然後要跳掉第3名，17分要第4名。

2、同上範例，總分相同時，請以數學為排序依據。

 

自我練習

1、同範例，但是總分相同時，以數學為排序依據。

2、前面已經介紹二維串列可以指定欄位排序，本例請先依名次排序、然後請自己填入名次，再依座號排序。

 

6_6搜尋

 

範例6-6a

假設有員工電話如下，請以適當資料結構儲存，並能輸入姓名而查得電話號碼。

 

編號

姓名

電話號碼

1

aa

1111168

2

hh

2222168

3

cc

3333168

4

gg

4444168

5

ff

5555168

6

ii

6666168

7

ee

7777168

8

bb

8888168

9

jj

9999168

10

dd

1688168

11

kk

2688268

12

ll

3688368

 

自我練習

1、同上題，但可重複查詢。

2、假如有帳號密碼如下表，只有輸入這些帳號與密碼才能使用範例4_3a的面積計算，請寫程式完成此功能。

編號

帳號

密碼

1

aa

1111168

2

hh

2222168

3

cc

3333168

4

gg

4444168

5

ff

5555168

6

ii

6666168

7

ee

7777168

8

bb

8888168

9

jj

9999168

10

dd

1688168

11

kk

2688268

12

ll

3688368

 

二分搜尋法

6-6b

同上範例，但使用二分搜尋法。

 

6-7實例探討

眾數

於大數據分析中，眾數就是出現頻率最高的數字，數字既然多，為了能簡化程式的撰寫，通常將這些數字以串列儲存，然後以迴圈配合索引存取這些數字，請看以下範例。

範例6_7a設有數據如下：（高中數據分析）

5,7,8,4,5,6,2,5,9,1

請寫程式求其眾數。

自我練習

 

2、全距與中位數。全距與中位數都要先排序，全距就是最大值減去最小值。中位數還要先判斷是奇數個數還是偶數個數，奇數個數就是中間那一個數字，偶數個數則取中間那兩位數字的平均。例如，設有資料分別如下：

6,1,12,2,9,8,19,

6,1,12,2,9,8,19,12

請寫程式可以求其全距與中位數。

 

範例6_7b T分數。假設T分數的轉換公式如下：　　　　　　　　　  

(1)   求全班平均 。（Ai為每人成績，n為全班人數）

    (2)   求全班標準差    （d為平均）                                                     

(3)   求每人Z分數   (Zi為每人的Z分數）

(4)   求每人T分數Ti=500+100´Zi 。（Ti為每人的T分數）

請產生40個1至100的亂數，請問資料結構為何？其平均分數為何？請依以上演算法將每人成績轉為T分數，輸出每人T分數，並觀察名次20的人平均為何？又T分數與名次的關係為何？

 

範例6_7c加法。大整數加法。若有兩個1百位數的數字，要執行精密加法，那要如何完成。

自我練習

1、同範例，請練習減法。

2、 

 

※範例6_7d 開根號運算。開根號運算原理如下：

        (10a+b)2=100a2+20ab+b2=100 a2+b(20a+b)

請寫程式完成以下開根號運算。

 

自我練習

※

將300＊4＋30＊2＊5… 減下來，放到下面一列）

 

範例6_7e1 產生7個不重複1∼42亂數。

 

自我練習

1、請寫一個程式，可以指派參加抽獎的人數與獎品數量，然後就可以得到得獎的編號。例如，本次收到42個來信，要抽出5位得獎編號。

2、假設有10個人要摸彩，獎品4個如下：

電視、電腦、筆電、手機

請寫一個程式，可以讓每個人都享受摸一次獎的樂趣。

 

範例6_7f  英文打字練習.請寫一個程式，可以出現10題英文單字，讓使用者可鍵入單字，並評判正確與錯誤題數、使用時間。

自我練習

1、請將自己課本單字輸入本題。

2、那如何測驗整句英文。

3、如何測驗中文打字。

 

範例6_7g 如何寫填充題程式。英文單字需要不斷練習才會進步，本單元將寫一個單字記憶程式，他會不斷出現中文，您可輸入英文，電腦會評判是否正確，並統計正確與錯誤題數。

自我練習

1、請將自己的學科，寫成填充題。

範例6_5g 選擇題測驗。請寫一程式，可以讓使用者使用選擇題測驗。

 

自我練習

1、請將自己的學科，以選擇題完成10題測驗題，然後全班收集起來，再分享大家一起使用。

 

※迴歸直線（高中數據分析）

使用最小平方法求迴歸直線的演算法如下：

1、設有n筆數據(x1,y1),(x2,y2),…(xn,yn)，x座標平均ux，y座標平均uy，其相關係數為

 

2、求m

3、則此迴歸直線方程式如下：

 

 

※範例6_5h 某班級共10人，其加強上課日數與期末考數學成績如下表。

座號

1

2

3

4

5

6

7

8

9

10

加強日數

6

6

12

4

7

9

8

11

6

11

數學成績

4

8

13

6

7

13

9

11

6

13

（1）、求其相關係數。

（2）、求回歸直線斜率。

（3）、求回歸直線方程式。

※範例6_7i示範矩陣相乘。

再談兩人猜拳

前面的兩個人猜拳問題，我們使用if~elif~else 解決3x3 共九種狀態。若使用二維串列，則可定義一個二維串列如下`

範例6_7j示範以上猜拳程式。

自我練習

1、同上範例，可以讓人和電腦連續猜拳，直到有一方贏3次。

2、同上題，那三個人一起猜拳呢，如何用串列表示。

3、假設高鐵票價如下：

 

新竹

台中

台南

高雄

台北

300

700

1000

1500

新竹

 

200

500

1000

台中

 

 

300

800

台南

 

 

 

300

請寫一程式，可以查詢票價。

4、以上題目，是否可以使用dict，那程式要如何寫？

 

 

 

 

習題

 

1、設某班有5人，每人有3科成績，其所佔學分分別為6、4及3，如下表所示：

座號

姓名

國文

英文

數學

平均

名次

1

aa

30

40

50

 

 

2

bb

40

50

60

 

 

3

cc

55

66

77

 

 

4

dd

10

20

30

 

 

5

ee

77

88

99

 

 

請問您的資料結構為何？，並計算其學分平均，輸出按照學分平均由高而低排列。

 

2.同上題，但排名次，且按照座號輸出。

 

3.樂透開獎。假設樂透號碼是1到42號球，假設本期樂透開獎號碼是2,3,8,14,22,39，特別號是29，使用者可輸入6個號碼，電腦回應中獎情形。請選擇適當資料結構儲存以上資料，且寫一程式，可以協助使用者對獎。

4.樂透對獎。假設以下是張三已經購買的樂透彩券號碼。

(1)請以適當資料結構儲存。

(2)請寫一程式，可以輸入樂透中獎號碼(本例假設中獎號碼是22,12,13,14,15,16)，並核對中獎情形。。

 

5.同上題，但是電腦開獎。

※6. 請寫一程式，滿足以下條件。

(1) 某次考試共10 題，假設正確答案如下：

1,4,2,4,2,3,3,3,1,1

(2) 某班共5 人，某次考試共10 題，每人答案如下，請核對其成績。

(3) 請統計每人分數。

(4) 統計以下區間的人數。

(5) 統計每一題、每一選項的人數。

(6) 統計每一題、答對人數的比率。

 

※7、我們回想國中老師如何找小於50 的質數時，其方法是將2∼50 的自然數寫在黑板上，如下表，然後其演算步驟如下，即可找出小於50 的質數。

(1) 將2 加括號， 並把2 的倍數全部打×， 故將4，6，8，10，12， ⋯，50，全部打×。

(2) 從2 往大數找，將第1 個沒被打× 者加括號，所以3 被加括號，並將3 的3 倍，4 倍，5 倍⋯全部打×。

(3) 從3 往大數找，將第一個沒被打× 者加括號，所以5 被加括號，並將5 的5 倍，6 倍⋯打×。

（4）依此類推，直至推演至大於 50 的整數為止，還沒被打× 者皆為質數。

※8. 請寫一程式，可以重複產生與輸出0 到99 的亂數，直到有數字重複時，輸出此亂數與其重複的序號 ( 例如，3，8，4，9，52，4，則表示於第6個亂數時，已有亂數重複) 。 重複以上實驗100 次，並統計其平均值。

 

※9、複選題評分。大學學測考試的複選題共五個選項，五個選項全答對得5 分，錯一個選項得3 分，錯兩個選項得1 分，錯超過兩個選項得0 分，未做答也是0 分， 且答錯不倒扣，請寫一程式，可以協助評分。（假設5題，以下是5個人的劃卡答案）    

座號

1

2

3

4

5

解答

10010

11100

01100

00011

00001

1

10010

11100

01100

00011

00001

2

 

11111

01111

00011

00101

3

10011

11000

01100

00011

00001

4

10011

11100

01100

00011

00001

5

10010

11100

01100

00011

00011

※10、高速公路計費系統。

照相點

車牌號碼

備註

1

1011,2000,4000

 

2

1011,2000,3000,4000,8000

 

3

2000,3000,4000,6000,8000,9000

 

4

3000,4000,5000,6000,7000,9000

 

5

4000,5000,7000,9000,1100

 

請寫一程式統計每台車行走的距離。本例假設每個照相點都等距，且距離都是5公里。

 

※11、鐵路時刻表查詢。

請實際操作高鐵的火車時刻表查詢，假如某一鐵路只有5站,時刻表如下，請問資料如何儲存，請問您如何設計一個程式，讓使用者可以方便查詢所要搭乘的車種。

車次編號

台北

新竹

台中

台南

高雄

備註

1

07:00

07:30

 

08:00

0840

09:20

 

2

07:30

 

07:50

 

08:40

 

3

08:00

 

09:00

09:40

10:20

 

4

08:10

 

 

 

10:20

 

5

09:00

09:30

10:00

10:40

11:40

 

6

09:30

 

 

10:30

11:20

 

7

10:00

 

11:00

 

12:00

 

8

10:30

11:00

11:30

12:00

12:40

 

9

11:00

 

 

 

13:30

 

10

11:30

12:00

12:30

 

13:30

 

※12、假設路旁的樹木每10公尺種一棵，假設以1表示活著，0表示死掉，目前樹木存活狀態如下：

        001110010011011100  （1代表存活，0代表死掉）

請問您的資料結構為何？請問還有幾棵樹存活？（本例9顆）若連續兩棵樹存活定義有樹蔭10公尺，請問共有樹蔭幾公尺（本例為50公尺）。