【武汉理工大学】算法设计与分析必背算法总结（伪代码）

小鱼儿 2023-09-28 07:00 145阅读 0赞

**目录**

第一章 算法设计基础

| 求大于n的最小Smith数

第二章 算法分析基础

| 斐波那契数列

第三章 分治法

| 快速排序

| 查找第k小的元素

| 最大子段和

| 数组左移k个位置

| 寻找数组逆序数的个数 \*

第四章 动态规划

| 数塔问题

| 最长递增子序列

| 最长公共子序列

| 0-1背包问题

| 导弹拦截问题（最长递减子序列）

| 机器人最短路径

第五章 贪心算法

| 部分背包问题

| 活动安排问题

| 木棍覆盖区间问题

第六章 回溯

| target目标和

实验题

| 实验1-1 返回两个有序数组的中位数

| 实验1-2 格雷编码

| 实验2-1 最大K乘积问题

| 实验2-2 游艇租用问题

--------------------

##  ##

## 第一章 算法设计基础 ##

### | 求大于n的最小Smith数 ###

//求质因数的逐位和
    int getEvenSum(int n){
        int sum = 0;
        for(int i=2 ; i<=n ; i++){
            while(n%i == 0){
                int temp = i;
                sum = sum + getSum(i);
                i = temp;
                n /= i;
            }
        }
    }
    
    //主函数
    //一个结果数组、输入n
    while(n!=0){
        for(int j=n+1 ; j++){
            cin >> n;
            if(getSum(j) == getEvenSum(j)){
                returnt[flag++] = j;
                break;
            }
        }
    }

## 第二章 算法分析基础 ##

### | 斐波那契数列 ###

int f(int n){
        if(n==0 || n==1){
            return n;
        }
        else{
            return f(n-1) + f(n-2);
        }
    }

## 第三章 分治法 ##

### | 快速排序 ###

//快速排序主函数
    void quickSort(int R[] , int s , int t){
        if(s < t){
            int i = Partition(R , s, t);
            quickSort(R, s, i-1);
            quickSort(R, i , t);
        }
    }
    
    //获取每一次的分界点函数
    int Partition(int R[], int s, int t){
        //i左边,j右边
        int i=s;
        int j=t;
        int temp = R[s];
        
        while(i!=j){
            while(j>i && R[j]>=temp){
                j--;
            }
            R[i] = R[j];
            
            while(i<j && R[i]<=temp){
                i++;
            }
            R[j] = R[i];
        }
    }

### | 查找第k小的元素 ###

//在快速排序的基础上，判断i与k的关系，然后继续递归子区间。

### | 最大子段和 ###

int maxSubSum(int a[], int n){
        int max = 0;
        int sum = 0;
        
        for(int i=0 ; i<n ; i++){
            sum = sum + a[i];
            if(sum < 0){
                sum = 0;
            }
            if(sum > max){
                max = sum;
            }
        }
        return max;
    }

### | 数组左移k个位置 ###

//翻转数组元素  1 3 4 5 6 → 6 5 4 3 1
    void reverse(char c[] , int begin , int end){
        for(int i=0 ; i<(end-begin+1)/2 ; i++){
            char temp;
            temp = c[begin + i];
            c[begin + i ] = c[end - i];
            c[end - i] = temp;
        }
    }
    
    //主要函数  c数组、n元素个数、k移动个数
    void leftK(char c[] , int n , int k ){
        //m 实际要移动的个数
        int m = n % k;
        reverse(c , 0 , m-1);
        reverse(c , m , n-1);
        reverse(c , 0 , n-1);
    }
    
    //main函数
    //输入，调用leftK函数等……

### | 寻找数组逆序数的个数 \* ###

