nuc算法设计与分析 ppt总结

总纲

                               插入排序算法

内容:

将数组待排序的元素依次插入到已排序部分,使已排序部分保持升序的性质。

伪代码:

复杂度分析:

时间复杂度为O(n^2),空间复杂度为O(1)。在数据量较小的情况下,插入排序的效率不输给其他更复杂的排序算法,并且其实现简单,易于理解和编写,并且不需要额外的存储空间。

运行结果:

源代码:

import java.util.Arrays;

public class InsertionSort {

public static void insertionSort(int[] arr) {

for (int j = 1; j < arr.length; j++) {

int key = arr[j];

//将A[j]插入到已排序的数组A[1...j-1]中

int i = j - 1;

while (i >= 0 && arr[i] > key) {

arr[i + 1] = arr[i];

i = i - 1;

}

arr[i + 1] = key;

}

}

public static void main(String[] args) {

int[] arr = {6 , 7 , 2 , 5 , 8 , 4 , 1 , 3 , 9};

insertionSort(arr);

System.out.println(“插入排序:”);

System.out.println(Arrays.toString(arr));

}

}

                    选择排序算法

内容:

第一次遍历找到最小元素

第二次在剩余数组中遍历找到最小元素,即整个数组的次小元素,并按照顺序放在已排列的数列的末尾

...

第n次在剩余数组中遍历找到第n小元素

伪代码:

复杂度分析:

时间复杂度为O(n^2),空间复杂度为O(1)。与插入排序算法相比,选择排序算法的比较次数相同,但交换次数比插入排序算法要少,因此在数据量较大的情况下,选择排序算法的效率要优于插入排序算法。然而,选择排序算法的局限性在于其不稳定,也就是说,在待排序序列中,存在多个元素值相同的元素,在排序后它们在序列中的相对位置可能会发生变化。

运行结果:

源代码:

public class Sort {

//选择排序

public static void selectionSort(int[] arr) {

for(int i = 0; i < arr.length - 1 ; i++) {

int minindex = i;

for(int j = i + 1; j < arr.length; j++) {

    //如果A[i]大于A[j],则交换二者的位置

if(arr[minindex] > arr[j]) {

minindex = j;

}

}

int temp = arr[i];

arr[i] = arr[minindex];

arr[minindex] = temp;

}

}

public static void main(String[] args) {

int[] arr = {6 , 7 , 2 , 5 , 8 , 4 , 1 , 3 , 9};

System.out.println(“选择排序:”);

selectionSort(arr);

for(int i : arr) {

System.out.print(i + “ ”);

}

}

}

时间复杂度:

递归式分析:

1、递归树法:

2、主定理法:

!!!

eg

                        分而治之篇

分而治之:一般步骤 (书73页)

     

          分而治之篇 之 归并排序算法

内容:

将待排序的序列划分成若干个子序列,对每个子序列进行排序,然后将已经排好序的子序列合并成一个有序的序列。

核心是通过比较两个有序子序列的首元素,将较小的元素依次放入结果序列中;如果其中一个子序列排完了,直接将另一个子序列剩下的元素并入结果序列。

算法流程:

伪代码:

复杂度分析:

归并排序是一种稳定的算法,在最坏情况下的时间复杂度为O(nlog n),但是空间复杂度为O(n),使用时需要注意空间的限制。它的优势在于适用于序列链表等数据结构以及具有较好的稳定性和复杂度分析。

运行结果:

源代码:

import java.util.Arrays;

public class MergeSort {

public static void mergeSort(int[] arr, int left, int right) {

if (left < right) {

int mid = (left + right) / 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 n1 = mid - left + 1;

int n2 = right - mid;

int[] L = new int[n1];

int[] R = new int[n2];

// L[i] <-- arr[left]  R[j] <-- arr[right] 将两个子序列分别赋值给L[i] 和R[j]

for (int i = 0; i < n1; i++) {

L[i] = arr[left + i];

}

for (int j = 0; j < n2; j++) {

R[j] = arr[mid + 1 + j];

}

// 比较两个有序子序列的首元素,将较小的元素依次放入结果序列中

int i = 0, j = 0, k = left;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

}

k++;

}

// 如果其中一个子序列排完了,直接将另一个子序列剩下的元素并入结果序列

while (i < n1) {

arr[k] = L[i];

i++;

k++;

}

while (j < n2) {

arr[k] = R[j];

j++;

k++;

}

}

public static void main (String[] args) {

int[] arr = {6 , 7 , 2 , 5 , 8 , 4 , 1 , 10 , 3 , 9};

mergeSort(arr, 0, arr.length - 1);

System.out.println(“归并排序:”);

System.out.println(Arrays.toString(arr));

}

}

 分而治之篇 之 最大子数组问题

背景:

子数组: 子数组为数组X中连续的一段序列

内容:

最大子数组:在一个数列中找到一个连续子序列,使得该子序列所有数字之和最大。

