BJFU_计算机算法设计与实践_作业2

曾经终败给现在 2023-02-23 07:44 4阅读 0赞

### 作业2 ###

##### 问题描述 #####

编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：  
（1）每个选手必须与其它n-1个选手各赛一次  
（2）每个选手一天只能赛一场  
（3）循环赛进行n-1天

##### 问题思路 #####

假设n位选手被顺序编号为1、2、…、n（2^k）。可将比赛日程表设计成一个n行n-1列的二维数组，其中第i+1行、第j+1列表示和第i个选手在第j天比赛的选手号。观察可知，数组均分四块后，其左上角等于右下角，左下角等于右上角。只要求出左上角和左下角的解，就能得出其余部分的解。  
故采用分治法，将一个难以直接解决的大问题划分成一些规模较小的相同问题，便于各个击破。在此基础上，我写了3种算法。  
(1)算法1：改写课件代码，采取自底向上的迭代。  
(2)算法2：算法1的改写，采取自顶向下的递归。  
(3)算法3：算法2的改写，仍采用自顶向下递归。

##### 算法1 #####

##### 伪代码描述 #####

1.输入k，总数为2k，a[0][0]=1，t=1
    2.循环直到k为0
    	2.1 for i=0 to i=t					//左上角的宽度为t
    			for j=0 to j=t
    				a[i+t][j+t]=a[i][j];	//填充右下角
    				a[i+t][j]=a[i][j]+t;	//填充右上角
    				a[i][j+t]=a[i][j]+t;	//填充左下角
    	2.2 t=t*2							//新的左上角产生，迭代填充
    	2.3 k--			
    3.输出a

##### 算法时间复杂度分析 #####

T(k)表示2^k个选手循环赛问题的求解时间，T(k)满足如下递推式：  
T(k)=1 k=1  
T(k)=4T(k-1) k>1  
解此递推式可得T(k)=O(4^k)。

##### C++描述 #####

#include<iostream>
    #include<Windows.h>
    #include<iomanip>
    using namespace std;
    void Plan(int a[][256],int k)
    {
           
    	a[0][0]=1;
    	int i,j,t=1;														 
    	while(k--)						//k为迭代次数
    	{
        
    		for(i=0;i<t;i++)			//t表示左上角的a[0][0]到a[t-1][t-1]填充完毕
    		{
        
    			for(j=0;j<t;j++)		//左上角的宽度为t
    			{
        
    				a[i+t][j+t]=a[i][j];	//填充右下角
    				a[i+t][j]=a[i][j]+t;	//填充右上角
    				a[i][j+t]=a[i][j]+t;	//填充左下角
    			}
    		}
    		t=t*2;					//新的左上角产生，接着填充
    	}
    	cout<<"算法1"<<endl;
    	for(i=0;i<t;i++)				//t为总人数，输出数组a
    	{
         
    		for(j=0;j<t;j++)
    		{
        
    			cout<<setiosflags(ios::left)<<setw(3)<<a[i][j];
    		}
    		cout<<endl;
    	}
    }
    int main()
    {
        
    	int k,a[256][256];
    	while(cin>>k&&k>0)
    	{
        
    		//准备计时
    		LARGE_INTEGER m_liPerfFreq;
    		QueryPerformanceFrequency(&m_liPerfFreq);
    		LARGE_INTEGER m_liPerfStart;
    		QueryPerformanceCounter(&m_liPerfStart);
    		//开始计时
    		Plan(a,k);
    		//结束计时
    		LARGE_INTEGER liPerfEnd;
    		QueryPerformanceCounter(&liPerfEnd);
    double Time=(double)(liPerfEnd.QuadPart-m_liPerfStart.QuadPart)/(double)m_liPerfFreq.QuadPart;
    	cout<<"耗时："<<setiosflags(ios::fixed)<<setprecision(1)<<Time*1000000<<"毫秒"<<endl;
    	}
        return 0;
    }

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