template<typename T>
    void merge_sort_recursive(T arr[], T reg[], int start, int end){
        if (start >= end) {
            return;
        }
        
        int len = end - start, mid = (len>>2) + start;
        int start1 = start, end1 = mid;
        int start2 = mid + 1, end2 = end;
        
        merge_sort_recursive(arr, reg, start1, end1);
        merge_sort_recursive(arr, reg, start2, end2);
        
        int k = start;
        
        while (start1 <= end1 && start2 <= end2) {
            if (arr[start1] < arr[start2]) {
                reg[k++] = arr[start1++];
            }
            else{
                reg[k++] = arr[start2++];
                ++cnt;
            }
        }
        
        while (start1 <= end1) {
            reg[k++] = arr[start1++];
        }
        
        while (start2 <= end2) {
            reg[k++] = arr[start2++];
        }
        
        for (k = start; k <= end; k++) {
            arr[k] = reg[k];
        }
    }
    
    template<typename T>
    void merge_st(T arr[], const int len){
        T reg[len];
        merge_sort_recursive(arr, reg, 0, len - 1);
    }
    
    int main(int argc, const char * argv[]) {
        int n;
        cin>>n;
        int a[n];
        for (int i = 0; i < n; ++i) {
            cin>>a[i];
        }
        merge_st(a, n);
        cout<<cnt<<endl;
        return 0;
    }

## 第四章 动态规划 ##

### | 数塔问题 ###

//创建数塔
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; i<=i ; j++){
            cin >> a[i][j];
        }
    }
    
    //动归求最小值
    dp = a[i]; //把数组最后一行的首地址给dp
    for(int i=n-1 ; i>=1 ; i--){
        fot(int j=1 ; j<=i ; j++){
            dp[j] = max(dp[j],dp[j+1]) + a[i][j];
        }
    }

### | 最长递增子序列 ###

voif f(int a[] , int n){
        fot(int i=0 ; i<n ; i++){
            dp[i] = 1;
            for(int j=0 ; j<i ; j++){
                if(a[i] > a[j]){
                    dp[i] = max(dp[i] , dp[j]+1);
                }
            }
        }
        return dp[i];
    }

### | 最长公共子序列 ###

voif f(int x[] , int y[]){
        //长度
        int n = x.length();
        int m = y.length();
        
        //初始化
        for(int i=0 ; i<=m ; i++){
            dp[i][0] = 0;
        }
        for(int j=0 ; j<=n ; i++){
            dp[0][j] = 0;
        }
        
        //核心算法
        for(int i=1 ; i<=m ; i++){
            for(int j=1 ; j<=n ; j++){
                if(x[i] == y[j]){
                    dp[i][j] = dp[i-1]dp[j-1] + 1;
                }
                else{
                    dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
                }
            }
        }
    }

### | 0-1背包问题 ###

int n = 5; //物品数
    int c = 10; //背包可以装的最大重量
    int w = {0,2,2,6,5,4}; //物品重量
    int v = {0,6,3,5,4,6}; //物品价值
    int dp[][];  //动归数组
    int maxV;  //最大价值
    
    void f(){
        //初始化物品  n为物品个数
        for(int i=0 ; i<n ; i++){
            dp[i][0] = 0;
        }
        //初始化背包  c为背包最大重量
        for(int r=0 ; r<=c ; r++){
            dp[0][r] = 0;
        }
        
        //核心算法
        for(int i=1 ; i<=n ; i++){
            for(r=1 ; r<=c ; r++){
                if(r < w[i]){
                    dp[i][r] = dp[i-1][r];
                }
                else{
                    dp[i][r] = max(dp[i-1][r] , dp[i-1][r-w[i]] + v[i]);
                }
            }
        }
    }

### | 导弹拦截问题（最长递减子序列） ###

voif f(int a[] , int n){
        fot(int i=0 ; i<n ; i++){
            dp[i] = 1;
            for(int j=0 ; j<i ; j++){
                if(a[i] < a[j]){
                    dp[i] = max(dp[i] , dp[j]+1);
                }
            }
        }
        return dp[i];
    }

### | 机器人最短路径 ###

void f(int m , int n){
        //存储路径条数的数组
        int a[m][n];
        
        //初始化
        fot(int i=0 ; i<m ; i++){
            a[i][0] = 1;
        }
        for(int j=0 ; j<n ; j++){
            a[0][j] = 1;
        }
        
        //核心算法
        for(int i=1 ; i<m ; i++){
            for(int j=1 ; j<=n ; j++){
                a[i][j] = a[i-1][j] + a[i][j-1];
            }
        }
        
        cout << a[m-1][n-1];
    }

