1. 重蔚自留地首页
  2. 科技动态

程序员都会的五大算法之——分治算法，恶补

语音刺客 • • 科技动态 • 阅读 85

一、算法概述

分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。

二、分治策略的基本思想

简单来说，分治算法就是“分而治之”，即就是讲一个规模很大很复杂的问题分 成若干份相同或相似的更小的子问题，直到最后可以简单的直接求解，将所有子问题的解合并即得到原问题的解。

此处，需要注意：

子问题与原问题的性质相同子问题必须可以独立求解递归停止时，子问题必须能够直接求解

三、时间复杂性

在分治算法中，假设原问题总规模为n，我们假设分解和合并所用时间为C(n)和D(n),假设W(x)为处理一个规模为x的问题所用的时间。每一个子问题是原问题规模的1/a。

如果原问题规模<=最小子问题的规模，既可以直接求解，那么其时间复杂度是一个常数。否则，W(n)=aW(n/a)+C(n)+D(n);

四、分治精髓

分治法的精髓：

分--将问题分解为规模更小的子问题；治--将这些规模更小的子问题逐个击破；合--将已解决的子问题合并，最终得出“母”问题的解；

五、经典例子：

二分归并排序汉诺塔

5.1 二分归并排序

设计思想：

1、将规模为n的原问题划分为规模为n/2的子问题； 2、继续划分，划分至规模为n/4的，继续一直到规模为1，可以直接求解，这块分治就结束了； 3、从规模1到n/2依次陆续归并排好序的子数组，直到原始数组。

伪代（pseudocode）：

算法 MergeSort(A, p, r)

输入： 数组A[p......r]

输出：元素按从小到大排序的数组A

 1.if p < r
 2.then q <- (p+r)/2     问题规模划分
 3.MergeSort(A, p, q)    子问题1
 4.MergeSort(A, q+1, r)  子问题2
 5.Merge(A, p, q, r)     综合解

程序代码实现（Java实现）：

 public static void mergeSort(int[] nums, int begin, int end){
     int length = end - begin + 1;
     if(length <= 1){
         return;
     }
     /*分*/
     int mid = (begin + end) / 2;
     mergeSort(nums, begin, mid);
     mergeSort(nums, mid+1, end);
     /*治*/
     merge(nums, begin, mid, end);
 }
 public static void merge(int[] nums, int begin, int mid, inr end){
     if(mid>=end){
         return;
     }
     int length = end - begin + 1;
     int [] temp = new int[length];
     int k = 0;
     int i = begin;
     int j = mid + 1;
     while(i<=mid&&j<=end){
         if(num[i]<num[j]){
             temp[k] = num[i];
             i++;
         }else{
             temp[k] = num[j];
             j++;
         }
         k++;
     }
     /*传进来前部分已经排完序*/
     if(i>mid){
         while(j<=end){
             temp[k] = nums[j];
             j++;
             k++;
         }
     }
     if(j>end){
         while(i<=mid){
             temp[k] = num [i];
             i++;
             k++
         }
     }
     /*重新存进原数组*/
     for(int m = 0; m < length; m++){
         num[begin+m] = temp[m];
     }
     
 }

图解：

程序员都会的五大算法之——分治算法，恶补

时间复杂度分析：

假设原问题规模为n，二分归并排序最坏情况： W(n)=2W(n/2)+n-1 其中子问题最小规模为1，W(1)=1;

W(n)=nlogn - n + 1 时间复杂度为O(nlogn)

5.2 汉诺塔

游戏介绍：

在汉诺塔游戏中，有三个塔座：A、B、C。几个大小各不相同，从小到大一次编号的圆盘，每个圆盘中间有一个小孔。最初，所有的圆盘都在A塔座上，其中最大的圆盘在最下面，然后是第二大，以此类推.

程序员都会的五大算法之——分治算法，恶补

汉诺塔示意

该游戏的目的是将所有的圆盘从A塔移到B塔;C塔用来放置临时圆盘,游戏的规则如下:

一次只能移动一个圆盘任何时候都不能将一个较大的圆盘压在较小的圆盘上面.除了第二条限制,任何塔座的最上面的圆盘都可以移动到其他塔座上.

设计思想：始终将较小的盘当做是一个整体

游戏完成过程：

在上述图中：我们将盘子由小到大分别记为1，2，3，4，5。

先将1挪到B，2挪到C，再将1从B挪到C，此时A上有3，4，5，B为空，C上有1，2。

