1.題目
設(shè)有n=2^k個(gè)運(yùn)動員要進(jìn)行網(wǎng)球循環(huán)賽?，F(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：
(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；
(2)每個(gè)選手一天只能參賽一次；
(3)循環(huán)賽在n-1天內(nèi)結(jié)束
2.問題分析
按分治策略，將所有的選手分為兩半，
n個(gè)選手的比賽日程表就可以通過為
n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。
遞歸地用對選手進(jìn)行分割，直到只剩下1個(gè)選手時(shí)，比賽日程表則不再安排
3.什么是分治
分治的核心思想就是：遞歸（分解）+ 合并：
遞歸分解：將原問題(大問題)分解成和原問題相似的子問題(小問題)。遞歸分解首先需要明確的就是遞歸函數(shù)的定義（一般和題目給出的函數(shù)類似）是什么，先不用管此時(shí)函數(shù)的內(nèi)部是怎么實(shí)現(xiàn)的，明白函數(shù)的定義也就知道了我們需要給函數(shù)傳遞的參數(shù)是什么，而這個(gè)參數(shù)一般就是我們將原問題劃分為子問題的依據(jù)。拿后面要講解的歸并排序和LeetCode 395.至少有K個(gè)重復(fù)字符的最長子串來舉例：對于歸并排序，假設(shè)我們有待排序序列：[a, b , c, d, e, f]，很自然就能想到需要定義一個(gè)能夠?qū)θ我忾L度的待排序序列進(jìn)行排序的函數(shù)，此時(shí)的參數(shù)就是任意長度的待排序序列，因此將原問題分解就可以通過將待排序序列不斷分解為更短的子序列；同樣對于至少有K個(gè)重復(fù)字符的最長子串來說，我們需要求出某個(gè)字符串中至少包含K個(gè)重復(fù)字符的最長子串，我們就可以定義遞歸函數(shù)來做這個(gè)事情，于是就有參數(shù)任意長度的字符串，所以我們分解原問題也就是將字符串分解不同的子串。
合并：遞歸函數(shù)會對每個(gè)子問題求解出一個(gè)子解，合并就是將各個(gè)子問題的答案進(jìn)行合并，求出原問題的答案，注意合并的形式可能是對各子問題的子解求最大值/最小值，也可能是將各子解合并在一起，需要根據(jù)具體題目進(jìn)行分析。
分治算法所能解決的問題一般具有以下幾個(gè)特征：
⑴原問題的規(guī)?？s小到一定的程度就可以很容易地解決
⑵原問題可以分解為若干個(gè)規(guī)模較小的相同問題，即原問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)
⑶利用原問題分解出的子問題的解可以合并為原問題的解
⑷原問題分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題（這條特征涉及到分治法的效率，如果各個(gè)子問題不獨(dú)立，也就是子問題劃分有重合部分，則分治法要重復(fù)的求解1公共子問題的解，此時(shí)雖然也可用分治法，但采用動態(tài)規(guī)劃更好）
4.算法實(shí)現(xiàn)思路
1.對表進(jìn)行分析
2.對表的實(shí)現(xiàn)
1.遞歸
2.循環(huán)
5算法實(shí)現(xiàn)代碼
1.遞歸
#include<iostream>
#include<cmath>
using namespace std;
int a[100][100];
void table(int k, int d)
// 邊長 步長
{
if (k == d)
return;
int i, j;
for (i = 0; i < d; i++)
{
for (j = 0; j < d; j++)
{
a[i + d][j + d] = a[i][j];
a[i][j + d] = a[i][j] + d;
a[i + d][j] = a[i][j] + d;
}
}
table(k, d * 2);
}
int main()
{
//輸入人數(shù)
int n;
cout << "學(xué)生人數(shù)k=2^n,請輸入k:";
int k;
cin >> n;
k = pow(2, n);
//判斷只有一個(gè)人時(shí)
if (k == 1)
a[0][0] = 0;
else
a[0][0] = 1;
//遞歸
table(k, 1);
//輸出
for (int i = 0; i < k; i++)
{
for (int j = 0; j < k; j++)
{
cout << a[i][j]<<' ';
}
cout << endl;
}
}
2.循環(huán)
#include<iostream>
#include<cmath>
#define N 50
using namespace std;
int a[N][N];
void Table(int k);
void print(int k);
int main()
{
int k;
cout << "\t\t****************************************\n";
cout << "\t\t**\t\t循環(huán)賽日程表 **\n";
cout << "\t\t****************************************\n\n";
cout << "設(shè)參賽選手的人數(shù)為n（n=2^k），請輸入k 的值：";
do
{
cin >> k;
if (k != 0)
{
Table(k);
print(k);
}
else
cout << "您輸入的數(shù)據(jù)有誤，請重新輸入！" << endl;
} while (k != 0);
}
void Table(int k)
{
int n = 1;//數(shù)組下標(biāo)從1開始
for (int i = 1; i <= k; i++)
n *= 2;//求總?cè)藬?shù)
for (int i = 1; i <= n; i++)
a[1][i] = i;//初始化，第一行等于1--8
int m = 1;//填充起始位置(用來控制每一次填表時(shí)i行j列的起始填充位置）
for (int s = 1; s <= k; s++)//總共循環(huán)k次（s指對稱賦值的總循環(huán)次數(shù)，即分成幾大步進(jìn)行制作日程表）
{
n = n / 2;
for (int t = 1; t <= n; t++)//分的塊數(shù)（t指明內(nèi)部對稱賦值的循環(huán)次數(shù)）
{
for (int i = m + 1; i <= 2 * m; i++)
for (int j = m + 1; j <= 2 * m; j++)
{
a[i][j + (t - 1) * m * 2] = a[i - m][j + (t - 1) * m * 2 - m];//右上角=左下角
a[i][j + (t - 1) * m * 2 - m] = a[i - m][j + (t - 1) * m * 2];//右下角=左上角
}
}
m *= 2;//更新填充起始位置
}
}
void print(int k)
{
int i, j;
int n = pow(2, k);
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
cout << a[i][j] << ' ';
}
cout << "\n";
}
}
6.時(shí)間\空間復(fù)雜度
1.遞歸
1.空間復(fù)雜度
運(yùn)行算法時(shí)，所用的數(shù)組是全局變量，所用空間不隨著某個(gè) 變量的改變而變化，是一個(gè)常數(shù)，所以空間復(fù)雜度為O(1)文章來源：http://www.zghlxwxcb.cn/news/detail-418677.html
2.時(shí)間復(fù)雜度
（2）時(shí)間復(fù)雜度:
n=2^k
遞歸: 先打印21矩陣，然后遞歸打印22矩陣,遞歸k次
打印時(shí)劃分成四個(gè)區(qū)域，左上角區(qū)域是已完成區(qū)域（d^2）
F=O(12+22+42+……(2(n-1))^2)
F=O(20+22+24+26+……+2^(2n-2))
所以時(shí)間復(fù)雜度是O(2(2k))=O(n2)
2.循環(huán)
1.空間復(fù)雜度
運(yùn)行算法時(shí)，所用的數(shù)組是全局變量，所用空間不隨著某個(gè) 變量的改變而變化，是一個(gè)常數(shù)，所以空間復(fù)雜度為O(1)
2.時(shí)間復(fù)雜度
總?cè)藬?shù)：n=2^k k:輸入值
分治:先打印一行，然后分成n/2份，然后進(jìn)行填充，接著分成n/4份，以此類推(2(k-1)+……20)，然后填充每一小塊 m^2，F(xiàn)=O( ((2(k-1))*(12) + (2(k-2))(22) +……+ (20)*(2（k-1）)2))，所以時(shí)間復(fù)雜度是O(2(2k))=O(n^2)文章來源地址http://www.zghlxwxcb.cn/news/detail-418677.html
到了這里，關(guān)于循環(huán)賽日程表 （遞歸與分治）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
