• CUMT算法导论课程

• 课本：计算机算法设计与分析（王晓东）

• 本blog代码为Java实现

第二章 分治与递归

递归

直接或间接调用算法自身。

全排列问题

求出n个元素的全排列，可以使用递归。即若要求出\(Perm(X_i)\),可以先求出\(Perm(X_{i-1})\),然后再依次加上前缀。

设\(R=\){\(r_1,r_2,r_3,···,r_n\)}是要进行排列的n个元素，\(R_i=R-\){\(r_i\)}。\((r_i)\)\(Perm(X)\)代表X的全排列加上前缀ri

R的全排列定义为：

当n = 1时,Perm(R) = r。

当n>1时,Perm(R)为 \((r_1)Perm(R_1),(r_2)Perm(R_2),···(r_n)Perm(R_n)\)。

代码实现：

/**
 * @author CrisKey
 * @date 2022/11/17 18:38
 * 全排列问题
 */
public class Arrangement {
    public int fullPermutation(List<String> list,int k,int m,int count){ //打印list[k:m]
        //递归到递归基
        if (k==m){
            System.out.println(list);
            count++;
        }
        for (int i=k;i<m;i++){
            Collections.swap(list,i,k);
          count =   fullPermutation(list,k+1,m,count);
            Collections.swap(list,i,k);
        }
        return count;
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list = Arrays.asList("1","3","5","7","9");
        Arrangement arrangement = new Arrangement();
        int count = 0;
        count = arrangement.fullPermutation(list,0,list.size(),count);
        System.out.println("总共有"+count+"种排列方式");
    }
}

整数划分问题

将正整数n表示为一系列正整数之和，

​ \(n=n_1+n_2+···+n_k\) (其中，\(n_1\ge n_2\ge n3 \ge ···\ge n_k \ge 1,k\ge 1\))

同样，本题可以用递归求解。

分析后可知，本题分为四种情况。

/**
 * @author CrisKey
 * @date 2022/11/17 19:39
 * 整数划分问题
 */
public class Divide {

    public static int  partition(int n,int m){

        if (n==1||m==1){
           return 1;
        }else if (m==n){
                //整形本身
          return   partition(n,m-1)+1;
        }else if (m>n){
         return    partition(n,n);
        }else if (n<1||m<1) {
            return 0;
        }else {
            return partition(n,m-1)+partition(n-m,m);
        }

    }
    public static void main(String[] args) {
        int x = 6;

            int count = partition(x,x);

        System.out.println("正整数x共有:"+String.valueOf(count)+"种划分");
    }
}

Hanoi塔问题

汉诺塔是典型的递归问题。

/**
 * @author CrisKey
 * @date 2022/11/17 20:48
 * 汉诺塔问题
 */
public class HanoiProblem {
    public static void hanoi(int n,String A,String B,String C){
        if (n>0){
            hanoi(n-1,A,C,B);
            System.out.println("将"+String.valueOf(n)+"从"+A+"移到"+C+"借助"+B);
            hanoi(n-1,C,B,A);
        }
    }

    public static void main(String[] args) {
        hanoi(3,"A","B","C");
    }
}

分治

二分搜索

二分搜索给定已排序好的n个元素，在这n个元素中找到特定元素x。

可以利用分治与递归，将问题划分为在数组的左边查找或者在数组的右边查找，可以降低时间复杂度。

使用二分搜索最坏情况下复杂度为\(O(logn)\)

/**
 * @author CrisKey
 * @date 2022/11/17 21:15
 */
public class BinarySearchProblem {
    public static void BinarySearch(int[] arr,int left,int right,int flag){
        if (right<left){
            System.out.println("错误");
        }else if (right==left){
            if (flag==arr[right]){
                System.out.println(right);
            }
        }
        else{
            int mid = (right-left)/2;
            if (arr[mid]==flag){
                System.out.println(mid);
            }else if (arr[mid]<flag){
               BinarySearch(arr,mid+1,right,flag);
            }else {
                BinarySearch(arr,left,mid-1,flag);
            }
        }
    }

    public static void main(String[] args) {
        int []arr = new int[]{0,1,2,3,4,5,6,7,8,9,10};
        BinarySearch(arr,0,10,5);
    }
}

大整数乘法

\(设X与Y都是n位二进制数，现在要计算他们的乘积XY\)。

可以将\(X Y\)分段，将其分别分为两段，每段长\(n/2\)位。

棋盘覆盖

合并排序

快速排序

线性时间选择

最接近点对问题

二维

三维

原文地址：http://www.cnblogs.com/cc-coding/p/16901119.html