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\)位，

棋盤覆寫

利用分治思想，將一個大棋盤分為四個小棋盤，其中沒有殘缺格的三個子棋盤可以用一個L型骨牌連接，

合并排序

合并排序可以使用分治遞回求解，

package second;

import java.util.Arrays;
import java.util.List;

/**
 * @author CrisKey
 * @date 2022/11/18 09:01
 * 各種排序問題
 */
public class SortProblem {

    public static void mergeSort(int[]arr,int left,int right){
        if (right<=left) {
            return;
        }

        int mid = (right+left)/2;
      mergeSort(arr,left,mid);
       mergeSort(arr,mid+1,right);
       merge(arr,left,mid,right);
}
public static void merge(int[]arr,int left,int mid,int right){
        //創建一個臨時陣列存放合并資料
        int[] temp = new int[right-left+1];
        int i = left;
        int j = mid+1;
        int k = 0;
        while(i<=mid&&j<=right){
            if (arr[i]<=arr[j]){
                temp[k++] = arr[i++];
            }else {
                temp[k++] = arr[j++];
            }
        }
        if (i<=mid){
            while (i<=mid){
                temp[k++] = arr[i++];
            }
        }
        if (j<=right){
            while(j<=right) {
                temp[k++] = arr[j++];
            }

        }
        k=0;
        for (int index =left;index<=right;index++){
            arr[index] = temp[k++];

        }

    }



}

也可以使用非遞回實作，

  /**
     *  非遞回實作
     */
    public static void sort(int[] arr){
        int len = 1;
        int size = arr.length;
        while(len<size){
            for (int i = 0 ;i+len<size;i+=len*2){
                int left = i;
                int mid =i+len-1;
                int right = i+len*2-1;
                if (right>size-1) right = size-1;
                merge(arr,left,mid,right);
            }
            len=len*2;
        }

    }

快速排序

快速排序使用分治遞回求解，求解步驟分為三步:

將陣列以基準元素分為左右兩邊
對左邊遞回
對右邊遞回

 public static void quickSort(int[]arr,int left,int right){
        if (left<right){
            int p = partition(arr,left,right);
            quickSort(arr,left,p);
            quickSort(arr,p+1,right);
        }
       
    }
    public static int  partition(int[] arr,int left,int right){
        int index;
        //以最左元素作為基準

        int flag = arr[left];
        int i = left;
        int j = right+1;
        //將大于flag的移至左邊，小于的移至右邊
        while (true){
            while (arr[++i]<flag&&i<right){

            }
            while (arr[--j]>flag){
            }
            if (i>=j) {
                break;
            }
            //將i與j交換
            swap(arr,i,j);
        }
        swap(arr,j,left);
        return j ;
    }

    public static void  swap(int[]arr,int i1,int i2){
        int x = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = x;
    }

選擇基準時，也可以通過隨機選擇

第三章動態規劃

動態規劃演算法適用于解最優化問題，通常可按照以下4個步驟設計：

找出最優解性質，并刻畫其結構特征，
遞回的定義最優值，
以自底向上的方式計算出最優值，
根據計算最優值時得到的資訊，構造最優解，

矩陣連乘問題

若要求解出\(A_1A_2···A_n\)，則必存在k使得\((A_1A_2···A_k)*(A_{k+1}···A_n)\)為最優，然后分別找出左半部分最優和右半部分最優，

使用一個二維陣列來記錄矩陣連乘所需次數，一個二維陣列記錄最佳位置，

/**
 * @author CrisKey
 * @date 2022/11/18 15:56
 * 矩陣連乘問題
 */
public class MatrixMultiply {
    public static void multiply(int[] m){
        int size = m.length;
        //存盤矩陣乘后結果
        int[][] result =new int[size][size];
        //存盤分割點
        int[][] s = new int[size][size];

        for (int i=1;i<size;i++) {
            result[i][i] = 0;

        }
       for (int r=2;r<size;r++){
           for (int l=r-1;l>=1;l--){
               result[l][r] = result[l][l]+result[l+1][r]+m[l-1]*m[l]*m[r];
               s[l][r] = l;
               for (int k=l+1;k<r;k++){
                   int t = result[l][k]+result[k+1][r]+m[l-1]*m[k]*m[r];
                   if (t<result[l][r]) {
                       s[l][r] = k;
                       result[l][r] = t;
                   }
               }
           }
       }
        System.out.println(result[1][size-1]);


    }


    public static void main(String[] args) {
        int[] m = new int[]{30,35,15,5,10,20,25};
        multiply(m);
    }
}

最長公共子序列

分析結構
建立遞回關系
計算最優值

完整代碼

package third;

/**
 * @author CrisKey
 * @date 2022/11/19 19:11
 * 最長公共子序列
 */
public class LCSLength {
    public static void lcsLength(String A,String B){
        char[] a = A.toCharArray();
        char[] b = B.toCharArray();

        int[][] m = new int[a.length+1][b.length+1];
        for (int i=1;i<=a.length;i++) {
            m[i][0] = 0;
        }
        for (int j=1;j<=b.length;j++){
                m[0][j] = 0;
            }
        m[0][0]=0;

        for (int i=1;i<=a.length;i++) {
            for (int j=1;j<=b.length;j++){
                if (a[i-1]==b[j-1]){
                    m[i][j] = m[i-1][j-1]+1;
                }
                else if (m[i][j-1]>m[i-1][j]){
                    m[i][j] = m[i][j-1];
                }else {
                    m[i][j] = m[i-1][j];
                }
            }
        }
        System.out.println("最長公共子序列是:");
        for (int i=1;i<=a.length;i++) {
            for (int j=1;j<=b.length;j++){
                if (m[i][j]==m[i-1][j]+1){
                    System.out.print(a[i-1]);
                    break;
                }
            }
        }
        System.out.println();
        System.out.println("==========");

    }



    public static void main(String[] args) {
        String A = "AFVGHBJNKKJL";
        String B = "AVNGJFDSKDBSL";
        lcsLength(A,B);
    }
}

最大欄位和

最大欄位和有多種方式求解，下面介紹的是動態規劃求解，

package third;

import java.util.Arrays;

/**
 * @author CrisKey
 * @date 2022/11/19 20:15
 * 最大欄位和
 */
public class MaxSum {
    public static void maxSum(int []a){
        int[] b= new int[a.length];
        b[0] = a[0];
        for (int i=1;i<a.length;i++){
            if (b[i-1]<0) b[i] = a[i];
            else b[i] = b[i-1]+a[i];
        }
        System.out.println("最大欄位和為：");
        System.out.println(Arrays.stream(b).max().getAsInt());
    }
    public static void main(String[] args) {
        int[] a = new int[]{-2,11,7,-3,-12,7,-3,7};
        maxSum(a);
    }
}

本文來自博客園，作者：我只有一天的回憶，轉載請注明原文鏈接：https://www.cnblogs.com/cc-coding/p/16901119.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/536218.html

標籤：其他

上一篇：Git基礎.ONE（簡單創建一個本地Git專案吧）

下一篇：「動態規劃」欠債還錢

演算法導論筆記

第二章 分治與遞回

遞回