再将3挪到B，C上的1也挪到A，C上的2挪到B，A上的1再挪到B，此时A上有45，B上有123，C为空

再将4挪到C，B上的1挪到A，B上的2移到C上，A上的1挪到C上，B上的3挪到A上，C上面的1挪到B上, 有1234

最后将

伪码（pesudocode）：

算法Hanoi(A,C,n) // n个盘子从A到C

 1.if n = 1 then move(A, C)
 2.else Hanoi(A, B, n-1)
 3.move(A, C)
 4.Hanoi(B,C,n-1) 设n个盘子的移动次数为T(n)
     T(n) = 2T(n-1) + 1
     T(1) = 1

程序：

 public static void solve(int n){
     hanoi(n, "A", "B", "C");
 }
 private static void hanoi(int n ,String a, String b,String c){
     if(n==1){
         move(n,a,c);
     } else {
         hanoi(n-1, a, c, b); // 将前n-1个圆盘从a挪到c，借助b
         move(n, a, c);       // 将第n个直接移到c
         hanoi(n-1, b, a, c); // 将前n-1个圆盘从b挪到c，借助啊
     }
 }
 private static void move(int n, String i, String j){
     Systtem.out.println("第"+n+"个盘，从"+ i + "塔移动到" + j + "塔");
 }

时间复杂度分析：

hanoi塔游戏的递推公式为T（n）=2T（n-1)+1，时间复杂度为O(2^n)

六、分治法联系（C语言）

6.1 求一组数据中最大的两个数和最小的两个数

输入输出实例：

 10 代表10个数
 1
 3
 5
 7
 9
 10
 8
 6
 4
 2
 max1=10 max2=9
 min1=1 min2=2

代码实现：

 #include <stdio.h>
 void maxtwo(int[], int, int, int*, int*);
 void mintwo(int[], int, int, int*, int*);
 int main()
 {
     int num,i;
     scanf("%d",&num);
     int a[num];
     for(i=0;i<num;i++)
         scanf("%d",&a[i]);
     
     /**********  Begin  **********/
     int max1, max2, min1, min2;
     maxtwo(a, 0, num-1, &max1, &max2);
     printf("max1=%d max2=%d\\n",max1,max2);
     mintwo(a, 0, num-1, &min1, &min2);
     printf("min1=%d min2=%d\\n",min1,min2);
             
     /**********  End  **********/
 }
 void maxtwo(int a[], int i,int j,int *max1,int *max2){ 
     int lmax1,lmax2,rmax1,rmax2;
     int mid;
     if(i==j){
         *max1=a[i];
         *max2=a[i];
     }else if (i==j-2){
         if (a[i]>=a[i+1]&&a[i+1]>=a[i+2]){
             *max1=a[i]; 
             *max2=a[i+1];
         }else if (a[i]>=a[i+2]&&a[i+2]>=a[i+1]){
             *max1=a[i]; 
             *max2=a[i+2];
         }else if (a[i+1]>=a[i]&&a[i]>=a[i+2]){
             *max1=a[i+1]; 
             *max2=a[i];
         }else if (a[i+1]>=a[i+2]&&a[i+2]>=a[i]){
             *max1=a[i+1]; 
             *max2=a[i+2];
         }else if (a[i+2]>=a[i]&&a[i]>=a[i+1]){
             *max1=a[i+2]; 
             *max2=a[i];
         }else{
             *max1=a[i+2]; 
             *max2=a[i+1];
             } 
     }else{
         mid=(i+j)/2;
         maxtwo(a, i,mid,&lmax1,&lmax2);
         maxtwo(a, mid+1,j,&rmax1,&rmax2);
         if(lmax1>=rmax1){ 
             *max1=lmax1;
             if (lmax2>=rmax2){
                 *max2=lmax2;
             }else{
                 *max2=rmax1;
             }
         }else{
             *max1=rmax1;
             if (rmax2>=lmax2){
                 *max2=rmax2;    
             }else {
                 *max2=lmax1;    
             }       
         }
     } 
 } 
 
 void mintwo(int a[], int i, int j, int *min1, int *min2){
     int lmin1, lmin2, rmin1, rmin2;
     int mid;
     if(i == j){
         *min1 = a[i];
         *min2 = a[i];
     }
     else if(i == j - 2){
         if(a[i]<=a[i+1]&&a[i+1]<=a[i+2]){
             *min1 = a[i];
             *min2 = a[i+1];
         }else if(a[i]<=a[i+2]&&a[i+2]<=a[i+1]){
             *min1 = a[i];
             *min2 = a[i+2];
         }else if(a[i+1]<=a[i]&&a[i]<=a[i+2]){
             *min1 = a[i+1];
             *min2= a[i];
         }else if(a[i+1]<=a[i+2]&&a[i+2]<=a[i]){
             *min1 = a[i+1];
             *min2 = a[i+2];
         }else if(a[i+2]<=a[i]&&a[i]<=a[i+1]){
             *min1 = a[i+2];
             *min2  =a[i];
         }else{
             *min1 = a[i+2];
             *min2 = a[i+1];
         }           
     }else{
         mid = (i + j)/2;
         mintwo(a, i, mid, &lmin1, &lmin2);
         mintwo(a, mid+1, j, &rmin1, &rmin2);
         if(lmin1 <= rmin1){
             *min1 = lmin1;
             if(lmin2 <= rmin2){
                 *min2 = lmin2;
             }else{
                 *min2 = rmin1;
             }
         }else{
             *min1 = rmin1;
             if(rmin2 <= lmin2){
                 *min2 = rmin2;
             }else{
                 *min2 = lmin1;
             }
         }       
     }
 }

