第八章分治法

第八章分治法null分治法分治法简介简介分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。简介简介这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)…… 分治法在高级语言中主要的一个思想是递归，LIST语言中的体现出了极丰富的分治法。 null任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，...

null分治法分治法简介简介分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。简介简介这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)…… 分治法在高级语言中主要的一个思想是递归，LIST语言中的体现出了极丰富的分治法。 null任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。null例如，对于n个元素的排序问题，当n=1时，不需任何计算。 n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。null分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。null 分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 null如果原问题可分割成k个子问题，1 表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。null因此，当P的规模不超过n0时直接用算法ADHOC(P) 求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。null根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？ null在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取 k = 2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。给定一个顺序表，编写一个求出其最大值和最小值的分治算法。给定一个顺序表，编写一个求出其最大值和最小值的分治算法。由于顺序表的结构没有给出，作为演示分治法这里从简顺序表取一整型数组。数组大小由用户定义，数据随机生成。我们知道如果数组大小为 1 则可以直接给出结果，如果大小为 2则一次比较即可得出结果，于是我们找到求解该问题的子问题即: 数组大小 <= 2。到此我们就可以进行分治运算了，只要求解的问题数组长度比 2 大就继续分治，否则求解子问题的解并更新全局解以下是代码。null#include #include #include #define M 40 null/* 分治法获取最优解 */ void PartionGet(int s,int e,int *meter,int *max,int *min){ /* 参数: * s 当前分治段的开始下标 * e 当前分治段的结束下标 * meter 表的地址 * max 存储当前搜索到的最大值 * min 存储当前搜索到的最小值 */ nullint i; if(e-s <= 1){ /* 获取局部解，并更新全局解 */ if(meter[s] > meter[e]){ if(meter[s] > *max) *max = meter[s]; if(meter[e] < *min) *min = meter[e]; } nullelse{ if(meter[e] > *max) *max = meter[s]; if(meter[s] < *min) *min = meter[s]; } return ; }null i = s + (e-s)/2; /* 不是子问题继续分治,这里使用了二分，也可以是其它 */ PartionGet(s,i,meter,max,min); PartionGet(i+1,e,meter,max,min); }nullint main(){ int i,meter[M]; int max = INT_MIN; /* 用最小值初始化 */ int min = INT_MAX; /* 用最大值初始化 */null printf("The array's element as followed:\n\n"); randomize(); /* 初始化随机数发生器 */ for(i = 0; i < M; i ++){ /* 随机数据填充数组 */ meter[i] = rand()%10000; if(!((i+1)%10)) /* 输出表的随机数据 */ printf("%-6d\n",meter[i]); else printf("%-6d",meter[i]); }nullPartionGet(0,M - 1,meter,&max,&min); /* 分治法获取最值 */ printf("\nMax : %d\nMin : %d\n",max,min); system("pause"); return 0; }

                    本文档为【第八章  分治法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

第八章 分治法

你可能还喜欢

第八章分治法