分而治之法是将数列二分分而治之,找出左半部分、右半部分和跨越中点的三种情况中最大的子数组和。

算法流程:

伪代码:

复杂度分析:

分治法思路的最大子数组问题时间复杂度为O(nlogn)。因为需要将问题分解成O(logn)个子问题,并且每个子问题的求解需要O(n)的时间。因此总共需要O(nlogn)的时间来解决这个问题。

源代码:

import java.util.Arrays;

public class MaxSubArray {

public static int[] maxSubArrayHelper(int[] nums) {

return maxSubArray( nums , 0 , nums.length - 1 );

}

private static int[] maxSubArray( int[] nums , int low , int high ) {

if ( low == high ) {

return new int[]{ low , high , nums[low] } ;

} else {

int mid = ( low + high ) / 2;

int[] left = maxSubArray( nums , low , mid );

int[] right = maxSubArray( nums , mid + 1 , high);

int[] cross = CrossingSubArray( nums , low , mid , high);

int leftSum = left[2];

int rightSum = right[2];

int crossSum = cross[2];

// Smax <-- max{S1,S2,S3} , 求数组nums的最大子数组之和

if ( leftSum >= rightSum && leftSum >= crossSum ) {

return left;

} else if ( rightSum >= leftSum && rightSum >= crossSum ) {

return right;

} else {

return cross;

}

}

}

private static int[] CrossingSubArray( int[] nums , int low , int mid , int high ) {

int leftSum = Integer.MIN_VALUE;

int Sum = 0;

int maxLeft = mid;

//从nums[mid]向前遍历求和,并记录最大值leftSum

for ( int l = mid ; l >= low ; l-- ) {

Sum += nums[l];

if ( leftSum < Sum ) {

leftSum = Sum;

maxLeft = l;

}

}

int rightSum = Integer.MIN_VALUE;

Sum = 0;

int maxRight = mid + 1;

//从nums[mid+1]向后遍历求和,并记录最大值rightSum

for ( int r = mid + 1 ; r <= high ; r++) {

Sum += nums[r];

if ( rightSum < Sum) {

rightSum = Sum;

maxRight = r;

}

}

return new int[]{ maxLeft , maxRight , leftSum + rightSum };

}

public static void main (String[] args) {

int[] nums = { -1 , -3 , 3 , 5 , -4 , 3 , 2 , -2 , 3 , 6 };

int[] result = maxSubArrayHelper(nums);

System.out.println(“输入的数组为:\n” + Arrays.toString(nums));

System.out.println(“最大子数组中,连续子序列在原始数组中的起始下标、终止下标,以及最大子数组的和为:\n” + Arrays.toString(result));

}

}

分而治之篇 之 快速排序算法

背景:

在将原数组一分为二,递归求解子问题时,设计到了“数组划分”思想

内容:

随机化快速排序(Randomized Quicksort)算法是一种基于“分治”的排序算法,其基本思路是选取一个随机元素(pivot),将待排序序列分为两个子序列:比pivot小的在左侧,比pivot大的在右侧,然后递归地对两个子序列进行排序,最终将所有子序列合并为一个有序序列。

具体流程:

伪代码:

复杂度分析:

随机化快速排序的平均时间复杂度为 O(nlogn),最坏情况下的时间复杂度为 O(n^ 2),空间复杂度为 O(logn) 或 O(n)。

运行结果:

源代码:

import java.util.Arrays;

import java.util.Random;

public class QuickSort {

public static int randomizedPartition ( int[] arr , int p , int r ) {

int s = new Random().nextInt(r - p + 1) + p;

swap( arr , s , r );

int q = partition( arr , p , r );

return q;

}

public static void randomizedQuickSort( int[] arr , int p , int r ) {

if ( p < r ) {

int q = randomizedPartition( arr , p , r );

randomizedQuickSort( arr , p , q - 1 );

randomizedQuickSort( arr , q + 1 , r );

}

}

public static int partition( int[] arr , int p , int r ) {

int x = arr[r];

int i = p - 1;

for ( int j = p ; j < r ; j++ ) {

if ( arr[j] <= x ) {

i++;

swap( arr , i , j );

}

}

swap( arr , i +1 , r );

int q = i + 1;

return q;

}

public static void swap( int[] arr , int i , int j ) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

public static void main(String[] args) {

int[] arr = new int[]{ 9 , 7 , 5 , 11 , 12 , 2 , 14 , 3 , 10 , 6 };

System.out.println(“排序前的数组为:” + Arrays.toString(arr));

randomizedQuickSort(arr , 0 , arr.length - 1 );

System.out.println(“排序后的数组为:” + Arrays.toString(arr));

}

}

分而治之篇 之 汉诺塔问题

内容:(书74页)

有三根柱子,标号分别为A、B、C。在A柱子上从下往上按大小顺序依次摆放着 n 个圆盘,现在需要将A柱子上的圆盘移动到C柱子上,每次只能移动一个圆盘,且在移动过程中不能出现大盘放在小盘上面的情况。请问,最少需要移动多少次,才能将所有圆盘从A柱子移动到C柱子上?

