期末考试算法复习

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

题目如下：

1、求阶乘

2、字符逆序输出

3、FJ的字符串

4、数塔问题

5、最长公共子序列问题

6、N皇后问题

7、铺瓷砖问题

8、01背包问题

**1、求阶乘**

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

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

**2、字符逆序输出**

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

**3、FJ的字符串**

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

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

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

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

样例输入  3

样例输出  ABACABA

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

**4、数塔问题**

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

![1259476-20190615193124124-150814986.png][]

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

**5、最长公共子序列问题**

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

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

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

**6、N皇后问题**

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

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

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

** **

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

[1259476-20190615193124124-150814986.png]: /images/20211215/c87d833a75e749a9bd271870422ff800.png