Embedded Files
(1)組合(樂透包牌)
*(上課)練習題 c074: Lotto acm 441 列出所有可能組合
給定n個數字，n個數字都不相同，從n個數字中取出m個數字的所有可能性，輸出的m個數字請按照由小到大輸出，不要重複輸出，保證m小於等於n。
輸入說明
輸入整數n，之後接著輸入n個數字，接著輸入整數m，表示要從n個數字中選取m個。
輸出說明
從n個數字中取出m個數字的所有可能性，輸出的m個數字請按照由小到大輸出，不要重複輸出。。
輸入範例
6 23 41 34 5 17 22 5
輸出範例
5 17 22 23 34
5 17 22 23 41
5 17 22 34 41
5 17 23 34 41
5 22 23 34 41
17 22 23 34 41
解題想法
使用遞迴方式暴力找出所有可能性，需要陣列num儲存輸入的n個數字，陣列step儲存包牌的在陣列num的索引值。遞迴需要兩個參數，一個控制目前選取幾個(currStep)，一個控制目前的起始元素讓選取的元素不重複。
程式碼
(2) 排列
給定n個相異的數字，請列出此n個數字的所有排列可能性。
輸入說明
輸入整數n，之後接著輸入n個數字。
輸出說明
列出n個數字的所有排列可能性。
輸入範例
3 5 4 6
輸出範例
4 5 6
4 6 5
5 4 6
5 6 4
6 4 5
6 5 4
解題想法
使用遞迴方式暴力找出所有排列的可能性，需要陣列num儲存輸入的n個數字，陣列step的元素儲存數字對應的陣列num索引值。遞迴需要一個參數，控制目前排列到第幾個(currStep)。
程式碼
每個數字都不同的排列
重複數字的排列
使用STL的next_permutation進行排列
(3)列舉所有子集合
列舉n個元素的所有子集合，有兩種寫法，一個使用遞迴，另一個使用位元運算。遞迴列舉所有可能性，考慮每一個元素取或不取。
列舉所有子集合-遞迴解1
列舉所有子集合-遞迴解2
位元運算使用數值0到2^n - 1的二進位表示，例如：假設n等於4，集合為{1,2,3,4}，0的二進位為0000，表示{}；1的二進位為0001，表示{1}；2的二進位為0010，表示{2}；3的二進位為0011，表示{1,2}；...；15的二進位為1111，表示{1,2,3,4}，就可以列出所有子集合。
列舉所有子集合-位元運算解
(4) 8queue問題，回溯法(backtracking)
*(上課)練習題 d324:acm-750 - 8 Queens Chess Problem 8Queen DFS
將西洋棋的8個queen放在8x8的棋盤上，如何擺放讓8個queen彼此互相不衝突，請找出在8x8棋盤上放上8個queen，而彼此相互不衝突的所有解。西洋棋的queen對於同一列、同一行與兩個對角線可以吃掉對方，如下圖，Q表示放置queen在第3列第4行，X表示這些位置不能放其他queen會發生衝突。
輸入說明
本題不需要輸入。
輸出說明
輸出所有可能的解，先輸出目前是第幾個解，接著輸出8個queen在8x8的棋盤上所在位置，每一行一定會有一個queen，請由第1行到第8行順序，依序輸出8個queen所在列的編號，舉例如下，下表中8個queen彼此互相不衝突，以「1 5 8 6 3 7 2 4」表示此8個queen在棋盤由左到右所在的列編號。
輸入範例
無須輸入。
輸出範例
全部共有92個解，輸出後面12個。
81 7 1 3 8 6 4 2 5
82 7 2 4 1 8 5 3 6
83 7 2 6 3 1 4 8 5
84 7 3 1 6 8 5 2 4
85 7 3 8 2 5 1 6 4
86 7 4 2 5 8 1 3 6
87 7 4 2 8 6 1 3 5
88 7 5 3 1 6 8 2 4
89 8 2 4 1 7 5 3 6
90 8 2 5 3 1 7 4 6
91 8 3 1 6 2 5 7 4
92 8 4 1 3 6 2 7 5
解題想法
使用遞迴方式暴力找出所有可能性，需要陣列s儲存8個queen所在的列編號。
程式碼
範例練習1 數字包牌
https://zerojudge.tw/ShowProblem?problemid=e289
小涵是妳喜歡的人，可是她現在很無聊，她選了n個正整數給你玩，你要從這幾個數中選出m個號碼。
她說：如果你能輸出這些選出數字的所有可能，她才會喜歡妳噢。 (m<=n<=100)
PS.姓名純屬杜撰，如有雷同純屬巧合。
輸入說明 ：
本題有多組測試資料。
每組測試資料有一行，第一個數n，接下來有n個數 A1~An，這些數不會有重覆的 ，最後有一個數 m。
若n=0請結束程式，不必輸出任何資料。
輸出說明 ：
你可以輸出:
1."我一點都不喜歡妳!!" (不含雙引號) 她就會因為過度傷心而讓你得到WA。
2.由小到大，依序列出從這n個數中選出m個號碼的所有可能 (請參考範例測資)。她就會因為過度開心而讓你得到AC。 全部可能輸出後請空一行。
範例輸入 ：
3 6 2 5 2
5 5 2 3 9 12 2
0
範例輸出 ：
2 5
2 6
5 6
2 3
2 5
2 9
2 12
3 5
3 9
3 12
5 9
5 12
9 12
提示 ：
出處 ：
(管理：magrady)
範例練習2 APCS201810第2題子集合的和
作業上傳：http://203.68.236.9/problem/c0003
TCIRC：https://judge.tcirc.tw/ShowProblem?problemid=d007
輸入 n 個正整數，請計算各種組合中，其和最接近 P 但不超過 P 的和是多少。 每個元素可以選取或不選取但不可重複選，輸入的數字可能重複。 P≤1000000009，0<n<26。
輸入說明
第一行是 n 與 P， 第二行 n 個整數是 A[i]， 同行數字以空白間隔。
輸出說明
最接近 P 但不超過 P 的和。
輸入範例1
5 17
5 5 8 3 10
輸出範例1
16
解題策略
枚舉、遞迴
範例練習3 APCS202109 第3題幸運數字
zerojudge網址：https://zerojudge.tw/ShowProblem?problemid=g277
在 n 個人之中，每個人被分配到一個號碼，記錄為 a1,a2,…,an，這些號碼彼此都不相同，我們要找出當中最幸運的一個
已知在[L,R] 區間之中，最幸運號碼定義為：
當 L=R 時，幸運號碼為 a[L]
當 L<R 時，找出當中最小號碼的位置 m，並以最小號碼所在的位置將整個區間區分為左邊 [L,m−1]與右邊 [m+1,R]，計算兩個區間各自的總和，總和比較大的區間即為幸運號碼所在的區間；如果兩個區間的總和相等，則幸運號碼位在右邊的區間，若區間不包含任何數字，總和視為 0
重複以上步驟直到收斂至1. 時即可找到幸運號碼 請找出這 n 個人之中的幸運號碼
輸入說明
第一行輸入一個正整數 n(1≤n≤3×10^5)，接下來有 n 個數字 a1,a2,…,an(1≤ai≤10^7)
輸出說明
輸出這 n 個數字中的幸運數字數值
輸入範例
5
4 2 3 1 5
8
3 9 4 5 1 6 2 8
輸出範例
4
9
解題策略
前綴和、遞迴、map
使用map建立數字與索引值對應的字典，且鍵值由小到大排序，可以加速搜尋每個區間最小數值所在位置。
範例練習4 APCS201910 第4題刪除邊界
TCIRC：https://judge.tcirc.tw/ShowProblem?problemid=d082
一個矩陣的第一列與最後一列以及第一行與最後一行稱為該矩陣的四條邊界線，
如果某一條邊界線的內容都是相同元素，則可以刪除該邊界線。
如果一條邊界線的內容不完全相同，你可以修改某些格子的內容讓邊界線的內容變成相同後，再刪除該邊界線。
矩陣在刪除一條邊界線後，還是一個矩陣，但列數或行數會減少一，本題的目標是重複執行修改與刪除邊界的動作，最後將整個矩陣刪除。
輸入一個 0/1 矩陣，請計算最少要修改多少個元素才能將整個矩陣刪除。
請注意：根據定義，只有一列或是只有一行的矩陣可以不需要任何修改就可以被全部刪除。
輸入說明
第一行為兩個不超過 25 的正整數 m 和 n，
以下 m 列 n 行是矩陣內容，順序是由上而下，由左至右，矩陣內容為 0 或 1，同一行數字中間以一個空白間隔。
輸出說明
最少修改次數。
輸入範例1
4 5
0 1 0 1 1
1 1 1 0 1
0 0 0 0 0
0 0 0 1 0
輸出範例1
2
輸入範例2
3 5
0 0 0 1 0
1 0 1 1 1
0 0 0 1 0
輸出範例2
1
解題策略
遞迴+陣列暫存結果
Page updated
Google Sites
Report abuse