分治算法-球隊問題

《分治算法-球隊問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、實驗一：分治與遞歸【實驗目的】應用分治與遞歸的算法求循環(huán)賽問題。【實驗性質(zhì)】驗證性實驗?！緦嶒瀮?nèi)容與要求】設有n=2k個運動員要進行網(wǎng)球循環(huán)賽。現(xiàn)要設計一個滿足以下要求的比賽日程表：⑴每個選手必須與其他n-1個選手各賽一次；⑵每個選手一天只能賽一次；⑶循環(huán)賽一共進行n-1天。按此要求可將比賽日程表設計－成有n行和n-l列的一個表。在表中第i行和第j列處填入第i個選手在第j天所遇到的選手。用分治法編寫為該循環(huán)賽設計一張比賽日程表的算法并運行實現(xiàn)、對復雜度進行分析。算法思想：按分治策略，我們可以將所有選手對分為兩組，n個選手的比賽日程表就可以通過為n/2個選手設計的比

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

3、#include#include#includeintdata[32][32];voidtable(intk,intn){inti,j;if(n==2){data[k-1][0]=k;data[k][0]=k+1;}else{table(k,n/2);table(k+n/2,n/2);}for(i=k-1;i

4、){for(j=n/2;j>n;if((n&(n-1))!=0)//在二進制數(shù)中，若2的k次方等于n，則n只有最高位為1，其他位為0，故（n-1）的最高位為0(相對于n來說)，其他位為1，{cout<<"輸入有誤，請重新輸入！"<

5、>>n;cout<<"輸入有誤，請重新輸入！"<