期末考试算法复习

骑猪看日落 2021-12-16 01:25 461阅读 0赞

题目如下：

1、求阶乘

2、字符逆序输出

3、FJ的字符串

4、数塔问题

5、最长公共子序列问题

6、N皇后问题

7、铺瓷砖问题

8、01背包问题

1、求阶乘

编写程序计算N! 要求使用递归算法和普通循环算法分别实现

  1. 1 public class 阶乘 {
  2.  2     
  3.  3     public static int NoRecur(int n){
  4.  4         int res = 1;
  5.  5         for(int i=1; i<=n; i++){
  6.  6             res *= i;
  7.  7         }
  8.  8         
  9.  9         return res;
  10. 10     }
  11. 11     
  12. 12     public static int Recur(int n){
  13. 13         if(n==1){
  14. 14             return 1;
  15. 15         }
  16. 16         return n * Recur(n - 1);
  17. 17     }
  18. 18     
  19. 19     public static void main(String[] args) {
  20. 20         System.out.println(NoRecur(1));
  21. 21         System.out.println(Recur(1));
  22. 22         System.out.println(NoRecur(3));
  23. 23         System.out.println(Recur(3));
  24. 24         System.out.println(NoRecur(5));
  25. 25         System.out.println(Recur(5));
  26. 26     }
  27. 27     
  28. 28 }

2、字符逆序输出

  1. 1 import java.util.Scanner;
  2.  2 
  3.  3 public class 字符逆序输出 {
  4.  4     
  5.  5     // 递归实现逆序输出
  6.  6     public static void reverseStr(char[] chs, int i) {
  7.  7         
  8.  8         if(i == chs.length) {
  9.  9             return;
  10. 10         }
  11. 11         reverseStr(chs, i+1);
  12. 12         System.out.print(chs[i]);
  13. 13         
  14. 14     }
  15. 15     
  16. 16     // 非递归实现逆序输出
  17. 17     public static void reverseStr2(char[] chs) {
  18. 18         
  19. 19         for(int i=chs.length-1; i>=0; i--) {
  20. 20             System.out.print(chs[i]);
  21. 21         }
  22. 22         System.out.println();
  23. 23     }
  24. 24     
  25. 25     public static void main(String[] args) {
  26. 26         
  27. 27         System.out.println("Input: ");
  28. 28         Scanner input = new Scanner(System.in);
  29. 29         String str = input.nextLine();
  30. 30         reverseStr(str.toCharArray(), 0);
  31. 31         System.out.println();
  32. 32         reverseStr2(str.toCharArray());
  33. 33         
  34. 34     }
  35. 35     
  36. 36 }

3、FJ的字符串

FJ在沙盘上写了这样一些字符串：

A1 = “A” A2 = “ABA” A3 = “ABACABA” A4 = “ABACABADABACABA” … … 　　你能找出其中的规律并写所有的数列AN吗？

输入格式 　仅有一个数：N ≤ 26。

输出格式 请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

样例输入 3

样例输出 ABACABA

  1. 1 import java.util.Scanner;
  2.  2 
  3.  3 public class FJ的字符串 {
  4.  4 
  5.  5     public static void f(int n) {
  6.  6         if (n == 0) {
  7.  7             return;
  8.  8         } else {
  9.  9             f(n - 1);
  10. 10             char c = (char) ('A' + n - 1);
  11. 11             System.out.print(c);
  12. 12             f(n - 1);
  13. 13         }
  14. 14 
  15. 15     }
  16. 16 
  17. 17     public static void main(String[] args) {
  18. 18         
  19. 19         System.out.println("Input: ");
  20. 20         Scanner input = new Scanner(System.in);
  21. 21         int n = input.nextInt();
  22. 22         f(n);
  23. 23         System.out.println();
  24. 24     }
  25. 25 
  26. 26 }

4、数塔问题

有如图所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大