##### 算法2 #####

##### 伪代码描述 #####

1. 输入k，总数为2k，a[0][0]=1
    2. Table(a,n)    				
    	2.1 If n=1  Return			//递归结束
    	2.2 Table(a,n/2);           //填充左上角
    	2.3 Copy(a,n);				//填充左下角、右上角、右下角
    3. Copy(a,n)					//复制函数
    	3.1 for(int i=0;i<n/2;i++)              
    			for(int j=0;j<n/2;j++)
    				a[i+n/2][j]=a[i][j]+n/2;  	//填充左下角            
    				a[i][j+n/2]=a[i][j]+n/2;  	//填充右上角    
    				a[i+n/2][j+n/2]=a[i][j];  	//填充右下角 
    4.输出a

##### 算法时间复杂度分析 #####

算法2是将算法1的迭代改写成了递归，依旧是T(k)=4T(k-1)，由递推式计算出T(k)=O(4^k)，时间复杂度和算法1相同。

##### C++描述 #####

#include<iostream>
    #include<Windows.h>
    #include<iomanip>
    using namespace std;
    void Copy(int a[][256],int n)
    {
        
        for(int i=0;i<n/2;i++)              
        {
        
            for(int j=0;j<n/2;j++)
            {
        
                a[i+n/2][j]=a[i][j]+n/2;   	//填充左下角 
                a[i][j+n/2]=a[i][j]+n/2;    //填充右上角    
                a[i+n/2][j+n/2]=a[i][j];    //填充右下角 
            }
    	}
    }
    void Table(int a[][256],int n)  
    {
        
        if(n==1)
    	{
        
    		a[0][0]=1;
            return;
        }
    	Table(a,n/2);                 	 	//填充左上角
        Copy(a,n);							//填充左下角、右上角、右下角
    }
    void Print(int a[][256],int n)			//输出数组
    {
        
        for(int i=0;i<n;i++)
        {
        
            for(int j=0;j<n;j++)
            {
        
                cout<<setiosflags(ios::left)<<setw(3)<<a[i][j];
            }
            cout<<endl;
        }
    }
    int main()
    {
        
        int a[256][256],k;    
        while(cin>>k&&k>0)
        {
        
    	    //准备计时
         	LARGE_INTEGER m_liPerfFreq;
            QueryPerformanceFrequency(&m_liPerfFreq);
            LARGE_INTEGER m_liPerfStart;
            QueryPerformanceCounter(&m_liPerfStart);
            //开始计时
    		int n=1;
    		for(int i=0;i<k;i++)			//计算选手总数
    		{
        
    			n=n*2;
    		}
    		Table(a,n);
            Print(a,n);
    		//结束计时
            LARGE_INTEGER liPerfEnd;
            QueryPerformanceCounter(&liPerfEnd);
            double Time=(double)(liPerfEnd.QuadPart-m_liPerfStart.QuadPart)/(double)m_liPerfFreq.QuadPart;
            cout<<"耗时："<<setiosflags(ios::fixed)<<setprecision(1)<<Time*1000000<<"毫秒"<<endl;
        }
        return 0;    
    }

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

##### 算法3 #####

##### 伪代码描述 #####

1.输入k，总数为2k，a[0][0]=1
    2.Table(a, n,k) 
       2.1 if n=1  return;			//递归结束
       2.2 Table(a,n/2,k);      	//求解前n/2个选手 
       2.3 Table(a,n/2,k+n/2);    	//求解后n/2个选手
       2.4 Copy(a,n,k);      		//合并子问题解
    3. Copy(a,n,k) 					//合并子问题解
       3.1 for(int i=k;i<k+n/2;i++)      
       			for(int j=0;j<n/2;j++)
    				a[i+n/2][j+n/2]=a[i][j]; 	//填充右下角
    				a[i][j+n/2]=a[i+n/2][j]; 	//填充右上角 
    4.输出a