算法流程:

通过三个步骤实现:

  1. 将塔A上的n-1个圆盘借助塔C先移动到塔B上;
  2. 将塔A上剩下的一个圆盘移动到塔C上;
  3. 将n-1个圆盘从塔B借助于塔A移动到塔C上。

    

伪代码:

Algorithm Hanoi(n, A, B, C)

// 将 A 上面的 n 个圆盘移动到 C 上面,借助 B

if n == 1:

move(A, C) // 将圆盘从 A 移动到 C

else:

Hanoi(n-1, A, C, B) // 将 A 上面的 n-1 个圆盘移动到 B 上面,借助 C

move(A, C) // 将圆盘从 A 移动到 C

Hanoi(n-1, B, A, C) // 将 B 上面的 n-1 个圆盘移动到 C 上面,借助 A

复杂度分析:

汉诺塔问题的递归解法的时间复杂度为 O(2^n),其中 n 表示圆盘的数量。这是因为,当有 n 个圆盘时,每次移动圆盘时都要将 n-1 个圆盘从一根柱子移动到另一根柱子,而这个操作的时间复杂度是 O(2^(n-1))。

汉诺塔问题的时间复杂度增长非常迅速,随着圆盘数量的增加,所需的步数呈指数级增长。

运行结果:

源代码:

import java.util.Scanner;

public class HanoiTower {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

System.out.println(“请输入圆盘的数目n:”);

int n = sc.nextInt();     // 将A上面的n个圆盘移动到C上面

String a = “A” , b = “B” , c = “C”;   // 三根柱子的标号

System.out.println(“汉诺塔问题运行结果:”);

Hanoi(n , a , b , c);

}

public static void Hanoi(int n , String A , String B , String C) {

if (n == 1) {

// 将圆盘从A移动到C

System.out.println(“move ” + A + “ to ” + C);

} else {

// 将A上面的n-1个圆盘移动到B上面,借助C

Hanoi(n - 1 , A , C , B);

// 将圆盘从A移动到C

System.out.println(“move ” + A + “ to ” + C);

// 将B上面的n-1个圆盘移动到C上面,借助A

Hanoi(n - 1 , B , A , C);

}

}

}

减治:

折半查找:

分治逆序对计数问题:

蛮力法:

分治法优化:

分治次序选择:选第k小元素:

固定位置划分:

随机位置划分:

动态规划篇

最优子问题

一般步骤:(书129页)

                动态规划篇 之 0/1背包问题  

内容:(书135页)

有一个背包,容量为C;有n个物品,每个物品的体积为v[i],价值为p[i]。要求从这n个物品中选择总体积不超过C的若干个物品放入背包中,使得这些物品的总价值最大。

算法流程:

用动态规划算法求解。首先,定义二维数组 P[i][c] 表示在前 i 个物品中选出若干个物品放入容量为 c 的背包中所能获得的最大价值。对于每个物品,存在两个选择:放入背包或者不放入背包。因此,可以得到状态转移方程:

如果第 i 个物品的体积 v[i] 大于 c,即装不下,此时 P[i][c] = P[i-1][c]

如果第 i 个物品的体积 v[i] 小于等于 c,可以选择放入或不放入背包:

放入背包:P[i][c] = P[i-1][c-v[i]] + p[i]

不放入背包:P[i][c] = P[i-1][c]

     

伪代码:

复杂度分析:

