使用分治算法设计程序时,一般可以按以下步骤进行:
(1)分解:将要求的问题划分成若干规模较小的同类问题;
(2)求解:当子问题划分的足够小时,用较简单的方法解决;
(3)合并:按求解问题的要求,将子问题的解逐层合并,即可构成最终的解.
实例:乒乓球比赛赛程安排
根据分治算法的思想,我们应该将问题进行拆分成规模较小的同类问题.
循环赛日程4人
循环赛日程2人
循环赛日程4人
这样就可以通过解决小规模的问题来一步步实现整体
Java代码描述:
public class Test { static int[][] is = null; static int m = 0; static{ System.out.println("请输入参赛选手人数:"); Scanner sc = new Scanner(System.in); m = sc.nextInt(); is = new int[m+1][m+1]; } public static void main(String[] args) { int i,j; j = 2; for(i=2;i<8;i++){ j=j*2; if(j==m){ break; } } if(i>=8){ System.out.println("参赛选手人数必须为2的整数次幂,且不超过64!"); return; } gamecal(1, m); System.out.print("NUM\t"); for(i=2;i<=m;i++){ System.out.print("第"+(i-1)+"天 \t"); } System.out.println(); for(i = 1;i<=m;i++){ for(j=1;j<=m;j++){ System.out.print(is[i][j]+"\t"); } System.out.println(); } } public static void gamecal(int k,int n){ int i = 0 ,j = 0; if(n==2){ is[k][1] = k; //参赛选手编号 is[k][2] = k+1; //对阵选手编号 is[k+1][1] = k+1; //参赛选手编号 is[k+1][2] = k; //对阵选手编号 }else{ gamecal(k,n/2); gamecal(k+n/2,n/2); for(i=k;i<k+n/2;i++){ //填充右上角 for(j=n/2+1;j<=n;j++){ is[i][j] = is[i+n/2][j-n/2]; } } for(i=k+n/2;i<k+n;i++){ //填充左下角 for(j=n/2+1;j<=n;j++){ is[i][j] = is[i-n/2][j-n/2]; } } } } }
运行结果:
相关推荐
学 习a c m 分 治算法 的入门 教程简单易学acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法vacm分治算法acm...
动态规划,分治算法,概率算法,模拟退火算法,搜索算法,贪婪算法,网上matlab,遗传算法,组合算法.
分治算法求n个数的数组中找出第二个最大元素
赛程问题分治算法.pdf赛程问题分治算法.pdf赛程问题分治算法.pdf赛程问题分治算法.pdf赛程问题分治算法.pdf赛程问题分治算法.pdf赛程问题分治算法.pdf
分治算法是计算科学的一个经典算法,主要也是用了递归
分治算法的具体代码实现,能实现较好的排序效率
贪心算法、分治算法和动态规划的区别 贪心算法和动态规划.pdf
芯片测试:蛮力测试和分治策略都有写到,算法按设计与分析课的笔记,博主自己写的,仅仅参考了讲义的伪代码,若有错误请指出,谢谢。 重要的假设:好芯片至少比坏芯片多一片。 测试结果:奇数个芯片√ 偶数个芯片...
从键盘输入一组整数,通过分治算法求第二大的数
平面最近点对问题分治算法解答,C++实现,代码整洁规范。
分治算法在循环赛赛程分配中的应用算法设计与分析 分治算法 循环赛事
求整数数组内元素和的分治算法,用c++语言实现
分治算法教案 - 分治策略.ppt
分治算法分治算法分治算法分治算法分治算法
主要介绍了Java基于分治算法实现的棋盘覆盖问题,简单描述了棋盘覆盖问题,并结合具体实例形式分析了java基于分治算法实现棋盘覆盖问题的相关操作技巧,需要的朋友可以参考下
第K小数,快速幂,下载之后负责答疑哦 int cmp(int x,int y) { return x; } void Swap() { swap(a[i],a[j]); swap(i,j); } void Operation(int START,int END) { i=START; j=END; while(i!...}
快速排序,使用分治算法,绝对AC,使用C++算法,没有使用sort,时间复杂度O(n logn)
该课件讲述了分治算法的基本思想,并利用分治思想完成了对数组的排序,快速排序,数组选top k问题,讲解相邻点对的解决方案。
简要介绍了分治算法的实现和应用场景,原理和相关的背景
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。