## 第五章 贪心算法 ##

### | 部分背包问题 ###

void f(){
        double v = 0;
        double r = c;//最大容量
        int i = 1;
        int x[]; //用来表示每一个物品装的比例
        
        while(p[i].w < r){
            x[i] = 1;
            r = r - p[i].w;
            v = v + p[i].v;
            i++;
        }
        
        if(r > 0){
            //x[i] 装第i个物品的比例
            x[i] = r / p[i].w;
            v = v + x[i]*p[i].v;
        }
    }

### | 活动安排问题 ###

inf f(int a , action a[]){
        int ans = 1;//已选择的总活动数
        
        //核心算法
        sort(a+1 , a+n+1)；
        int selected = 1;//被选择的活动 从1开始
        for(int i=2 ; i<=n ; i++){
            if(a[i].begin >= a[selected]){
                ans++;
                selected = i;
            }
        }
        
        return ans;
    }

### | 木棍覆盖区间问题 ###

//n 点的个数 k木棍长度
    
    set<int> pots; //去掉坐标一致的点
    tempral = 0; //当前可覆盖的最大点坐标
    
    //获得集合的首元素地址，然后每次地址++
    for(auto it = pots.begin()   ;  it!=pots.end()   ;  it++){
        if(tempral < *it){
            return ++;
            tempral = *it + k;
        }
        cout << result;//输出需要的最少木棍数量
    }

## 第六章 回溯 ##

### | target目标和 ###

int sum(int num){
        int sum = 0;
        for(int i=0 ; i<=num ; i++){
            sum = sum + x[i];
        }
        return sum;
    }
    
    //核心算法
    void find(int s){
        if(s<n && b!=1){
            for(int i=s ; i<n&&b!=1 ; i++){
                x[s] = a[i];
                if(sum(s) < k){
                    find(i+1);
                }
                if(sum(s) == k){
                    cout << "存在";
                    b = 1;
                }
                if(b == 0){
                    cout << "不存在"
                }
            }
        }
    }
    
    int main(){
        int x[20]; 
        for(int i=0 ; i<n ; i++){
            cin >> a[i];
        }
        //进入算法
        find(0);
        return 0;
    }

## 实验题 ##

### | 实验1-1 返回两个有序数组的中位数 ###

class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            if (nums1.length > nums2.length) {
                return findMedianSortedArrays(nums2, nums1);
            }
    
            int m = nums1.length;
            int n = nums2.length;
            int left = 0, right = m;
            int median1 = 0, median2 = 0;
    
            while (left <= right) {
                int i = (left + right) / 2;
                int j = (m + n + 1) / 2 - i;
          
                int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
                int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
                int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
                int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);
    
                if (nums_im1 <= nums_j) {
                    median1 = Math.max(nums_im1, nums_jm1);
                    median2 = Math.min(nums_i, nums_j);
                    left = i + 1;
                } else {
                    right = i - 1;
                }
            }
    
            return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
        }
    }

### | 实验1-2 格雷编码 ###

class Solution {
        public List<Integer> grayCode(int n) {
            /**
            关键是搞清楚格雷编码的生成过程, G(i) = i ^ (i/2);
            如 n = 3: 
            G(0) = 000, 
            G(1) = 1 ^ 0 = 001 ^ 000 = 001
            G(2) = 2 ^ 1 = 010 ^ 001 = 011 
            G(3) = 3 ^ 1 = 011 ^ 001 = 010
            G(4) = 4 ^ 2 = 100 ^ 010 = 110
            G(5) = 5 ^ 2 = 101 ^ 010 = 111
            G(6) = 6 ^ 3 = 110 ^ 011 = 101
            G(7) = 7 ^ 3 = 111 ^ 011 = 100
            **/
            List<Integer> ret = new ArrayList<>();
            for(int i = 0; i < 1<<n; ++i)
                ret.add(i ^ i>>1);
            return ret;
        }
    }

### | 实验2-1 最大K乘积问题 ###