1259476-20190615193124124-150814986.png

  1. 1 public class 数塔问题 {
  2.  2 
  3.  3     public static void main(String[] args) {
  4.  4         int[][] dp = new int[5][5];
  5.  5         dp[0][0] = 9;
  6.  6         dp[1][0] = 12; dp[1][1] = 15;
  7.  7         dp[2][0] = 10; dp[2][1] = 6; dp[2][2] = 8;
  8.  8         dp[3][0] = 2; dp[3][1] = 18; dp[3][2] = 9; dp[3][3] = 5;
  9.  9         dp[4][0] = 19; dp[4][1] = 7; dp[4][2] = 10; dp[4][3] = 4; dp[4][4] = 16;
  10. 10         for (int i = 3; i >= 0; i--) {
  11. 11             for (int j = 0; j <= i; j++) {
  12. 12                 dp[i][j] += Math.max(dp[i + 1][j], dp[i + 1][j + 1]);
  13. 13             }
  14. 14         }
  15. 15         System.out.println(dp[0][0]);
  16. 16     }
  17. 17 
  18. 18 }

5、最长公共子序列问题

设有两个序列X=(x1,x2,…,x7)=(a,b,c,b,d,a,b)和Y=(y1,y2,…,y6)=(b,d,c,a,b,a)。

求它们的最长公共子序列。

  1. 1 public class 最长公共子序列问题 {
  2.  2 
  3.  3     public static void main(String[] args) {
  4.  4 
  5.  5         String str1 = "abcbdab";
  6.  6         String str2 = "bdcaba";
  7.  7         int str1Len = str1.length();
  8.  8         int str2Len = str2.length();
  9.  9         int[][] dp = new int[str1.length() + 1][str2.length() + 1];
  10. 10         for (int i = 1; i <= str1Len; i++) {
  11.     // 构造一个LCS长度数组
  12. 11             for (int j = 1; j <= str2Len; j++) {
  13. 12                 if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
  14.     // 对应公式第二条相等
  15. 13                     dp[i][j] = dp[i - 1][j - 1] + 1;
  16. 14                 } else {
  17.     // 对应公式第三条不相等
  18. 15                     dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
  19. 16                 }
  20. 17             }
  21. 18         }
  22. 19         
  23. 20         // 反推结果
  24. 21         int i = str1Len;
  25. 22         int j = str2Len;
  26. 23         StringBuffer sb = new StringBuffer();
  27. 24         while (i > 0 && j > 0) {
  28. 25             if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
  29. 26                 sb.append(str1.charAt(i - 1));
  30. 27                 i--;
  31. 28                 j--;
  32. 29             } else {
  33. 30                 if (dp[i][j - 1] > dp[i - 1][j]) {
  34. 31                     j--;
  35. 32 
  36. 33                 } else if (dp[i][j - 1] < dp[i - 1][j]) {
  37. 34                     i--;
  38. 35                 } else if (dp[i][j - 1] == dp[i - 1][j]) {
  39. 36                     i--;
  40. 37                 }
  41. 38             }
  42. 39         }
  43. 40         
  44. 41         System.out.println(sb.reverse().toString());
  45. 42 
  46. 43     }
  47. 44 
  48. 45 }

6、N皇后问题

在一个n*n的国际象棋棋盘上放置n个皇后，使得它们中任意2个之间都不互相“攻击”，即任意2个皇后不可在同行、同列、同斜线上。

输入N，求N皇后问题的所有放法

  1. 1 import java.util.Scanner;
  2.  2 
  3.  3 public class N皇后问题 {
  4.  4 
  5.  5     public static int total;
  6.  6     public static int n;
  7.  7 
  8.  8     public static boolean check(int row, int col, int[][] array) {
  9.  9         // 判断是否放置正确
  10. 10         for (int i = 0; i < n; i++) {
  11. 11             if (i != col && array[row][i] == 1) {
  12. 12                 return false;
  13. 13             }
  14. 14             if (i != row && array[i][col] == 1) {
  15. 15                 return false;
  16. 16             }
  17. 17             for (int j = 0; j < n; j++) {
  18. 18                 if (i != row && j != col && array[i][j] == 1 && Math.abs((row - i) / (col - j)) == 1) {
  19. 19                     return false;
  20. 20                 }
  21. 21             }
  22. 22         }
  23. 23 
  24. 24         return true;
  25. 25     }
  26. 26 
  27. 27     public static void queen(int row, int[][] array) {
  28. 28 
  29. 29         if (row == n) {
  30. 30             total++;
  31. 31             // 输出最后结果
  32. 32             for (int i = 0; i < n; i++) {
  33. 33                 for (int j = 0; j < n; j++) {
  34. 34                     if (array[i][j] == 1) {
  35. 35                         System.out.print("Q");
  36. 36                     } else {
  37. 37                         System.out.print("X");
  38. 38                     }
  39. 39                 }
  40. 40                 System.out.println();
  41. 41             }
  42. 42             System.out.println("**********");
  43. 43         } else {
  44. 44             for (int col = 0; col < n; col++) {
  45. 45                 if (check(row, col, array)) {
  46. 46                     array[row][col] = 1;
  47. 47                     queen(row + 1, array);
  48. 48                     array[row][col] = 0;
  49. 49                 }
  50. 50             }
  51. 51         }
  52. 52 
  53. 53     }
  54. 54 
  55. 55     public static void main(String[] args) {
  56. 56 
  57. 57         Scanner input = new Scanner(System.in);
  58. 58         System.out.println("Input: ");
  59. 59         n = input.nextInt();
  60. 60         int[][] array = new int[n][n];
  61. 61         queen(0, array);
  62. 62         System.out.println(total);
  63. 63     }
  64. 64 
  65. 65 }