动态规划算法解决0/1背包问题的时间复杂度为 O(nC,其中 n 表示物品数量,C 表示背包容量。

源代码: 

import java.util.*;

public class KnapsackProblem {

// 动态规划实现 0/1 背包问题

// 输入:商品数量n , 各商品的价值p , 各商品的体积v , 背包容量C

// 输出:商品价格的最大值,最优解方案

public static int knapsackDP(int n , int[] p , int[] v , int C) {

//创建二维数组P[0...n,0...C] 和Rec[0...n,0...C]

int[][] P = new int[n+1][C+1];

int[][] Rec = new int[n+1][C+1];

//初始化

for (int i = 0 ; i <= C ; i++) {

P[0][i] = 0;

}

for (int i = 0 ; i <= n ; i++) {

P[i][0] = 0;

}

for (int i = 0 ; i <= C ; i++) {

Rec[0][i] = 0;

}

for (int i = 0 ; i <= n ; i++) {

Rec[i][0] = 0;

}

//求解表格

for (int i = 1 ; i <= n; i++) {

        for (int c = 1 ; c <= C ; c++) {

if (c < v[i - 1]) {

P[i][c] = P[i-1][c];

Rec[i][c] = 0;

} else {

P[i][c] = Math.max(P[i-1][c] , P[i-1][c-v[i-1]] + p[i-1]);

Rec[i][c] = 1;

}

}

}

//输出最优解方案

int k = C;

//输出最优解方案

int k = C;

for (int i = n ; i > 0 ; i--) {

if (Rec[i][k] == 1) {

System.out.println(“选择第” + i + “个商品”);

k = k - v[i-1];

} else {

System.out.println(“不选择第” + i + “个商品”);

}

}

return P[n][C];

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

System.out.println(“请输入商品的数目n:”);

int n = sc.nextInt();

int[] v = new int[n];

int[] p = new int[n];

System.out.println(“请依次输入商品的体积v:”);

for (int i = 0 ; i < n ; i++) {

v[i] = sc.nextInt();

}

System.out.println(“请依次输入商品的价值p:”);

for (int i = 0 ; i < n ; i++) {

p[i] = sc.nextInt();

}

System.out.println(“请输入背包的容量C:”);

int C = sc.nextInt();

int result = knapsackDP(n , p , v , C);

System.out.println(“得到的总价值最大为(即产生的最优解为):” + result);

}

}

动态规划篇 之 最大子数组问题

内容:

最大子数组:在一个数列中找到一个连续子序列,使得该子序列所有数字之和最大。

算法流程:

伪代码:

复杂度分析:

动态规划思路的最大子数组问题的时间复杂度为O(n),其中n是数组的长度。因为每个子问题只会被计算一次,所有总共有n个子问题需要计算。

import java.util.Scanner;

public class maxSubArray1 {

    public static int[] maxSubarraySum(int[] nums, int n) {

        int[] D = new int[n];           //记录最优解

        int[] Rec = new int[n];         //记录终止位置

        //初始化

        D[n - 1] = nums[n - 1];

        Rec[n - 1] = n-1;

        //动态规划

        //自底向上填最优解D和终止位置Rec的表格

//Rec[i]的填写方法:D[i+1] > 0,填入Rec[i+1]的值;D[i+1] < 0,填入i

        for (int i = n-2 ; i >= 0 ; i--) {

            if (D[i+1] > 0) {

                D[i] = nums[i] + D[i+1];

                Rec[i] = Rec[i+1];

            } else {

                D[i] = nums[i];

                Rec[i] = i;

            }

        }

//查找解

        int maxSum = D[0] , l = 0 , r = 0;

        for (int i = 1 ; i <= n-1 ; i++) {

            if (maxSum < D[i]) {

                maxSum = D[i];

l = i;

                r = Rec[i];

            }

        }

        return new int[] { maxSum , l+1 , r+1 };

}

public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.println("请输入数组的长度n:");

        int n = sc.nextInt();

        int[] nums = new int[n];

System.out.println("请依次输入数组的元素:");

        for (int i = 0 ; i < n ; i++) {

            nums[i] = sc.nextInt();

        }

        int[] maxSum = maxSubarraySum(nums, n);

        System.out.println("最大子数组的和为:" + maxSum[0]);

        System.out.println("最大子数组的起始位置为:" + maxSum[1]);

        System.out.println("最大子数组的终止位置为:" + maxSum[2]);

    }

}

动态规划篇 之 最长公共子序列问题

背景:

子序列:

将给定序列中零个或多个元素(如字符)去掉后所得结果

内容:

最长公共子序列(Longest Common Subsequence,LCS)是指两个序列在某个相同的子序列中所拥有的最长的序列,而子序列不要求在原序列中是连续的。动态规划算法是解决最长公共子序列问题的常见方法。

算法流程:

最终构造的递推公式:

伪代码:

复杂度分析:

动态规划方法解决最长公共子序列问题的时间复杂度为O(mn),其中m和n分别为两个序列的长度。

运行结果:

源代码:

import java.util.*;

public class LongestCommonSubsequence {

    public static char[][] LCS(char[] X, char[] Y, int n, int m) {

        //创建二维数组C[0...n,0...m]和Rec[0...n,0...m]

        int[][] C = new int[n + 1][m + 1];

        char[][] Rec = new char[n + 1][m + 1];

        //初始化

        for (int i = 0; i <= n; i++) {

            C[i][0] = 0;

        }

        for (int j = 0; j <= m; j++) {

            C[0][j] = 0;

        }

        //动态规划   用1代替"LU",用2代替"U",用3代替"L";

        for (int i = 1; i <= n; i++) {

            for (int j = 1; j <= m; j++) {

                if (X[i-1] == Y[j-1]) {

                    C[i][j] = C[i - 1][j - 1] + 1;

                    Rec[i][j] = 1;

                } else if (C[i-1][j] >= C[i][j-1]) {

                    C[i][j] =  C[i-1][j];

                    Rec[i][j] = 2;

                } else {

                    C[i][j] =  C[i][j-1];

                    Rec[i][j] = 3;

                }

            }

        }

        System.out.println("最长公共子序列的长度为:" + C[n][m]);

        return Rec;

    }

