第一章算法设计基础

| 求大于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

更多推荐

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

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

第一章算法设计基础

| 求大于n的最小Smith数

第二章算法分析基础

| 斐波那契数列

第三章分治法

| 快速排序

| 查找第k小的元素

| 最大子段和

| 数组左移k个位置

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

第四章动态规划

| 数塔问题

| 最长递增子序列

| 最长公共子序列

| 0-1背包问题

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

| 机器人最短路径

第五章贪心算法

| 部分背包问题

| 活动安排问题

| 木棍覆盖区间问题

第六章回溯

| target目标和

实验题

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

| 实验1-2 格雷编码

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

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

发布评论取消回复

最近发表

热门文章

标签列表

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

第一章 算法设计基础

| 求大于n的最小Smith数​

第二章 算法分析基础

| 斐波那契数列

第三章 分治法

| 快速排序

| 查找第k小的元素

| 最大子段和

| 数组左移k个位置

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

第四章 动态规划

| 数塔问题

| 最长递增子序列

| 最长公共子序列

| 0-1背包问题

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

| 机器人最短路径

第五章 贪心算法

| 部分背包问题

| 活动安排问题

| 木棍覆盖区间问题

第六章 回溯

| target目标和

实验题

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

| 实验1-2 格雷编码

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

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

相关文章

发布评论取消回复

最近发表

热门文章

标签列表

第一章算法设计基础

| 求大于n的最小Smith数

第二章算法分析基础

第三章分治法

第四章动态规划

第五章贪心算法

第六章回溯