暴力(Brute Force)--使用迴圈

暴力(Brute Force)--使用迴圈

暴力(Brute Force)就是在解題過程中列舉所有可能性，是一種很直觀的解題方法，通常程式效率不會太好，若題目輸入資料不大，有可能在題目所規定的時間內，執行完畢獲得答案，解題後可以再想想如何讓程式執行效率更好，有沒有其他解法。

本章使用迴圈進行列舉，下一個章使用遞迴進行列舉，遞迴也是一種暴力演算法，暴力演算法強調列舉所有可能性，在找出符合要求的答案。

(1)統計字母數量

給定一行英文句子，忽略標點符號與特殊符號，只考慮英文字母並將大寫英文字母一律轉成小寫字母，照英文字母順序輸出英文字母與個數。

輸入說明

第一行輸入數字n，表示後面的輸入有幾行，每次輸入一行英文句子，中間可能有空白鍵，一行結束後進行換行，以換行進行區分多個輸入，可能有多行輸入。

輸出說明

針對每一行輸入，依照英文字母順序輸出英文字母與個數。

輸入範例

1

An apple a day keeps the doctor away.

輸出範例

a 6

c 1

d 2

e 4

h 1

k 1

l 1

n 1

o 2

p 3

r 1

s 1

t 2

w 1

y 2

解題想法

本範例就是使用暴力，取出每一個字母判斷是否是英文字母，並一律轉成小寫字母，計算每個英文字母出現的個數，最後依照英文字母順序輸出英文字母與個數。

(2)找出直角三角形

請求出三邊長相加大於等於整數L與小於等於整數R的所有直角三角形，三角形的邊長都是整數，請以邊長遞增方式輸出，邊長越小越優先輸出。

輸入說明

輸入整數L與R，表示三邊長和的上限與下限，保證輸入範圍內一定有直角三角形，允許輸入多組測資。

輸出說明

輸出所有符合的直角三角形邊長。

輸入範例

30 100

輸出範例

5 12 13

7 24 25

8 15 17

9 12 15

10 24 26

12 16 20

15 20 25

解題想法

列舉三角形三邊長的各種可能性，判斷邊長和是否大於等於整數L與小於等於整數R，且可以組成直角三角形就顯示出來。

(3)找出假的硬幣 

n個硬幣中有1個偽幣，目前有一個天平可以測量左右兩邊的硬幣是否重量相同，或者不相同，題目會提供m個天平量測結果，每個量測結果會提供左右兩邊硬幣編號與量測結果，請找出偽幣的編號，每組測資都保證能找到答案。

輸入說明

輸入整數n與m，n表示硬幣個數，編號由1到n，接著輸入m列天平測量結果，測量結果的第一個數字p，表示左右共有幾個硬幣被測量，數字p為正數且是偶數，後面接著p個數字，每個數字表示一個硬幣編號，先顯示左邊p/2個，再顯示右邊p/2個，最後接著一個數字0或1，0表示左右相等，1表示左右不相等，允許多組測資輸入。n小於50，m小於10，p小於等於n。

輸出說明

輸出偽幣的編號。

輸入範例

7 2

2 1 3 0

4 2 4 6 7 0

輸出範例

5

解題想法

因為n個硬幣只有一個是偽幣，若天秤左右兩邊相等，則表示天平兩邊的硬幣都是真幣，使用陣列將這些硬幣編號記錄下來；若不相等，則記錄天平兩邊的硬幣編號。利用以下兩種情形判斷偽幣的編號，若全部n個硬幣中，能確定n-1個是真幣，則就能確定剩下一個是假幣；若天秤左右兩邊測量結果不相等的情形，天平兩邊總共有p個，若已經確定p-1個是真幣，則剩下一個一定是假幣，如此就能判斷出偽幣的編號。

輸入說明

第一行有五個正整數s，t，n，m 與 r。 接下來 s 行(line)每行包含 t 個數，第 i 行第 j 個數代表 Aij 的值。 接下來 n 行(line)每行包含 m 個數，第 i 行第 j 個數代表 Bij 的值。 同一行間數字以空格隔開。

測資範圍如下： 

1≤s≤n≤10 

1≤t≤m≤100 

1≤r≤100 

0≤Aij,Bij≤9 

