比赛日程安排
問題描述:
設有n（2^k）位選手參加網球循環賽，循環賽共進行n-1天，每位選手要與其他n-1位選手比賽一場，且每位選手每天只能賽一場，試安排比賽。
?
舉例說明：
1，當n為偶數時，循環賽一共要進行n-1天；比如，有運動員：周董，信哥，蔡依林，小七，一共4個人，可以如下安排：
?
運動員 | 第一天 | 第二天 | 第三天 |
周董 | 信哥 | 蔡依林 | 小七 |
信哥 | 周董 | 小七 | 蔡依林 |
蔡依林 | 小七 | 周董 | 信哥 |
小七 | 蔡依林 | 信哥 | 周董 |
?
可以看出，當四個人比賽的時候，要比3天才能全部比完。
?
2，當n為奇數時，循環賽要進行n天；如圖，現有運動員：周董，信哥，蔡依林
，比賽安排表如下：
?
運動員 | 第一天 | 第二天 | 第三天 |
周董 | 信哥 | 蔡依林 | X |
信哥 | 周董 | X | 蔡依林 |
蔡依林 | X | 周董 | 信哥 |
?
可以看出，當n=3時，人數為奇數，并且出現輪空現象。
?
綜上，我們可以得出一個基本結論
?
? | 比賽次數= |
n為偶數 | n-1天 |
n為奇數 | n天 |
?
?
?
算法描述：
?
按照分治策略，我們將n個選手先一分為二，每組n/2人，如果n為奇數，則（n+1）/2后分組，然后像我們一起的歸并排序那樣，一直分下去，直到最后只有兩個人比賽。
?
舉例說明，6個人比賽，需要比賽5天，安排如下：
?
1 | 2 | 3 | 4 | 5 | 6 |
2 | 1 | 5 | 3 | 6 | 4 |
3 | 6 | 1 | 2 | 4 | 5 |
4 | 5 | 6 | 1 | 3 | 2 |
5 | 4 | 2 | 6 | 1 | 3 |
6 | 3 | 4 | 5 | 2 | 1 |
?
?
回想我們的歸并排序，歸并排序是先分開，最后再合起來。這里也是。
?
我們先將6個人分成2組，每組3個人（[1,2,3],[4,5,6]），然后發現3是個奇數，然后在每組中+1個虛擬人：X和Y；這樣，每組就變成了4個人，然后將這4個人在除以2，我們就得到了一個兩兩組合的小的組。
?
首先來看[1,2]; [3,x]
?
1 | 2 |
2 | 1 |
?
3 | X |
X | 3 |
?
將這兩組合起來：
?
?
1 | 2 |
2 | 1 |
3 | X |
X | 3 |
?
?
這樣，第一天的比賽排好了，然后來排第二天的比賽。
?
接下來第二天讓1跟3比較，這樣2就只能跟x比較了。
?
?
1 | 2 | 3 |
2 | 1 | 3 |
3 | X | 1 |
X | 3 | 2 |
?
依此類推，第三天，讓1跟x比較，2跟3比較：
?
1 | 2 | 3 | x |
2 | 1 | x | 3 |
3 | X | 1 | 2 |
X | 3 | 2 | 1 |
?
這里要得到3個選手的比賽安排，所以，我們將假象的X去掉，并將它的位置以*代替：
?
1 | 2 | 3 | * |
2 | 1 | * | 3 |
3 | * | 1 | 2 |
?
?
?
然后我們也按照這個規律，安排[4,5,6]的日程，得到表格
?
4 | 5 | 6 | * |
5 | 4 | * | 6 |
6 | * | 4 | 5 |
?
將前3天的日程安排合并起來：
?
1 | 2 | 3 | * |
2 | 1 | * | 3 |
3 | * | 1 | 2 |
4 | 5 | 6 | * |
5 | 4 | * | 6 |
6 | * | 4 | 5 |
?
?
?
我們可以看到，第一天，3和6都空閑，可以讓他們比賽；第二天，2和5都空閑，可以讓他們比賽；第三天，1和4空閑，讓他們相互比賽；
?
所以，上表重新安排，得到前3天的日程安排表：
?
1 | 2 | 3 | 4 |
2 | 1 | 5 | 3 |
3 | 6 | 1 | 2 |
4 | 5 | 6 | 1 |
5 | 4 | 2 | 6 |
6 | 3 | 4 | 5 |
?
?
這樣，我們就比較過了[1,2,3]和[4,5,6].
?
然后循環下，得到:
?
[1,2,3]& [5,6,4] | [1,2,3]& [6,4,5] |
?
?
安排三天的比賽：
?
1 | 2 | 3 | 5 |
2 | 1 | 6 | 3 |
3 | 4 | 1 | 2 |
5 | 6 | 4 | 1 |
6 | 5 | 2 | 4 |
4 | 3 | 5 | 6 |
?
1 | 2 | 3 | 6 |
2 | 1 | 4 | 3 |
3 | 5 | 1 | 2 |
6 | 4 | 5 | 1 |
4 | 6 | 2 | 5 |
5 | 3 | 6 | 4 |
?
選取黃色的日程安排，加入到前3天的日程安排表中：
?
1 | 2 | 3 | 4 | 5 | 6 |
2 | 1 | 5 | 3 | 6 | 4 |
3 | 6 | 1 | 2 | 4 | 5 |
4 | 5 | 6 | 1 | 3 | 2 |
5 | 4 | 2 | 6 | 1 | 3 |
6 | 3 | 4 | 5 | 2 | 1 |
?
?
如果n恰好等于2^k，那么，安排日程表就變得比較簡單了，我們先安排兩位選手，
1 | 2 |
2 | 1 |
?
安排4位選手：
?
1 | 2 | 3 | 4 |
2 | 1 | 4 | 3 |
3 | 4 | 1 | 2 |
4 | 3 | 2 | 1 |
?
這時候，我們先按照兩個選手的，將1和2的安排填好，然后填寫左下角的安排，然后將左下角的元素抄到右上角，最后將左上角的元素抄到右下角。
小結：
??? 分治法在將大問題一步一步兩兩分，直到劃分成可以解決的小問題時，求出這些小問題的解，然后再將小問題合成大問題的解，但是前提是這些小問題在求解是不受到其他小問題的解的影響的。
總結
- 上一篇： BC26与BC260Y区别
- 下一篇： 【SQL SERVER 2005+版本行