6.2 分治法求一组数据的和

输入输出示例：

 8   代表8个数
 18
 -38
 -16
 87
 -27
 74
 31
 100
 分治法求出数组元素的和为:229

代码实现：

 #include "stdio.h"
 
 /**********  Begin  **********/
 int calculate_sum(int[], int, int);
 int main()
 {
     
     int i, num, sum;
     scanf("%d", &num);
     int a[num];
     for(i = 0; i < num; i++){
         scanf("%d", &a[i]);
     }   
     sum = calculate_sum(a, 0, num-1);
     printf("分治法求出数组元素的和为:%d",sum);
 }
 /**********  End  **********/
 int calculate_sum(int a[], int i, int j){
     int mid, left_sum, right_sum;
     if(i == j){
         return a[i];
 //  }else if(j-1 == 1){
 //      return a[i] + a[j];
     }else{
         mid = (i + j) / 2;
         left_sum = calculate_sum(a, i, mid);
         right_sum = calculate_sum(a, mid+1, j);
         return left_sum + right_sum;
     }
 }

6.3 求一组数据中第k小的数

输入输出示例：

 10 5 代表10个数据，求第5个小的元素
 -34
 95
 -50
 67
 73
 81
 -38
 10
 -11
 70
 第5小的元素是10

代码实现：

 #include<stdio.h>
 #define ArrLen 20
 void mergeSort(int[], int, int);
 void merge(int[], int, int, int);
 int main()
 {
     int i, num, k;
     scanf("%d %d", &num, &k);
     int a[num];
     for(i = 0; i < num; i++){
         scanf("%d", &a[i]);
     }
     mergeSort(a, 0, num-1);
     printf("第%d小的元素是%d", k, a[k - 1]);
     return 0;
 }
 void merge(int arr[], int start, int mid, int end) {
     int result[ArrLen];
     int k = 0;
     int i = start;
     int j = mid + 1;
     while (i <= mid && j <= end) {
         if (arr[i] < arr[j]){
             result[k++] = arr[i++];
         }
         else{
             result[k++] = arr[j++];
         }
     }
     if (i == mid + 1) {
         while(j <= end)
             result[k++] = arr[j++];
     }
     if (j == end + 1) {
         while (i <= mid)
             result[k++] = arr[i++];
     }
     for (j = 0, i = start ; j < k; i++, j++) {
         arr[i] = result[j];
     }
 }
  
 void mergeSort(int arr[], int start, int end) {
     if (start >= end)
         return;
     int mid = ( start + end ) / 2;
     mergeSort(arr, start, mid);
     mergeSort(arr, mid + 1, end);
     merge(arr, start, mid, end);
 }

本文来自投稿，不代表重蔚自留地立场，如若转载，请注明出处https://www.cwhello.com/96963.html

如有侵犯您的合法权益请发邮件951076433@qq.com联系删除

赞 (0)
语音刺客语音刺客订阅用户
0
上一篇 2022年9月12日 19:04
下一篇 2022年9月12日 20:04

相关推荐

联系我们

QQ：951076433

在线咨询：点击这里给我发消息邮件：951076433@qq.com工作时间：周一至周五，9:30-18:30，节假日休息