递归与分治策略算法之循环赛日程表

我不是女神ヾ 2022-12-05 12:19 170阅读 0赞

## 递归与分治策略算法之循环赛日程表 ##

**1、先简单的来介绍一下分治策略的思想**

分治策略的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，分解出来的子问题与原问题相同，并且相互独立。通过递归去解决子问题，然后将子问题的解合并得到原问题的解。

--------------------

**2、循环赛日程表问题的介绍**  
假设有n= 2 k 2^k 2k个运动员要进行网球循环赛，现在要设计一个比赛日程表满足如下要求：

*  每个选手必须与其他n-1个选手都比赛一次；
 *  每个选手一天只能比赛一次；
 *  循环赛一共进行n-1天；

我们可以用一个n\*（n-1）的表来表示比赛的日程表。比赛日程表的第i行和j列的值表示第i个选手在第j天所遇到的选手。

按照分治的策略，将所有选手对分为两半，n个选手的比赛日程表就可以通过n/2个选手的比赛日程来决定。直到剩下两个选手时，直接让这两个选手直接比赛即可。

如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]

--------------------

**3、循环赛日程表问题的具体实现**

实现思路：

*  当只剩下两个选手( 2 1 2^1 21)时，直接让两个选手比赛；
 *  依次处理 2 2 2^2 22、 2 3 2^3 23… 2 k 2^k 2k个选手的比赛日程；  
    \-比赛日程表的左上角和右下角元素相同，左下角和右上角元素相同；  
    \-比赛日程表的左上角和左下角对应元素的差值为**n/2**；

通过如上思路，即可将比赛日程表依次按位置填充。

具体实现：

#include <stdio.h>
    #include <stdlib.h>
    
    //生成赛事表，参数是赛事表arr[][]，运动员人数n=2^k
    void Table(int arr[][9], int n)//数组下标从1开始
    {
        
    	//两个选手时，直接比赛，得到左上角元素(左上角元素手动初始化)
    	arr[1][1] = 1;
    	arr[1][2] = 2;
    	arr[2][1] = 2;
    	arr[2][2] = 1;
    
    	int i, j, half;
    
    	// 循环处理，依次处理 2^2 ... 2^k 个选手比赛日程
    	int num = 2;//当前选手数num
    	while (num < n)
    	{
        
    		half = num;//当前选手的一半
    		num = num * 2;//当前选手数(第一次循环4个选手)
    
    		//处理右下角
    		for (i = half + 1; i <= num; i++)//行
    			for (j = half + 1; j <= num; j++)//列
    				arr[i][j] = arr[i - half][j - half];
    
    		//处理左下角
    		for (i = half + 1; i <= num; i++)
    			for (j = 1; j <= half; j++)
    				arr[i][j] = arr[i - half][j] + half;//这里第一次循环变成3,4号选手
    
    		//处理右上角
    		for (i = 0; i <= half; i++)
    			for (j = half + 1; j <= num; j++)
    				arr[i][j] = arr[i + half][j - half];
    
    	}
    
    }
    
    int main()
    {
        
    	int arr[9][9];
    	Table(arr, 8);
    	for (int i = 1; i <= 8; i++) 
    	{
        
    		for (int j = 1; j <= 8; j++)
    		{
        
    			if(j==1)
    				printf("%d号  ", arr[i][j]);
    			else
    				printf("%d  ", arr[i][j]);
    		}
    		printf("\n");
    	}
    
    	return 0;
    }

实现结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 1]

--------------------

tips：行动不一定带来快乐，而无行动则决无快乐。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/db14bbaf7bad4c6f86317c8165c22172.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/14399b22a02e4223a923fa59be6ee2d5.png