本題包含三個子題組，每個子題組配分如下： 

第 1 子題組共 50 分： s=n=1 

第 2 子題組共 50 分： 無額外限制。

輸出說明

輸出有兩行： 

第一行輸出符合條件的子矩陣個數。 

第二行輸出所有符合條件的子矩陣中，數字總和與A相差最小的值，若找不到符合條件的子矩陣，則輸出−1。

輸入範例1

1 3 1 10 1

7 4 7

6 7 7 7 4 5 0 4 4 7

輸出範例1

3

2

輸入範例2

3 3 5 5 2

1 2 1

2 4 2

2 4 5

1 2 1 2 3

2 4 2 4 2

2 4 2 3 5

3 2 4 2 0

3 2 4 5 5

輸出範例2

3

1

解題策略

暴力，列舉n*m二維陣列B的所有s*t的子陣列，與陣列A計算距離小於等於r，子陣列數字總和與陣列A相差最小的值

範例練習4  APCS201906第4題美麗的彩帶 

作業上傳：http://203.68.236.9/problem/c0302

https://zerojudge.tw/ShowProblem?problemid=e289

你有一條彩虹色的彩帶，但是因為它是異世界來的彩帶，所以可能不只七個顏色(異世界有可能有87色的彩虹)，

你有一個定義彩帶美麗度的標準，你定義一條彩帶的美麗度為它所擁有的長度為 m 且有 m 種顏色的子區間數量

現在你需要寫一個程式來計算一個字串的美麗度

輸入說明

第一行有兩個數字 m 和 n ，代表定義的子區間長度和彩帶長度

第二行有 n 個數字代表彩帶的顏色

輸出說明

輸出這條彩帶的美麗度

輸入範例1

3 7

1 2 3 5 4 5 4

輸出範例1

3

輸入範例1說明 ：

共有 5 個長度 m 的子區間

分別為

1 2 3

2 3 5

3 5 4

5 4 5

4 5 4

其中 3 個有 3 種不同顏色

所以美麗度為 3

20% 所有數字介於 1 ~ m 之間且 m ≤ n ≤ 10000

68% 所有數字可以被 int 存入且 m ≤ n ≤ 200000 

100% 所有數字介於 0 ~ 10^150 之間且 m ≤ n ≤ 200000

解題策略

雙指標，暴力，模擬

使用map紀錄元素與元素個數，每次刪除一個元素與新增一個元素，確定map元素個數是否為m個

輸入範例

5 5

-3 -3 3 3 -3

2 2 2 2 2

5 5

-3 -3 -3 5 -5

-5 5 -3 -3 -3

4 3

1 2 3 4

-1 -2 -3

輸出範例

12

77

-1

解題策略

枚舉、模擬、貪婪

枚舉兩陣列的內積的所有可能性

Step1)先取A陣列的最後一個，與B陣列的第一個求內積，更新最大值。

Step2)取A陣列的最後兩個，與B陣列的前面兩個求內積，首先計算A陣列倒數第二個與B陣列第一個內積到加總值(sum)，更新最大值，如果加總值(sum)小於0則更新為0，接著累加A陣列倒數第一個與B陣列第二個內積到加總值(sum)，更新最大值，此時已經計算出兩個區段的內積，減少重覆計算，有DP的精神。如果前一個相鄰點的內積大於0，則累加起來一定會更大，如果相鄰點的內積小於0，則歸0才能求出更大內積。

Step3)取A陣列的最後三個，與B陣列的前面三個求內積，首先計算A陣列倒數第三個與B陣列第一個內積到加總值(sum)，更新最大值，如果加總值(sum)小於0則更新為0，接著累加A陣列倒數第二個與B陣列第二個內積到加總值(sum)，更新最大值，此時已經計算出兩個區段的內積，減少重覆計算，有DP的精神，接著累加A陣列倒數第一個與B陣列第三個內積到加總值(sum)，更新最大值，此時已經計算出三個區段的內積，減少重覆計算，有DP的精神。如果前一個相鄰點的內積大於0，則累加起來一定會更大，如果相鄰點的內積小於0，則歸0才能求出更大內積。

依此類推，直到陣列A第一個元素與陣列B最後一個元素求內積。

Step4)反向也需要計算一次。