    public static String getLCS(char[][] Rec, char[] X, int i, int j){

        StringBuilder sb = new StringBuilder();

        if (i == 0 || j == 0) {

            System.out.println("没有最长公共子序列");

        }

while (i > 0 && j > 0) {

            if (Rec[i][j] == 1) {

                    i--;

                    j--;

                    sb.append(X[i]);

            } else if (Rec[i][j] == 2) {

                    i--;

            } else {

                    j--;

            }

        }

        return sb.reverse().toString();

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.print("请输入数组X的长度n: ");

        int n = sc.nextInt();

        char[] X = new char[n];

        System.out.print("请依次输入数组X的元素:");    // X,测试数据:A B C B D A B

        for (int i = 0 ; i < n ; i++) {

            X[i] = sc.next().charAt(0);

        }

        System.out.print("请输入数组Y的长度m: ");

        int m = sc.nextInt();

        char[] Y = new char[m];

        System.out.print("请依次输入数组Y的元素:");    // Y,测试数据:B D C A B A

        for (int j = 0 ; j < m ; j++) {

            Y[j] = sc.next().charAt(0);

        }

        char[][] rec = LCS(X, Y, n, m);

        System.out.print("最长公共子序列为:");

        System.out.println(getLCS(rec, X, n, m));

    }

}

动态规划篇 之 最长公共子串问题

背景:

内容:

给定两个字符串X和Y,求它们的最长公共子串及其长度。

算法流程:

伪代码:

复杂度分析:

最长公共子串问题的动态规划法的时间复杂度为O(nm),空间复杂度同样为O(nm),其中n和m分别为两个字符串的长度。

源代码:

import java.util.*;

public class LongestCommonSubstring {

    public static int[] longestCommonSubstring(String X, String Y) {

        int n = X.length() , m = Y.length();

        int[][] C = new int[n + 1][m + 1];

        int lmax = 0;    // 最长公共子串长度

        int pmax = 0;    // 最长公共子串末尾位置

        //初始化

        for (int i = 0 ; i < n ; i++) {

            C[i][0] = 0;

        }

        for (int j = 0 ; j < n ; j++) {

            C[0][j] = 0;

        }

        //动态规划

        for (int i = 1 ; i <= n ; i++) {

            for (int j = 1 ; j <= m ; j++) {

                if (X.charAt(i - 1) == Y.charAt(j - 1)) {

                    C[i][j] = C[i - 1][j - 1] + 1;

                    if (lmax < C[i][j]) {

                        lmax = C[i][j];

                        pmax = i - 1;

                    }

} else {

                    C[i][j] = 0;

                }

            }

        }

        return new int[]{lmax , pmax};

    }

    public static void LCS (String X, int lmax, int pmax){

        if (lmax == 0) {

            System.out.println("没有最长公共子串!");

        }

        System.out.print("最长公共子串为:");

        for (int i = (pmax - lmax + 1) ; i <= pmax ; i++) {

            System.out.print(X.charAt(i));

        }

    }

    public static void main(String[] args) {

        // 从键盘读入两个字符串

        Scanner sc = new Scanner(System.in);

        System.out.println("请输入字符串X:");     //测试X:ABCADBB

        String X = sc.next();

        System.out.println("请输入字符串Y:");     //测试Y:BCEDBB

        String Y = sc.next();

        // 求解最长公共子串及其长度

        int[] result = longestCommonSubstring(X, Y);

        int lmax = result[0];

        int pmax = result[1];

        System.out.println("最长公共子串长度为:" + lmax);

        LCS(X, lmax,pmax);

    }

}

动态规划篇 之 钢条切割问题

内容:

给定一段长度为n的钢条和一个价格表p[1...n] ,求切割钢条的最优方案,使得切割后获得的收益最大。

算法流程:

伪代码:

复杂度分析:

动态规划法的钢条切割问题的时间复杂度为O(n^2),空间复杂度为O(n),其中n为钢条的长度。

运行结果:

源代码:

import java.util.Scanner;

public class RodCutting {

    public static void rodCutting(int[] p , int n) {

        int[] C = new int[n+1];

        int[] rec = new int[n+1];

        // 初始化

        C[0] = 0;

        //动态规划

        for (int j = 1 ; j <= n ; j++) {

            int q = p[j-1];     // 不切割

            rec[j] = j;

            for (int i = 1 ; i <= j - 1 ; i++) {

                if (q < p[i-1] + C[j-i]) {

                    q = p[i-1] + C[j-i];

                    rec[j] = i;

                }

            }

            C[j] = q;

        }

        System.out.println("最大收益为:" + C[n]);

        //输出最优方案

        System.out.print("切割方案为:{ ");

        while (n > 0) {

            System.out.print(rec[n] + " ");

            n = n - rec[n];

        }

        System.out.print("}");

    }

public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        System.out.print("请输入钢条的长度n:");             //测试: 10

        int n = sc.nextInt();

        System.out.print("请依次输入钢条价格表p[1...n]:");    //测试: 1 5 8 9 10 17 17 20 24 24

