《《算法設計與分析》第05章.ppt》由會員分享，可在線閱讀，更多相關《《算法設計與分析》第05章.ppt（103頁珍藏版）》請在裝配圖網上搜索。

1、算法設計與分析 DeSign and Analysis of Algorithms In C+ “十一五”國家級規(guī)劃教 材 陳慧南 編著 電子工業(yè)出版社 第 2部分 算法設計策略 第 5章 分治法 5.1 分治法的基本思想 5.2 求最大最小元 5.3 二分搜索 5.4 排序問題 5.5 選擇問題 5.6 斯特拉森矩陣乘法 5.1 一般方法 5.1.1 分治法的基本思想 分治法 顧名思義就是分而治之 。 一個問題能夠 用分治法求解的要素是：第一 ， 問題能夠按照某 種方式分解成若干個規(guī)模較小 、 相互獨立且與原 問題類型相同的子問題；第二 ， 子問題足夠小時 可以直接求解；第三 ， 能夠將子問

2、題的解組合成 原問題的解 。 由于分治法要求分解成同類子問題 ， 并允許不 斷分解 ， 使問題規(guī)模逐步減小 ， 最終可用已知的 方法求解足夠小的問題 ， 因此 ， 分治法求解很自 然導致一個遞歸算法 。 【 程序 5-1】 分治法 SolutionType DandC(ProblemType P) ProblemType P1， P2， ， Pk; if (Small(P) return S(P); else Divide(P， P1， P2， ， Pk); Return Combine(DandC(P1)， DandC(P2)， ， DandC(Pk); 【 程序 5-2】 一分為二的分治法

3、 SolutionType DandC(int left， int right) if (Small(left, right) return S(left,right); else int m=Divide(left， right); Return Combine(DandC(left， m)， DandC(m+1， right); 5.1.2 算法分析 采用分治法求解問題通常得到一個遞歸算法。如 果較大的問題被分解成同樣大小的幾部分，那么分 析相應算法的執(zhí)行時間，往往可得到如下的遞推關 系式： T(n) = aT(n/b) + cnk， T(1) = c 定理 5-1 設 a,b,c和 k為

4、常數， T(n)=aT(n/b)+cnk， T(1)=c，則， kk kk kal o g ba )n( ba )nl o gn( ba )n( )n(T b 如果 如果 如果 m i ikm m i ikim kkkmmm kkk kkk kk kk k abca bac cnbnacbncaTa cnbnacbncabnTa cnbnacbncbnaTa cnbnacbnTa cnbncbnaTa cnbnaTnT 0 0 11 2233 232 22 2 )/( )/()/()1( )/()/()/( )/()/()/( )/()/( )/()/( )/()( 設 r= bk /a ，

5、下面分三種情況計算 。 （ 1） 若 r1， 則 所以 )r1/(1r m 0i i )(nT (n ) al o g b nl o g1m1r b m 0i i )nl o gn()nl o g (nT (n ) kal o g b )r(1r 1rr m 1mm 0i i )n()b()r(aT ( n ) kmkmm 例如： (1) T(n)=2T(n/2)+n a=2,b=2,k=1,a=bk 所以 T(n)= (nlog(n) (2) T(n)=4T(n/4)+n2 a=4,b=4,k=2,abk 所以 T(n)= (n4) kk kk kal o g ba )n( ba )nl o

6、 gn( ba )n( )n(T b 如果 如果 如果 5.1.3 數據結構 【 程序 5 3】 可排序表類 template struct E /可排序表中元素的類型 operator K( ) const return key; /重載類型轉換運算符 K key; /關鍵字可以比較大小 D data; /其他數據 ; template class SortableList /可排序表類 public: SortableList(int mSize) /構造函數 maxSize=mSize; l=new TmaxSize; n=0; SortableList()delete l; /析構函數

7、 private: T *l ; /定義動態(tài)一維數組 int maxSize; /線性表的最大表長 int n; /線性表的實際長度 ; 5.2 求最大最小元 問題 在一個元素集合中尋找最大元素和最小元 素的問題。 5.2.1 分治法求解 【 程序 5 4】 求最大最小元 template void SortableList:MaxMin(T max=min=l0; for (int i=1; imax) max=li; if(limin) min=li; / /Tn=2(n-1) 5.2.1 分治法求解 【 程序 5 4】 求最大最小元 template void SortableList:

8、MaxMin(T max=min=l0; for (int i=1; imax) max=li; else if(limin) min=li; Wn=2(n-1) (遞減有序） Bn=n-1(遞增有序） 【 程序 5 5】 分治法求最大最小元 template void SortableList:MaxMin(int i, int j, T if (i=j) max=min=li; else if (i=j-1) if (lilj) max=lj; min=li; else max=li; min=lj; else int m=(i+j)/2; MaxMin(i,m,max,min); Max

9、Min(m+1,j,max1,min1); if (maxmin1) min=min1; 5.2.2 時間分析 定理 5 2 設有 n個元素的表 ， 假定 n是 2的冪 ， 即 n=2k， k 是正整數 ， 程序 5 5在最好 、 平均和最壞情況下 的比較次數都為 3n/22。 2n 2)2/n(T)2/n(T 2n 1 1n 0 )n(T n=2k,T(n)=2T(n/2)+2 T(n)=3n/2-2 5.3 二分搜索 問題 在有序表 （ 已按關鍵字值非減排序 ） 中搜 索給定元素的問題 。 5.3.1 分治法求解 int SortableList:BSearch(const T if (x

10、lm) return BSearch(x,m+1,right); else return m; return -1; 5.3.2 對半搜索 對半搜索 對半搜索是一種二分搜索 。 設當前搜索的子表 為 （ aleft,aleft+1, ,aright） ， 令 m=(left+right)/2 例如，假設給定有序表中關鍵字為 8,17,25,44,68,77,98,100,115,125，將查找 K=17和 K=120的情況描述為以下形式。 8 17 25 44 68 77 98 10 1 15 125 low high (a) 初始情形 8 17 25 44 68 44 98 100 1 15

11、 125 low hig h m id (b ) 經過一次比較后的情形 8 1 7 2 5 4 4 6 8 7 7 9 8 1 0 0 1 1 5 1 2 5 ( c ) 經過二次比較后的情形 ( R m id .k e y = 17) l o w m i d h i g h 查找 K = 17 的示意圖 ( 查找成功 ) 8 17 25 44 68 77 98 100 1 15 125 (a) 初始情形 low hig h 8 17 25 44 68 77 98 100 1 15 125 (b ) 經過一次比較后的情形 m id low hig h 8 17 25 44 68 77 98 1

12、00 1 15 125 (c) 經過二次比較后的情形 m id low hig h 8 17 25 44 68 77 98 100 1 15 125 (d ) 經過三次比較后的情形 m id low hig h 17 25 44 77 98 10 0 1 15 12 5 hi gh l ow m i d (e) 經過四次比較后的情形 ( h i g h lo w ) 查找 K= 1 2 0 的示意圖 ( 查找不成功 ) 【 程序 5 7】 對半搜索遞歸算法 template int SortableList:BSearch(const T if (xlm) return BSearch(x,m

13、+1,right); else return m; return -1; 二分查找的性能分析 為了分析二分查找的性能 ， 可以用二叉樹來描述二分查 找過程 。 把當前查找區(qū)間的中點作為根結點 ， 左子區(qū)間和右 子區(qū)間分別作為根的左子樹和右子樹 ， 左子區(qū)間和右子區(qū)間 再按類似的方法 ， 由此得到的二叉樹稱為二分查找的判定樹 。 例如 ， 對關鍵字序列 8,17,25,44,68,77,98,100,115,125， 的判定 樹下圖 。 44 8 25 17 98 77 68 100 1 15 125 圖具有 10 個關鍵字序列的二分查找判定樹 二分查找的性能分析 44 8 25 17 98 7

14、7 68 100 1 15 125 圖具有 10 個關鍵字序列的二分查找判定樹 查找成功：最好： Ws=1；最壞： Ws= logn +1= O(logn) 查找失?。?Wf= logn +1 = (logn) 搜索成功的平均時間復雜度： 從上圖可知 ， 查找根結點 68， 需一次查找 ， 查找 17 和 100， 各需二次查找 ， 查找 8、 25、 77、 115各需三 次查找 ， 查找 44、 98、 125各需四次查找 。 于是 ， 可 以得到結論：二叉樹第 K層結點的查找次數各為 k次 (根結點為第 1層 )， 而第 k層結點數最多為 2k-1個 。 假 設該二叉樹的深度為 h， 則

15、二分查找的成功的平均查 找次數為 （ 假設每個結點的查找概率相等 ） ： ASL= = 1/n 1/n(1+22+322+h 2h-1) =1/n n i ii cp 1 n i ic 1 h k kk 1 12 設 s= =20+221+322+ +(h-1)2h-2+h2h-1 則 2s=21+222+ +(h-2)2h-2+(h-1)2h-1+h2h s=2s-s =h .2h-(20+21+22+ +2h-2+2h-1) =h .2h-(2h-1) h k kk 1 12 ASL=1/n( log2(n+1) (2h-1+1)-n) =1/n( log2(n+1) (n+1)-n) =

16、(n+1)/n log2(n+1)-1 =(1+1/n) log2(n+1)-1 當 n很大時， ASL log2(n+1)-1 可以作為二分查找成 功時的平均查找長度，它的時間復雜度為 (log2n)。 根據二叉樹的性質，最大的結點數 n=2h-1， h=log2(n+1) ，于是可以得到平均查找次數 ASL=s/n ASL= 1/n(h2h-(2h-1) 5.3.4 搜索算法的時間下界 定理 5 6 在一個有 n個元素的集合中 ， 通過關鍵字值之間 的比較 ， 搜索指定關鍵字值的元素 ， 任意這樣的算 法在最壞情況下至少需要作 log n+1次比較 。 5.4 排序問題 問題 排序是將一個

17、元素序列調整為按指定關鍵字值的 遞增（或遞減）次序排列的有序序列。 合并兩個有序表： 合并算法排序也屬于分治方法。合并（ Merge） 就是將兩個或多個有序表合并成一個有序表，例如 下圖所示的兩個有序表經合并運算后得到一個有序 表。我們在此只用到兩個有序表的合并，稱為二路 合并 Two-way merge）。 5.4.1 合并排序 合并排序（ Merge sort）就是利用這種合并 過程進行排序，即先將 n個數據看成 n個長度為 l 的表，將相鄰的表成對合并，得到長度為 2的 n/2個有序表；進一步再將相鄰表成對合并，得 到長度為 4的 n/4個有序表； ；如此重復做下 去，直至所有數據均合并

18、到一個長度為 n的有序 表為止，即完成排序。上述每一次的合并過程 稱為一趟 Pass），整個排序過程叫二路合并 排序。下圖是二路合并排序過程的一個例子。 合并排序 7 15 13 10 4 20 19 8 7 15 10 13 4 20 8 19 7 15 13 10 4 20 19 8 7 10 13 15 4 8 19 20 4 7 8 10 13 15 19 20 合并兩個有序序列 【 程序 5 9】 合并兩個有序序列 （ Merge函數 ） template void SortableList:Merge(int left, int mid,int right) T* temp=new

19、 Tright-left+1; int i=left,j=mid+1,k=0; while ( i=mid ) else tempk+=lj+; while (i=mid) tempk+=li+; while (j=right) tempk+=lj+; for (i=0,k=left;k=right;) lk+ = tempi+; 分治法求解 將待排序的元素序列一分為二分 ， 得到兩個長度 基本相等的子序列 ， 如同對半搜索的做法；然后對 兩個子序列分別排序 ， 如果子序列較長 ， 還可繼續(xù) 細分 ， 直到子序列的長度不超過 1為止；當分解所得 的子序列已排列有序 ， 可以采用上面介紹的將兩個

20、 有序子序列 ， 合并成一個有序子序列的方法 ， 實現(xiàn) 將子問題的解組合成原問題解 ， 這是分治法不可缺 少的一步 。 對于二路合并，如果數據個數 n是 2的整數 次方，則所需的趟數為 logn，例如 n=8， logn=3， 故共需三趟合并過程。如果 n不是 2的整數次方， 則在每趟合并時表的數目不一定總是偶數個。 若表的數目為奇數，就剩下一個表要 “ 輪空 ” ， 直接進入下一趟。這樣，下一趟合并時此表的 長度與其它的表將不相同，因此我們設計的合 并過程，并不要求待合并的兩個表長度必須相 同。 【 程序 5 10】 兩路 合并排序 template void SortableList:Me

21、rgeSort(int left,int right) if (leftright) int mid = (left+right)/2; MergeSort(left,mid); MergeSort(mid+1,right); Merge(left,mid,right); template void SortableList:MergeSort() MergeSort(0,n-1); 性能分析 合并排序遞歸算法的時間復雜度為 (nlog n)。 1n cn)2/n(T2 1n d)n(T 1n )2/(2 1n )( cnnT dnT 定理 5-1 設 a,b,c和 k為常數， T(n)=aT

22、(n/b)+cnk， T(1)=c，則， kk kk kal o g ba )n( ba )nl o gn( ba )n( )n(T b 如果 如果 如果 使用 遞歸樹 可以形象地看到遞推式的迭代過程。 例 2-13 T(n) = 2T(n/2) + n的遞歸樹 遞歸路徑： n-(1/2)n-(1/2)2n .(1/2)kn1 (1/2)kn=1，即 n/2k=1，即 2k=n， k=log2n=logn 所以 T(n)=n*(logn+1)= (nlogn) 5.4.2 快速排序 快速排序采用一種特殊的分劃操作對排序問題進 行分解，其分解方法是：在待排序的序列 (K0,K1, Kn-1)中選

23、擇一個元素作為分 劃元素 ，也稱 為 主元 （ pivot）。不妨假定選擇 K為主元。經過一 趟特殊的分劃處理將原序列中的元素 重新排列 ，使 得以主元為軸心，將序列分成左右兩個子序列。主 元左測子序列中所有元素都不大于主元，主元右測 子序列中所有元素都不小于主元。 15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20 1、主元最后的位置就是它最終的合適位置，進一步 的運算過程中此數據即不必再動； 2、以后的排序運算只需在劃分成的兩部分里進行， 兩部分之間不會再有數據互換。 3、第一次劃分以后，再用相同的算法對劃成的部分 進行類似的運算，即從每部分中任選一個數據將

24、其 劃分成更小的兩部分，依此遞歸地做下去，直至每 個小部分中的數據個數均不超過一個為止，排序過 程即結束。 15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20 分劃操作 【 程序 5 11】 分劃函數 template int SortableList:Partition(int left, int right) /前置條件： leftright int i=left,j=right+1; do do i+; while (lilleft); if (ij) Swap(i,j); while (ij); Swap(left,j); return j; 快速排序算

25、法 【 程序 5 12】 快速排序 template void SortableList:QuickSort() QuickSort(0,n-1); template void SortableList:QuickSort(int left,int right) if(leftright) int j=Partition(left,right); QuickSort(left,j-1); QuickSort(j+1,right); 若快速排序出現(xiàn)最壞的情形 （ 每次能劃分成兩個子區(qū)間 ， 但其中一個是空 ） ， 因此 ， 快速排序的最壞時間復雜度為 O(n2)。 快速排序所占用的輔助空間為棧的

26、深度 ， 故最好的空間 復雜度為 O（ logn） ， 最壞的空間復雜度為 O(n2)。 若快速排序出現(xiàn)最好的情形 （ 左 、 右子區(qū)間的長度大致 相等 ） ， 快速排序的最好時間復雜度應為 O（ nlog2n） 。 時間分析 理論上已經證明，快速排序的平均時間復雜度也為 O（ nlogn）。 平均情況時間 )k(A n 2 1n )1kn(A)k(A( n 1 1n)n(A 1n 0k 1n 0k )k(A2)1n(n)n(nA 1n 0k )k(A2)1n(n)1n(A1n 2n 0k ）（ )1n(l o g2 x dx 2 k 1 2 3 2 1n 2 n 2 1n 2 2 1A 1n

27、 2 n 2 1n 2 2n 3nA n 2 1n 2 1n 2nA 1n 2 n 1nA 1n )n(A 1n 3k 1n 2 e ）（ ）（ ）（ ）（ )nl o gn(O)1n(l o g)1n(2)n(A e 5.4.3 排序算法的時間下界 定理 5 7 任何一個通過關鍵字值比較對 n個元素進行排序 的算法 ， 在最壞情況下 ， 至少需作 （ n/4） log n 次比較 。 5.5 選擇問題 問題 選擇問題（ select problem）是指在 n個元素的集 合中，選出某個元素值大小在集合中處于第 k位的 元素，即所謂的 求第 k小元素問題 (kth-smallest)。 5.5

28、.1 分治法求解 設原表長度為 n， 假定經過一趟分劃 ， 分成兩個左 右子表 ， 其中左子表是主元及其左邊元素的子表 ， 設其長度為 p， 右子表是主元右邊元素的子表 。 那 么 ， 若 k=p， 則主元就是第 k小元素；否則若 kp， 則第 k小元素必 定在右子表中 ， 需求解的子問題成為在右子表中求 第 k-p小元素 。 15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20 5.5.2 隨機選擇主元 隨機選主元算法 假定表中元素各不相同 ， 并且隨機選擇主元 ， 即 在下標區(qū)間 left,right中隨機選擇一個下標 r， 以該 下標處的元素為主元 。 【

29、程序 5 13】 Select函數 template ResultCode SortableList:Select1(T int left=0, right=n; ln = INFTY; do int j=rand()% (right-left+1)+left; Swap(left,j); j=Partition(left, right); if (k=j+1) x=lj;return Success; else if (kj+1) right=j; else left=j+1; while (true); 定理 5 8 程序 5 13的 Select算法的平均時間 A(n)=O(n)。 算法

30、的最壞情況時間復雜度 O(n2) 。 5.5.3 線性時間選擇算法 改進的選擇算法采用 二次取中法 (median of medians rule)確定主元 【 程序 5 14】 線性時間選擇算法 ResultCode SortableList:Select(T int j=Select(k,0,n-1,5); x=lj;return Success; template int SortableList:Select(int k, int left,int right,int r) int n=right-left+1; if (n=r) InsertSort(left,right); ret

31、urn left+k-1; for (int i=1;i=n/r;i+) InsertSort(left+(i-1)*r,left+i*r-1); Swap(left+i-1, left+(i-1)*r+Ceil(r,2)-1); int j=Select(Ceil(n/r,2),left,left+(n/r)-1,r ); Swap(left,j); j =Partition(left,right); if (k=j-left+1) return j; else if (kj-left+1) return Select(k,left,j-1,r); else return Select(k-

32、(j-left+1),j+1,right,r); 5.5.4 時間分析 以二次取中的中間值 mm為主元，經過一趟分 劃，左、右兩個子表的大小均至多為： nn/r/2 r/2 設 T(n)為當表長為 n時執(zhí)行程序 5 14所需的時 間 。 T(n)由三部分時間組成： T(n)T(n/5)+T(3n/4)+cn 用歸納法容易證明 ， T(n)20cn， n1是線性時 間的 。 5.5.5 允許重復元素的選擇算法 由于允許包含相同元素 ， 左子表中除了小于 mm的 元素外 ， 還包含與 mm相同值的元素 。 因此 ， 左子 表的大小至多可達 nn/r/2 r/2+1/2 n/r/2 r/2 = n-

33、1/2 n/r/2 r/2 容易用歸納法證明對于所有 n90， T(n)T(n/9)+T(7n/8)+cn72cn， n90 5.6 斯特拉森矩陣乘法 問題 矩陣相乘 矩陣乘積的 Strassen算法 C=AB=(cij)n n。 求 C=AB即對 n2個元素 cij進行計算 ， 故要作 n3次乘法 。 相當時間內沒有人懷疑過是否可以用少于 n3次乘法來 完成 。 其實不然 ， 先以 n=2的矩陣乘積為例 。 對于矩陣 則有： 共需作 8次乘法和 4次加法。 分治法求解大矩陣 C11 A11B11+A12B21 C12 A11B12+A12B22 C21 A21B11+A22B21 C22 A

34、21B12+A22B22 2221 1211 2221 1211 2221 1211 CC CC BB BB AA AA 一個四階方陣可以看作由 4個二階方陣組成 分治法求解大矩陣 C11 A11B11+A12B21 C12 A11B12+A12B22 C21 A21B11+A22B21 C22 A21B12+A22B22 一個 n階方陣可以看作由 4個 n/2階的方陣組成，二個 n 階方陣的乘積，轉化為八個 n/2階方陣的乘積和 4個 n/2階方陣的加法。 2n dn)2/n(T8 2n b)n(T 2 T(n)=(n 3) 定理 5-1 設 a,b,c和 k為常數， T(n)=aT(n/b

35、)+cnk， T(1)=c，則， kk kk kal o g ba )n( ba )nl o gn( ba )n( )n(T b 如果 如果 如果 5.6.2 斯特拉森分治法 P=(A11+A22)(B11+B22) Q=(A21+A22)B11 R=A11(B12-B22) S=A21(B21-B11) T=(A11+A12)B22 U=(A21-A11)(B11+B12) V=(A12-A22)(B21+B22) C11=P+S-T+V C12=R+T C21=Q+S C22=P+R-Q+U 2n dn)2/n(T7 2n b )n(T 2 T(n)= (nlog 7)(n2. 81) 2

36、*2矩陣的最少乘法次數是 7。 目前最好的矩陣乘法的時間上界是： O(n2.376)。 我們研究兩個 n位二進制數相乘的問題。用普通的方 法運算，將乘數的每一位（由低位至高位）逐個去乘 被乘數，每乘一次將乘積與原來的積相加，然后乘數 和乘積移位一步，如此下去直至乘數的最高位運算完 即得出結果，這樣運算共需 n2 次一位乘一位運算， n(n-1)次一位加一位運算和 n次移位，假設兩個一位數 相乘，兩個一位數相加和任何數移位一步所需運算時 間均為 O(1)，即均為常數?？傔\算復雜性為 O（ n2）。 大整數相乘 現(xiàn)在用分治法來做。設 n=2r,將兩個數都按位數劃分成 兩段，如圖所示， 這需要三次

37、n位的加法，一次 n步移位，一次 n/2步 移位和四次 n/2位的乘法。 設用分治法做兩個 n位數乘法的復雜性為 T （ n），因加法和移位都是 O（ n），故： 這樣并沒有顯出其優(yōu)越性，我們可以將其進一步 改進，增加一些加法運算以減少乘法運算。 定理 5-1 設 a,b,c和 k為常數， T(n)=aT(n/b)+cnk， T(1)=c，則， kk kk kal o g ba )n( ba )nl o gn( ba )n( )n(T b 如果 如果 如果 減少了乘法運算的次數。 顯然較普通方法更有效。這種思想同樣可以用 于十進制數的乘法中。 類似于上述例子，可以看出，一般情況下采用 分治解決

38、法劃分子問題時，使各子問題的規(guī)模盡量 相等為好。此外，如果是逐層劃分，采用遞歸形式 可以使程序簡而明，分析起來也較為方便。 計算： 2348 3825=？ 循環(huán)賽日程表 設有 n=2k個運動員要進行網球循環(huán)賽 。 現(xiàn)要設計一 個滿足以下要求的比賽日程表： （ 1） 每個選手必須與其他 n-1個選手各賽一次； （ 2） 每個選手一天只能賽一次； （ 3） 循環(huán)賽一共進行 n-1天 。 按此要求可將比賽日程表設計成有 n行和 n列的 一個表 。 在表中第 i行和第 j列處填入第 i個選手在第 j 天所遇到的選手 。 4個選手的比賽日程表 日程 選手 一 二 三 四 五 六 七 1 2 3 4 5

39、6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 按分治策略 ， 我們可以將所有選手對分為兩組 ， n個選手 的比賽日程表就可以通過為 n/2個選手設計的比賽日程表來 決定 。 遞歸地用這種一分為二的策略對選手進行分割 ， 直到 只剩下 2個選手時 ， 比賽日程表的制定就變得很簡單 。 這時 只要讓這 2個選手進行比賽就可以了 。 下圖所列出的正方形表是 4個選手的比賽日程表 。 其中左 上角與左下角的兩小塊分別為選手 1至選手 2和選手 3至選手 4 第 1天的比賽日程 。 據此 ， 將左上角小塊中的所有數字按其 相對位置抄到右下角 ， 將左下角小塊中的所有數字按其相對 位置抄到右上角 ， 這樣我們就分別安排好了選手 1至選手 2和 選手 3至選手 4在后 2天的比賽日程 。 這種安排是符合要求的 。 4個選手的比賽日程表 依此思想容易將這個比賽日程表推廣到具有任意 多個選手的情形。下表是 8個選手的日程安排表。