##### 算法时间复杂度分析 #####

T(n)表示2^k个选手循环赛问题的求解时间，T(k)满足如下递推式：  
T(n)=1 n=1  
T(n)=2T(n/2)+1/2\*n2 n>1  
由递推式可得，T(k)=O(n2)=O(4^k)，即时间复杂度和算法1、2相同。

##### C++描述 #####

#include<iostream>
    #include<Windows.h>
    #include<iomanip>
    using namespace std;
    void Copy(int a[][256],int n,int k) 	//合并子问题结果
    {
        
        for(int i=k;i<k+n/2;i++)      
        {
        
            for(int j=0;j<n/2;j++)
            {
        
                a[i+n/2][j+n/2]=a[i][j]; 	//左上粘贴到右下
                a[i][j+n/2]=a[i+n/2][j]; 	//左下粘贴到右上 
            }
    	}
    }
    void Table(int a[][256],int n,int k) 
    {
        
        if(n==1)               		//递归结束
        {
        
            return;
        }
        Table(a,n/2,k);      			//求解前n/2个选手，首元素是a[k][0] 
        Table(a,n/2,k+n/2);    			//求解后n/2个选手，首元素是a[k+n/2][0]
        Copy(a,n,k);      			//合并两个子问题的解
    }
    void Print(int a[][256],int n)
    {
        
    	cout<<"算法3"<<endl;
        int i,j;
        for(i=0;i<n;i++)
        {
        
            for(j=0;j<n;j++)
            {
        
            	cout<<setiosflags(ios::left)<<setw(3)<<a[i][j];
            }
            cout<<endl;
        }
    }
    int main()
    {
        
        int i,k;
        int a[256][256]; 
        while(cin>>k&&k>0)   					   
     	{
        
    		//准备计时
            LARGE_INTEGER m_liPerfFreq;
            QueryPerformanceFrequency(&m_liPerfFreq);
            LARGE_INTEGER m_liPerfStart;
            QueryPerformanceCounter(&m_liPerfStart);
            //开始计时
    		int n=1;
    		for(i=0;i<k;i++)				
            {
        
                n=n*2;					//n为总数
            }
            for(i=0;i<n;i++)				
          	{
        
          		a[i][0]=i+1;				//标注选手序号
            }
            Table(a,n,0);     				//求解前n个选手，首元素是a[0][0] 
            Print(a,n);
            //结束计时
            LARGE_INTEGER liPerfEnd;
            QueryPerformanceCounter(&liPerfEnd);
            double Time=(double)(liPerfEnd.QuadPart-m_liPerfStart.QuadPart)/(double)m_liPerfFreq.QuadPart;
            cout<<"耗时："<<setiosflags(ios::fixed)<<setprecision(1)<<Time*1000000<<"毫秒"<<endl;
        }
        return 0; 
    }

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

##### 总结 #####

算法1耗时最短，算法3耗时最长。我思考这是由“算法1迭代，算法2、3递归”导致的。算法1是课件代码的简化，可读性更强。算法2则是将算法1的迭代转化成递归。而算法3与2的区别，在于算法3的左下角与左上角分别递归求解。

迭代和递归是解决问题的两种方法，可以互相转化。迭代是循环重复执行同一步骤，采用的是自底向上实现。可读性较差，循环边界容易错。递归是指函数内部调用自身，采用的是自顶向下实现。逻辑清晰，代码简洁，可读性强，但每次调用时需传递参数和保存地址，影响程序执行效率，递归太多次有栈溢出的危险。  
综合比较，我倾向于算法2，比算法1可读性更强，比算法3代码更简洁。通过作业三，我加深了分治思想，学会用递推式求时间复杂度，并理解了递归与迭代的区别与联系。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020070521310894.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200705213713786.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200705220733893.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyMjgyNw==,size_16,color_FFFFFF,t_70