        int[] p = new int[n];

        for (int i = 0; i < n; i++) {

            p[i] = sc.nextInt();

        }

//求最优解

        rodCutting(p , n);

    }

}

动态规划篇 之 矩阵链问题

   

动态规划篇 之 编辑距离问题

衡量序列的相似程度

  

贪心算法篇

             

贪心策略篇 之 部分背包问题

内容:

调制饮品比赛:

算法流程:

伪代码:

复杂度分析:

如果为每个物品都计算性价比并按照性价比从大到小排序,需要 O(nlogn) 的时间复杂度。然后,遍历一遍排序后的数组,对每个物品进行选择/放弃(或者选择部分)的操作,这部分的时间复杂度为 O(n)。

因此,总时间复杂度为O(nlogn)+O(n)=O(nlogn)。

运行结果:

源代码:

import java.util.Arrays;

import java.util.Comparator;

import java.util.Scanner;

public class FractionlKnapsack {

    // 贪心算法实现 部分背包问题

    // 输入:商品数量n , 各商品的价值p , 各商品的体积v , 背包容量C

// 输出:商品价格的最大值,最优解方案

private static void knapsack(int n, double[] p, double[] v, int C) {

        // 计算单位体积价值

        double[] indices = new double[n];

        for (int i = 0; i < n; i++) {

            indices[i] = p[i] / v[i];

        }

// 按照性价比降序排序

        Double[] Ratio = new Double[n];

        for (int i = 0; i < n; i++) {

            Ratio[i] = indices[i];

        }

        Arrays.sort(Ratio, Comparator.reverseOrder());

        int i = 0;

        double ans = 0;

        // 根据贪心策略求解

        while (C > 0 && i < n) {

            if (v[i] <= C) {

                System.out.println("选择商品" + (i+1));

                ans += p[i];

                C -= v[i];

            } else {

                System.out.println("选择" + C + "体积的商品" + (i+1));

                ans += p[i] * (C / v[i]);

                C = 0;

            }

            i++;

        }

        System.out.print("总价格为:" + ans);

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.print("请输入商品的数目n:");

        int n = sc.nextInt();

        double[] v = new double[n];

        double[] p = new double[n];

        System.out.print("请依次输入商品的体积v:");

        for (int i = 0; i < n; i++) {

            v[i] = sc.nextInt();

        }

        System.out.print("请依次输入商品的价值p:");

        for (int i = 0; i < n; i++) {

            p[i] = sc.nextInt();

        }

        System.out.print("请输入背包的容量C:");

        int C = sc.nextInt();

        knapsack(n, p, v, C);

    }

}

System.out.print("请输入背包的容量C:");

        int C = sc.nextInt();

        knapsack(n, p, v, C);

    }

}

动态规划的0/1背包和贪心法的部分背包问题的比较:

贪心策略篇 之 霍夫曼编码问题

内容:

对于一个给定的字符集,霍夫曼编码是一种使用变长编码表来将每个字符编码为比特串的方式。编码的长度与字符出现的频率有关,出现频率越高的字符编码长度越短,反之则编码长度越长。

贪心算法可以用来构造霍夫曼编码树,其基本思路是首先将字符出现的频率作为结点的初始权值,然后每次选择两个权值最小的结点并将它们合并为一个新结点,直到所有的结点被合并为一棵树为止。在这个过程中,新结点的权值为它所包含的两个子结点的权值之和。

最终构造出的霍夫曼编码树是一棵无回路的树(也称为无环树),每个叶子结点表示一个字符并给出该字符的编码。

构造出霍夫曼编码树后,可以通过从根结点开始遍历的方式来确定每个字符的编码。遍历左子树时添加一个 “0”,遍历右子树时添加一个 “1”,直到遇到一个叶子结点。对于每个字符,它的编码就是到达它的路径上的比特串。

算法流程:

伪代码:

复杂度分析:

贪心算法的优点是速度快,时间复杂度为 O(nlogn),其中 n 是字符集的大小。缺点是它只能得到一个局部最优解,而无法保证一定得到全局最优解。

运行结果:

伪代码:

import java.util.*;

// 记录节点信息

class Node implements Comparable {

    char c;            // 字符

    double F;          // 出现概率

Node left, right;  // 左右子节点

public Node(char c, double F) {

        this.c = c;

        this.F = F;

    }

@Override

    public int compareTo(Object other) {

        return Double.compare(this.F, ((Node)other).F);

    }

}

public class Huffman {

    // 数组chars中每个字符出现的概率存放在数组F中,函数返回对应的霍夫曼编码