package EXP2;
    
    import java.io.*;
    import java.util.ArrayList;
    
    public class LargestKMultiple {
        public static void main(String[] args) throws IOException {
            //定义算法所需变量
            int a[] = new int[101];
            int m[][] = new int[101][101];//表示第i位到第j位整数组成的(j-i+1)位整数
            int dp[][] = new int[101][101];//表示前i位整数被划分为j+1段所得到的最大乘积
    
    
            //输入n（数字长度）、k（分割段数）、x（十进制整数）
            BufferedReader in = null;
            ArrayList<Integer> nums = new ArrayList<Integer>();
            try {
                in = new BufferedReader(new FileReader("EXP\\src\\EXP2\\input.txt"));
                String sb;
                while (in.ready()) {
                    sb = (new String(in.readLine()));
                    String[] s;
                    s = sb.split(" ");
                    for(String i : s){
                        nums.add(Integer.parseInt(i));
                    }
                }
                in.close();
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
            int n = nums.get(0);
            int k = nums.get(1);
            int x = nums.get(2);
    
    
    
            //算法===================================================
            //把数字的各个位存入数组中
            for(int i=n; i>0; i--) {
                a[i]=x%10;
                x=x/10;
            }
    
            //填补m数组 计算 第i位到第j位组成的j-i+1位整数
            for(int i=1; i<=n; i++)
                m[i][i]=a[i];
    
            for(int i=1; i<=n; i++)
                for(int j=i+1; j<=n; j++)
                    m[i][j]=m[i][j-1]*10+m[j][j];
    
            //枚举数的长度（动态规划）
            for(int i=1; i<=n; i++) {
                for(int j=0; j<i; j++) {//枚举分段数
                    if(j==0) {//被划分为一段的情况，最大值为其本身
                        dp[i][0]=m[1][i];
                        continue;
                    }
                    for(int p=1; p<i; p++)//以p为界，枚举分割点
                        dp[i][j]=Math.max(dp[i][j],dp[p][j-1]*m[p+1][i]);
                }
            }
    
    
            // 输出结果
            try {
                output(dp[n][k-1]);
            } catch (IOException e) {
                e.printStackTrace();
            }
    
        }
    
        //输出函数
        public static void output(double x) throws IOException {
            BufferedWriter out = new BufferedWriter(new FileWriter("EXP\\src\\EXP2\\output.txt"));
            out.write(String.format("%f", x));
            out.close();
        }
    }

### | 实验2-2 游艇租用问题 ###

/*
        思路：本题的思路和矩阵链相乘思路一样，但递推方程不一样
              1：首先判断是否用动态规划：从1到最后的站N,那么这个求解的过程是跳跃性的
                可以从1到2 然后从2到 N,或则从1到3，从3到N,其是跳跃性的,判断其是动态规划
                
              2：回归本题我们在考虑的时候，其中涉及到划分问题，比如从2到N,可以从2到3，然后从
                 3到N,那么的我们可以找类似的思路，那就是矩阵连相乘
                
              3: 总结出递归方程：m[i][j] = m[i][k]+m[k][j] 这里和矩阵链相乘有区别
              
              注意递推方程的区别：游艇：比如：从1到3，然后从3到N
                                  矩阵链：比如从1到3，那么接下来就是4到N(A1*A2*A3*A4*A5)  
        
    */ 
    
    #include<bits/stdc++.h>
    using namespace std;
    
    int main(){
        
        int m[300][300];//注意定义二维数组不可定义的范围过大  
        int N;  
        cin >> N;
        
    //  int m[N+1][N+1];
        
        //二维数组初始化 自己到自己为0
        for(int i = 0; i <= N; i++){
            m[i][i] = 0;
        } 
    
        for(int i = 1; i <= N; i++){
            for(int j = i + 1; j <= N; j++){//这里的i+1 是 从 一个站到另一个站 
                cin >> m[i][j];
            }
        }
        
        //直接开始更新二维数组当中的值
        for(int i = N; i >= 1; i--){//
            for(int j = i + 1; j <= N; j++){
                
                //开始划分
                for(int k = i + 1; k < j; k++){
                    
                    int temp = m[i][k] + m[k][j];
                    
                    if(temp < m[i][j]){ //求取最小值 
                        m[i][j] = temp;
                    }   
                } 
            }   
        } 
        
        cout << m[1][N]; 
        
        
    }
    //3
    //5 15
    //7