算法设计与分析——递归与分治策略——循环日程赛

缺乏、安全感 2022-11-11 05:15 130阅读 0赞

问题描述：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]

非递归方案一：代码

#include<bits/stdc++.h>
    using namespace std;
    
    void gameTable(vector<vector<int>> &vec,int k)
    {
        
    	
    	int i=0,j=0;//二维数组的下标，行，列 
    	int temp;//需要新安排选手数目 
    	int n;//当前的选手数目 
    	
    	//先初始化一个两人的比赛表
    	n=2; //k=1两个参赛选手日程可以直接求得
    	vec[1][1]=1;
    	vec[1][2]=2;
    	vec[2][1]=2;
    	vec[2][2]=1;
    	
    //关键的大循环 
    	for(int x=1;x<k;x++)//安排2^x个选手的日程表 
    	{
        
    		temp=n;//多了temp个选手  已建立了temp个选手的表 
    		n*=2;//目前选手的数量
    		
    		 
    		//安排左下角的比赛日程 
    		for(i=temp+1;i<=n;i++)//左下角的行 
    		{
        
    			for(j=1;j<=temp;j++)//左下角的列 
    				vec[i][j]=vec[i-temp][j]+temp;
    			//同一列的第i-temp行（从上到下依次对应）的值加上新增数temp  
    		}
    		//安排右上角的比赛日程 
    		for(i=1;i<=temp;i++)//右上角的行 
    		{
        
    			for(j=temp+1;j<=n;j++)//右上角的列 
    				vec[i][j]=vec[i+temp][j-temp];
    		}
    		//安排右下角的比赛日程 
    		for(i=temp+1;i<=n;i++)//右下角的行 
    		{
        
    			for(j=temp+1;j<=n;j++)//右下角的列 
    				vec[i][j]=vec[i-temp][j-temp];
    			
    		} 
    	} 
    	
    	
    	cout<<"(第i行第j列表示和第i个选手在第j天比赛的选手序号)"<<endl;
        for(i=1;i<=n;i++)//画表 
        {
        
        	for(j=1;j<=n;j++)
            {
        
                 cout<<setw(3)<<vec[i][j];
            }
            cout<<endl;
    	}
            
    	
    	
    	
    }
    
    int main()
    {
        
    	cout<<"比赛选手个数为n(n=2^k)，请输入参数K(K>0):";
    	int k;
    	cin>>k;
    	int num=1;
    	for(int i=0;i<k;i++)
    	{
        
    		num*=2;
    	}
    	//stl的二维的vector需要初始化后才可以使用 
    	vector<vector<int>> vec(num+1, vector<int>(num+1));
    	gameTable(vec,k);
    	return 0; 
    	
     }

for(int x=1;x<k;x++)//安排2^x个选手的日程表  
//stl的二维的vector需要初始化后才可以使用  
vector<vector> vec(num+1, vector(num+1));  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 2]  
方案二：使用递归来解决

#include<bits/stdc++.h>
    using namespace std;
    
    void Copy(int **a,int cow,int col,int cow2,int col2,int k)
    {
        
    	for(int i=0;i<k;i++)
    	{
        
    		for(int j=0;j<k;j++)
    		{
        
    			a[cow2+i][col2+j]=a[cow+i][col+j];
    		}
    	}
    }
    void table(int **a,int cow,int col,int k)//k为参加比赛的总人数 
    {
        
    	if(k==1)
    		return ;
    	else
    	{
        
    		//填充左上角的比赛进程
    		table(a,cow,col,k/2); 
    		
    		//填充左下角的比赛进程
    		table(a,cow+k/2,col,k/2); 
    		
    		//将左下角的信息复制到右上角的比赛进程
    		Copy(a,cow+k/2,col,cow,col+k/2,k/2);
    		
    		//将左上角的信息复制到右下角的比赛进程 
    		Copy(a,cow,col,cow+k/2,col+k/2,k/2);
    	}
    } 
     
    int main()
    {
        
    	int k;
    	 cout<<"输入k(n=2^k):";
    	 cin>>k;
    	 
    	 int num=1;
    	 for(int i=0;i<k;i++)
    	 {
        
    	 	num=num*2;
    	 }
    	  
    
    	
    	//输入运动员的人数
    
    	int ** p =new int*[num];
    	//赛程表初始化
    	for (int i = 0; i < num; i++)
    	{
        
    		p[i] = new int[num];
    		p[0][i] = i+1;
    		p[i][0] = i+1;
    	}
    	 
    	
    	
    	
    	//运行函数
    	table(p,0,0,num);
    	//输出结果
    	cout<<"循环赛日程表（递归法）:"<<endl;
    	for(int i=0;i<num;i++)
    	{
        
    		for(int j=0;j<num;j++)
    		{
        
    			cout<<setw(3)<<p[i][j];
    		}
    		cout<<endl;
    	}
    	return 0;
    }

动态开辟空间  
int \**p = new int*\[m\]; //开辟行  
for(int i = 0; i < m; i++)  
p\[i\] = new int\[n\]; //开辟列

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221022/a5b804be296b4e22a58cbbd92f1d200f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]: /images/20221022/60f21e7c264c441db675ead3d22d0ea1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210319120708220.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210319125156853.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70