    public static String[] encode(char[] chars, double[] F) {

        int n = chars.length;

        // 将char和概率信息保存到Nodes中

        Node[] Nodes = new Node[n];

        for (int i = 0; i < n; i++) {

            Nodes[i] = new Node(chars[i], F[i]);

        }

        // 构造霍夫曼树

        Queue<Node> pq = new PriorityQueue<Node>();

        for (int i = 0; i < n; i++) {

            pq.offer(Nodes[i]);

        }

        while (pq.size() > 1) {

            //弹出两个概率最小的节点

            Node left = pq.poll(), right = pq.poll();

            // 构造新节点

            Node parent = new Node('\0', left.F + right.F);

            parent.left = left;

            parent.right = right;

            pq.offer(parent);

        }

        Node root = pq.poll();    // 最后剩下唯一的节点,即霍夫曼树的根

        String[] codes = new String[n];    // 保存每个字符的霍夫曼编码

        if (n == 1) {

            codes[0] = "0";

        } else {

            assignCode(root, "", codes);    // 从霍夫曼树的根开始递归地生成编码

        }

        return codes;

    }

  

   

private static void assignCode(Node node, String code, String[] codes) {

        if (node.c != '\0') {    // 叶子节点表示一个字符

            codes[node.c - 'a'] = code;

        } else { // 非叶子节点,递归搜索左右子树

            assignCode(node.left, code + "0", codes);

            assignCode(node.right, code + "1", codes);

        }

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.print("请输入字符个数n:");

        int n = sc.nextInt();

        char[] chars = new char[n];

        double[] F = new double[n];

        System.out.print("请依次输入字符:");

        for (int i = 0 ; i < n ; i++) {

            chars[i] = sc.next().charAt(0);

        }

        System.out.print("请依次输入各字符频数:");

        for (int i = 0 ; i < n ; i++) {

            F[i] = sc.nextDouble();

        }

        String[] codes = encode(chars, F);

        for (int i = 0; i < chars.length; i++) {

            System.out.println(chars[i] + " : " + codes[i]);

        }

    }

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/726341.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Linux服务器挖矿病毒处理

文章目录 Linux服务器挖矿病毒处理1.中毒表现2.解决办法2.1 断网并修改root密码2.2 找出隐藏的挖矿进程2.3 关闭病毒启动服务2.4 杀掉挖矿进程 3. 防止黑客再次入侵3.1 查找异常IP3.2 封禁异常IP3.3 查看是否有陌生公钥 补充知识参考 Linux服务器挖矿病毒处理 情况说明&#x…

echarts dataZoom用按钮代替鼠标滚轮实现同样效果

2024.06.19今天我学习了echarts dataZoom如何用按钮来控制放大缩小的功能&#xff0c; 效果如下&#xff1a; 通过控制按钮来实现图表放大缩小数据的效果。 步骤如下&#xff1a; 一、写缩放按钮&#xff0c;以及图表数据。 二、设置初始位置的变量&#xff0c;我这边是七个…

InPixio Photo Cutter v10 解锁版安装教程 (懒人抠图工具)

前言 InPixio Photo Cutter是一款懒人抠图工具&#xff0c;采用了增强的算法切割技术&#xff0c;可以在不影响图像质量的情况下&#xff0c;允许用户从照片中删除任何物体或人物&#xff0c;并且保持其完整的质量。你只需点击几下鼠标&#xff0c;便可从照片中剪下任何细节、…

上位机图像处理和嵌入式模块部署(h750 mcu中的pwm控制)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 所谓的pwm&#xff0c;其实就是方波。我们都知道&#xff0c;对于一个电机来说&#xff0c;如果插上正负极的话&#xff0c;那么电机就会全速运转。…

C#.Net筑基-集合知识全解

01、集合基础知识 .Net 中提供了一系列的管理对象集合的类型&#xff0c;数组、可变列表、字典等。从类型安全上集合分为两类&#xff0c;泛型集合 和 非泛型集合&#xff0c;传统的非泛型集合存储为Object&#xff0c;需要类型转。而泛型集合提供了更好的性能、编译时类型安全…

spring cloud Alibaba 整合 seata AT模式

准备工作&#xff1a; 1、MySQL正常安装并启动 2、nacos正常部署并启动 3、下载 Seata-1.4.2 源码包和 seata-server-1.4.2 服务端源码包&#xff08;版本根据自己的需要选择&#xff0c;我这里选择1.4.2&#xff09; 下载地址&#xff1a; Seata&#xff1a;https://gite…

PFA托盘400*300*42mm耐酸碱透明聚四氟乙烯方盘方槽耐高温厂家供

PFA方盘又称托盘&#xff1a;耐高温、耐腐蚀。 进口透明可溶性聚四氟乙烯方盘。可应用于成膜实验&#xff0c;样品液体脱漏等。能放在电热板上直接加热使用&#xff0c;也可以用于烘箱烘干&#xff0c;实验室腐蚀性样品的转移和搬运&#xff0c;防止腐蚀性液体洒落。 产品特性…

计算机网络 —— 应用层(FTP)

计算机网络 —— 应用层&#xff08;FTP&#xff09; FTP核心特性&#xff1a;运作流程&#xff1a; FTP工作原理主动模式被动模式 我门今天来看应用层的FTP&#xff08;文件传输协议&#xff09; FTP FTP&#xff08;File Transfer Protocol&#xff0c;文件传输协议&#x…

sprintboot依赖管理和自动配置

springboot依赖管理和自动配置 依赖管理和自动配置依赖管理什么是依赖管理修改自动仲裁/默认版本号 starter场景启动器starter场景启动器基本介绍官方提供的starter第三方starter 自动配置自动配置基本介绍SpringBoot自动配置了哪些?如何修改默认配置如何修改默认扫描包结构re…

基于SSM的足球联赛管理系统

文章目录 项目介绍主要功能截图&#xff1a;部分代码展示设计总结项目获取方式 &#x1f345; 作者主页&#xff1a;超级无敌暴龙战士塔塔开 &#x1f345; 简介&#xff1a;Java领域优质创作者&#x1f3c6;、 简历模板、学习资料、面试题库【关注我&#xff0c;都给你】 &…

南开大学漏洞报送证书【文尾有福利】

证书介绍 获取来源&#xff1a;edusrc&#xff08;教育漏洞报告平台&#xff09; url&#xff1a;教育漏洞报告平台(EDUSRC) 兑换价格&#xff1a;30金币​ 获取条件&#xff1a;南开大学任意中危或以上级别漏洞 证书规格&#xff1a;证书做了木框装裱&#xff0c;显得很高…

查看电脑支持的CUDA安装版本与显卡驱动更新

说明&#xff1a; torch版本依赖于CUDA版本与Python版本 Start Locally | PyTorchCUDA版本依赖于显卡驱动版本 1. CUDA 12.5 Release Notes — Release Notes 12.5 documentation 显卡驱动版本依赖于显卡型号与电脑系统 当前电脑3060显卡&#xff0c;安装了CUDA V11.6与torc…

python-画正方形

[题目描述] 输入一个正整数n&#xff0c;要求输出一个n行n列的正方形图案&#xff08;参考样例输入输出&#xff09;。图案由大写字母组成。 其中&#xff0c;第1行以大写字母A开头&#xff0c;第2行以大写字母B开头&#xff0c;以此类推&#xff1b;在每行中&#xff0c;第2列…

使用ASM动态创建接口实现类

使用ASM动态生成一个接口的实现类&#xff0c;接口如下&#xff1a; public interface ISayHello {public void MethodA();public void MethodB();public void Abs(); } 具体实现如下&#xff1a; public class InterfaceHandler extends ClassLoader implements Opcodes {pu…

DV、OV通配符SSL证书有什么区别

通配符SSL证书是经常提及的一种SSL证书类型&#xff0c;也被称为泛域名SSL证书。通配符证书在SSL证书当中是比较特殊的&#xff0c;它具有保护主域名及其下一级所有子域名的功能&#xff0c;非常适合子域名多的域名网站&#xff0c;能够有效的节省成本&#xff0c;并降低证书管…

iis下asp.netcore后台定时任务会取消

问题 使用BackgroundService或者IHostedService做后台定时任务的时候部署到iis会出现不定时定时任务取消的问题&#xff0c;原因是iis会定时的关闭网站 解决 应用程序池修改为AlwaysRunning 修改web.config <?xml version"1.0" encoding"utf-8"?…

研究Redis源码的一些前期准备

一 背景 Redis数据结构讲完后&#xff0c;觉得还是有点不过瘾&#xff0c;想研究一下Redis的底层实现。找了一些相关资料&#xff0c;准备借鉴和学习其他各位大佬钻研Redis底层的方法和经验&#xff0c;掌握Redis实现的基本原理。 二 源码归类 网上有大佬已经总结了…

内网穿透方法有哪些?路由器端口映射外网和软件方案步骤

公网IP和私有IP不能互相通讯。我们通常在局域网内部署服务器和应用&#xff0c;当需要将本地服务提供到互联网外网连接访问时&#xff0c;由于本地服务器本身并无公网IP&#xff0c;就无法实现。这时候就需要内网穿透技术&#xff0c;即内网映射&#xff0c;内网IP端口映射到外…

视频服务网关的特点

一、视频服务网关的介绍 视频服务网关采用Linux操作系统&#xff0c;可支持国内外不同品牌、不同协议、不同设备类型监控产品的统一接入管理&#xff0c;同时提供标准的H5播放接口供其他应用平台快速对接&#xff0c;让您快速拥有视频集成能力。不受开发环境、跨系统跨平台等条…

全新量子计算技术!在硅中可以生成大规模量子比特

内容来源&#xff1a;量子前哨&#xff08;ID&#xff1a;Qforepost&#xff09; 文丨沛贤/浪味仙 排版丨沛贤 深度好文&#xff1a;1600字丨6分钟阅读 摘要&#xff1a;研究人员利用气体环境在硅中形成被称为“色心”的可编程缺陷&#xff0c;首次利用飞秒激光&#xff0c;…