日程安排"/>
分治算法:乒乓球比赛的日程安排
乒乓球比赛的日程安排
问题:
设有n位选手参赛,初赛进行n-1天,每位选手每天必须比赛一次,不能轮空。编程求解赛程安排。
分析:
1、求n位选手的赛程安排,可采用分治算法的思想,将问题规模不断缩小,比如缩小到8,4,2等规模大小;
2、分析2,4,8等小规模时的赛程安排:
分治算法主要思想:
(1)、若原问题规模大小不便计算,将问题原本规模分解成若干个规模较小的相同问题;
(2)、每个子问题求解相互独立,且与原问题形式相同,递归解这些子问题合并后组成原问题答案;
分治算法适用问题:
(1)、问题可分解成若干个规模较小的相同问题;
(2)、合并子问题的解可以得到原问题的解;
(3)、各个子问题相互独立;
分治算法的主要步骤:
(1)、分解:缩小问题规模;
(2)、求解:足够小的规模可用简单方法求解;
(3)、合并:按照求解问题要求,合并子问题的解,构成最终的解;
代码实现:
#include <iostream>#define max 64int a[max+1][max+1] = {0};void game_cal(int k, int n){if (n == 2){a[k][1] = k;a[k][2] = k + 1;a[k+1][1] = k+1;a[k+1][2] = k;}else{game_cal(k, n/2);game_cal(k+n/2, n/2);for (int i = k; i < k+n/2; ++i){for (int j = n/2+1; j <= n; ++j)a[i][j] = a[i+n/2][j-n/2];}for (int i = k+n/2; i < k+n; ++i){for (int j = n/2+1; j <= n; ++j)a[i][j] = a[i-n/2][j-n/2];}}}int main(){int num;std::cout << "enter the player numbers:" << std::endl;std::cin >> num;game_cal(1, num);std::cout << " n ";for (int i = 1; i < num; ++i)std::cout << i << " ";std::cout <<std::endl;for (int i = 1; i <= num; ++i){for (int j = 1; j <=num; ++j)printf("%2d", a[i][j]);std::cout << std::endl;}return 0;}
答案截图:
缺陷:
只能解决2的整数次幂数据输入;
数据大小限制,不过可以在代码头部,宏定义部分修改;
*****
分治和递归的区别与联系:
递归:函数直接或者间接的调用自身;
递归是分治算法在解决问题时可能用到的方法(当问题规模足够简单时直接计算即可);
更多推荐
分治算法:乒乓球比赛的日程安排
发布评论