7、铺瓷砖问题

有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？

例如，长度为4的地面一共有如下5种铺法：

4=1+1+1+1、4=2+1+1、4=1+2+1、4=1+1+2、4=2+2

输入格式 只有一个数N，代表地板的长度

输出格式 输出一个数，代表所有不同的瓷砖铺放方法的总数

样例输入 4

样例输出 5

  1. 1 import java.util.Scanner;
  2.  2 
  3.  3 public class 铺瓷砖问题 {
  4.  4 
  5.  5     public static int n;
  6.  6     public static int res;
  7.  7 
  8.  8     public static void f(int t) {
  9.  9 
  10. 10         if (t == n) {
  11. 11             res++;
  12. 12             return;
  13. 13         }
  14. 14 
  15. 15         if (t + 1 <= n) {
  16. 16             f(t + 1);
  17. 17         }
  18. 18         if (t + 2 <= n) {
  19. 19             f(t + 2);
  20. 20         }
  21. 21     }
  22. 22 
  23. 23     public static void main(String[] args) {
  24. 24         Scanner input = new Scanner(System.in);
  25. 25         System.out.println("Input: ");
  26. 26         n = input.nextInt();
  27. 27         f(0);
  28. 28         System.out.println(res);
  29. 29 
  30. 30     }
  31. 31 
  32. 32 }

8、01背包问题

问题描述：有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

换个说法如下：

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处

都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。

如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式：

第一行有 2个整数T(1≤T≤1000) 和 M(1≤M≤100) ，用一个空格隔开， T 代表总共能够用来采药的时间， M 代表山洞里的草药的数目。
接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100 ）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式：

1个整数，表示在规定的时间内可以采到的草药的最大总价值。

输入
70 3
71 100
69 1
1 2
输出
3

  1. 1 import java.util.*;
  2.  2 
  3.  3 public class _01背包问题 {
  4.  4 
  5.  5     public static void main(String[] args) {
  6.  6         Scanner in = new Scanner(System.in);
  7.  7         System.out.println();
  8.  8         int T = in.nextInt();    // 采药的时间
  9.  9         int M = in.nextInt();    // 采药的数目
  10. 10         int[][] arr = new int[M + 1][2];
  11. 11         for (int i = 1; i <= M; i++) {
  12. 12             arr[i][0] = in.nextInt();    // 时间
  13. 13             arr[i][1] = in.nextInt();    // 价值
  14. 14         }
  15. 15         int[][] dp = new int[M + 1][T + 1];
  16. 16         for (int i = 1; i <= M; i++) {
  17. 17             for (int j = 0; j <= T; j++) {
  18. 18                 if (j < arr[i][0])
  19. 19                     dp[i][j] = dp[i - 1][j];
  20. 20                 else
  21. 21                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - arr[i][0]] + arr[i][1]);
  22. 22             }
  23. 23         }
  24. 24         System.out.println(dp[M][T]);
  25. 25     }
  26. 26 
  27. 27 }

转载于:https://www.cnblogs.com/wyb666/p/11028266.html

发表评论

表情：
评论列表 （有 0 条评论，461人围观）

还没有评论，来说两句吧...

相关阅读

    相关 免疫考试 期末复习

    一、 简述免疫系统组成及主要功能： 免疫系统由免疫组织和器官、免疫细胞和免疫分子组成。 1.免疫器官： ① 中枢免疫器官：骨髓、腔上囊（禽类）、胸腺；是免疫细胞发生、分

    水深无声水深无声/ 0 赞/ 143 阅读