数据结构课程中分治法的基本思想是什么啊

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)…… 任何一个可以用计算机求解的问题所需的计算时间都与其规模 　　有关。问题的规模越小，越容易直接求解，解题所需的计算时间也 　　越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。 　　n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。 　　而当n较大时，问题就不那么容易处理了。要想直接解决一个规模 　　较大的问题，有时是相当困难的。 　　分治法的设计思想是，将一个难以直接解决的大问题，分割成一 　　些规模较小的相同问题，以便各个击破，分而治之。 　　分治策略是：对于一个规模为n的问题，若该问题可以容易地解决 　　（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的 　　子问题，这些子问题互相独立且与原问题形式相同，递归地解这些 　　子问题，然后将各子问题的解合并得到原问题的解。这种算法设计 　　策略叫做分治法。 　　如果原问题可分割成k个子问题，1 　　#include 　　#include 　　#define m 40 　　 　　void partionget(int s,int e,int *meter,int *max,int *min){ 　　 　　int i; 　　if(e-s <= 1){ 　　if(meter[s] > meter[e]){ 　　if(meter[s] > *max) 　　*max = meter[s]; 　　if(meter[e] < *min) 　　*min = meter[e]; 　　} 　　else{ 　　if(meter[e] > *max) 　　*max = meter[s]; 　　if(meter[s] < *min) 　　*min = meter[s]; 　　} 　　return ; 　　} 　　i = s + (e-s)/2; 　　partionget(s,i,meter,max,min); 　　partionget(i+1,e,meter,max,min); 　　} 　　int main(){ 　　int i,meter[m]; 　　int max = int_min; 　　int min = int_max; 　　printf("the array's element as followed:\n\n"); 　　randomize(); 　　for(i = 0; i < m; i ++){ 　　meter = rand()%10000; 　　if(!((i+1)%10)) 　　printf("%-6d\n",meter); 　　else 　　printf("%-6d",meter); 　　} 　　partionget(0,m - 1,meter,&max,&min); 　　printf("\nmax : %d\nmin : %d\n",max,min); 　　system("pause"); 　　return 0; 　　}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息