iis怎么做IP网站,有永久免费的域名吗知乎,潜江资讯网一手机版,做那个的网站一、算法思路1、思路分治算法的思想是#xff1a;对于一个规模位N的问题#xff0c;若该问题可以容易解决(比如规模N较小)#xff0c;则直接解决#xff0c;否则将其分解为M个规模较小的子问题#xff0c;这些子问题互相独立#xff0c;并且与原问题形式相同#xff0c;…一、算法思路1、思路 分治算法的思想是对于一个规模位N的问题若该问题可以容易解决(比如规模N较小)则直接解决否则将其分解为M个规模较小的子问题这些子问题互相独立并且与原问题形式相同递归的解决这些子问题然后将各子问题的解合并得到原问题的解2、分治法适用范围一般具有以下特征的问题可以使用分治算法求解(1)求解问题可以分解为若干个规模较小的相同问题(2)求解问题的规模分解到一定程度就能够很容易地求解(3)合并子问题的解可以得到问题的解(4)由求解问题所分解的各个子问题是互相独立的3、分治法的步骤(1)分解将要求解的问题划分为规模较小的同类问题(2)求解当子问题划分的足够小的时候用比较简单的方法求解得到子问题的解(3)合并按求解问题的要求将子问题的解逐层合并即可构成最终的解二、分治法实例比赛日程的安排1、问题描述 某学校举行乒乓球比赛在初赛阶段设置为循环赛设有n位选手参赛初赛共进行n-1天每位选手要与其他每一位选手进行一场比赛然后按积分排名选拔进入决赛的选手。根据学校作息时间要求每位选手每天必须比赛一场不能轮空。按此要求为比赛安排具体日程即决定每天各选手对阵的对手2、分析设有n2^k个选手参加循环赛那么需要要求设计一个满足以下要求比赛日程表1)每个选手必须与其它n-1个选手各赛一次2)每个选手一天只能赛一次3、图解(1)2个选手的情况如果只有两个选手那么第0列看作选手编号(我们从0开始对列编号我们的第0列可以看作每个选手第0天在和自己打)第1列就是在第一天每个选手要比赛的选手号(2)如果选手的个数为2^24那么日程安排如下图如果有4个选手分别设计4/22个选手的比赛日程表1-2选手前一天的比赛日程表如上图表格左上角的深蓝色子表格部分3-4选手前一天的比赛日程表如上图表格左下角的子表格。据此后两天的日程表可以将左上角的子表按其对应位置抄到右下角的子表左下角的子表可以按其对应位置抄到右上角的子表。(同时我们注意到这是表的行列均为参赛选手数2^2 4在用分治法求行、列均为(2^2)/2的长度的子表时首先确定左上角的子表左下角的子表可以由左上角的子表加(2^2)/2得到)(3)如果选手的个数为2^38那么日程安排表如下选手人数为8时左上角的子表是选手1至选手4的前三天的比赛日程左下角是选手5至选手8前三天的比赛日程。据此后四天的比赛日程就是分别将左上角子表按其对应位置抄到右下角将左下角的子表按其对应位置抄到右上角。这样就完成了比赛日程的安排这种解法是把求解2^k个选手的比赛日程问题划分为2^1,2^2......2^k个选手的比赛日程问题。也就是说要求2^k个选手的比赛日程就要分为两部分分别求出2^(k-1)个选手的比赛日程然后再进行合并。当然这种解法只能求选手个数是2的次幂的情况在每次迭代求解的过程中可以看作4部分1)求左上角子表左上角子表是前2^(k-1)个选手的比赛前半程的比赛日程。2)求左下角子表左下角子表是剩余的2^(k-1)个选手的比赛前半程比赛日程。这个子表和左上角子表的对应关系是对应元素等于左上角子表对应元素加2^(k-1)。3)求右上角子表等于左下角子表的对应元素4)求右下角子表等于左上角子表的对应元素代码实现如下#include #include int main(void){ int a[9][9]; int x,y,i,j,t; for(x0;x9;x){ for(y0;y9;y){ a[x][y]0; } } int n2; a[1][1]1; a[1][2]2; a[2][1]2; a[2][2]1;for(t1;t3;t){ /*使用分治法填充日程表*/ int tempn; nn*2; /*扩展左下角*/ for(itemp1;in;i) for(j1;jtemp;j) a[i][j]a[i-temp][j]temp; /*扩展右上角*/ for(i1;itemp;i) for(jtemp1;jn;j) a[i][j]a[i][j-temp]temp; /*扩展右下角*/ for(itemp1;in;i){ for(jtemp1;jn;j) a[i][j]a[i-temp][j-temp]; } }//打印结果for(i0;i9;i){ for(j0;j9;j){ printf(%d ,a[i][j]); } printf();}return 0;}
