• 注册
  • 赞助本站

    • 支付宝
    • 微信
    • QQ

    感谢一直支持本站的所有人!

    • 查看作者
    • 《算法第四版》课后练习题1.1.11-1.1.20答案

      习题1.1.11

      编写一段代码,打印出一个二维布尔数组的内容。其中,使用 * 表示真,空格表示假。打印出行号和列号。

      参考答案

      public class Test {
          public static void printBooleanMatrix(boolean[][] b) {
              for (int i = 0; i < b.length; i++) {
                  for (int j = 0; j < b[i].length; j++) {
                      System.out.print((i + 1) + " 行 " + (j + 1) + " 列  :");
                      System.out.println(b[i][j] == true ? "*" : " ");
                  }
              }
          }
          public static void main(String[] args) {
              boolean[][] b = new boolean[][]{{true, false, false}, {true, true, true}};
              printBooleanMatrix(b);
          }
      }
      输出:
      1 行 1 列  :*
      1 行 2 列  : 
      1 行 3 列  : 
      2 行 1 列  :*
      2 行 2 列  :*
      2 行 3 列  :*

       


      习题1.1.12

      以下代码段会打印出什么结果?

              int[] a = new int[10];
              for (int i = 0; i < 10; i++)
                  a[i] = 9 - i;
              for (int i = 0; i < 10; i++)
                  a[i] = a[a[i]];
              for (int i = 0; i < 10; i++)
                  System.out.println(i);

      参考答案

      0

      1

      2

      3

      4

      5

      6

      7

      8

      9

      不过大多数都认为这里应该是印刷错误,作者的本意应该输出的不是i的值,而是a[i]的值。则答案如下:

      0

      1

      2

      3

      4

      4

      3

      2

      1


      习题1.1.13 

      编写一段代码,打印出一个 M 行 N 列的二维数组的转置(交换行和列)。

      参考答案

      public class Test {
          public static void transposedMatrix(int[][] a) {
              for (int i = 0; i < a[0].length; i++) {
                  for (int j = 0; j < a.length; j++) {
                      System.out.print(a[j][i] + "  ");
                  }
                  System.out.println();
              }
          }
          public static void printMatrix(int[][] a) {
              for (int i = 0; i < a.length; i++) {
                  for (int j = 0; j < a[0].length; j++) {
                      System.out.print(a[i][j] + "  ");
                  }
                  System.out.println();
              }
          }
          public static void main(String[] args) {
              int[][] a = {{1, 2, 3}, {4, 5, 6}};
              System.out.println("原始数组 :");
              transposedMatrix(a);
              System.out.println("置换结果:");
              printMatrix(a);
          }
      }
      输出:
              
      原始数组 :
              1  4
              2  5
              3  6
      置换结果:
              1  2  3
              4  5  6

       


      习题1.1.14

      编写一个静态方法 lg(),接受一个整型参数 N,返回不大于 log2N 的最大整数。不要使用 Math 库。

      参考答案

      解法一:

      public class Test {
          public static int lg(int n) {
              int i = 2;
              int j = 0;
              while (true) {
                  i *= 2;
                  j++;
                  if (i >= n) {
                      return j;
                  }
              }
          }
          public static void main(String[] args) {
              System.out.println(lg(23));
          }
      }
      输出:
              4
              4
              4

      解法二:

          //Kyson版本
          public static int lg(int N) {
              int product = 1;
              int x = -1;
              while (product <= N) //*,把等于的情况也纳入进来,从而避免了在如23>5这种情况的自增导致输出结果为3的情况
              {
                  product *= 2;
                  x++;
              }
              return x;
          }

      摘自Kyson博客

      解法三:

          //Jimmy Sun版本
          public static int lg(int n) {
              int shiftRightCount = 0;
              do {
                  n >>= 1;
                  shiftRightCount++;
              } while (n != 0);
              return shiftRightCount - 1;
          }

      摘自Jimmy SunGitHub


       


      习题1.1.15

      编写一个静态方法 histogram(),接受一个整型数组 a[] 和一个整数 M 为参数并返回一个大小为 M 的数组,其中第 i 个元素的值为整数 i 在参数数组中出现的次数。如果 a[] 中的值均在 0 到 M-1之间,返回数组中所有元素之和应该和 a.length 相等。

      参考答案

      public class Test {
          public static int[] histogram(int[] a, int M) {
              int[] r = new int[M];
              for (int i = 0; i < a.length; i++) {
                  if (a[i] < M) { //防止数组a中元素大于M后,发生越界错误
                      r[a[i]]++;
                  }
              }
              return r;
          }
          public static void print(int[] b, int a) {
              int sum = 0;
              for (int i : b) {
                  sum += i;
                  System.out.print(i + " ");
              }
              System.out.println("\n返回数组中所有元素的和a.length是否相等?" + (sum == a ));
          }
          public static void main(String[] args) {
              int[] a = {1, 1, 1, 2, 2, 2, 3, 3, 5, 6, 7, 9, 9, 9, 9};
              print(histogram(a, 10), a.length);
          }
      }
      输出:
      0 3 3 2 0 1 1 1 0 4
      返回数组中所有元素的和a.length是否相等?true


       


      习题1.1.16

      给出 exR1(6) 的返回值

      public static String exR1(int n)
      {
         if (n <= 0) return "";
         return exR1(n-3) + n + exR1(n-2) + n;
      }

      参考答案

      311361142246


      习题1.1.17

      找出以下递归函数的问题:

      public static String exR2(int n) {
          String s = exR2(n - 3) + n + exR2(n - 2) + n;
          if (n <= 0) return "";
          return s;
      }

      参考答案

      该方法将会一直不停的调用本身,if语句永远不可能执行,直到运行的时候栈的深度超过了虚拟机容许的最大深度,将抛出 StackOverflowError 异常


      习题1.1.18

      请看以下递归函数:

          public static int mystery(int a, int b) {
              if (b == 0) return 0;
              if (b % 2 == 0) return mystery(a + a, b / 2);
              return mystery(a + a, b / 2) + a;
          }

      mystery(2, 25) 和 mystery(3, 11) 的返回值是多少?

      给定正整数 a 和 b,mystery(a,b)计算的结果是什么?

      将代码中的 + 替换为 * 并将 return 0 改为 return 1,然后回答相同的问题。

      参考答案

      测试类:

      public class Test {
          public static int mystery(int a, int b) {
              if (b == 0) return 0;
              if (b % 2 == 0) return mystery(a + a, b / 2);
              return mystery(a + a, b / 2) + a;
          }
          public static int mystery2(int a, int b) {
              if (b == 0) return 1;
              if (b % 2 == 0) return mystery2(a * a, b / 2);
              return mystery2(a * a, b / 2) * a;
          }
          public static void main(String[] args) {
              System.out.println(mystery(2,25));
              System.out.println(mystery(3,11));
              System.out.println(mystery2(2,25));
              System.out.println(mystery2(3,11));
          }
      }

      mystery(2,25):输出50

      mystery(3,11):输出33

      mystery2(2,25):输出33554432

      mystery2(3,11):输出177147


      习题1.1.19

      在计算机上运行以下程序:

              public class Fibonacci {
                  public static long F(int N) {
                      if (N == 0) return 0;
                      if (N == 1) return 1;
                      return F(N - 1) + F(N - 2);
                  }
                  public static void main(String[] args) {
                      for (int N = 0; N < 100; N++)
                          StdOut.println(N + " " + F(N));
                  }
              }

      计算机用这段程序在一个小时之内能够得到 F(N) 结果的最大 N 值是多少?开发 F(N) 的一个更好的实现,用数组保存已经计算过的值。

      参考答案

      因时间限制,这里以一分钟为例,一分钟程序跑出的结果如下:

      (受到电脑配置的影响一分钟内最大结果可能有所不同)

      0 0
      1 1
      2 1
      3 2
      4 3
      5 5
      6 8
      7 13
      8 21
      9 34
      10 55
      11 89
      12 144
      13 233
      14 377
      15 610
      16 987
      17 1597
      18 2584
      19 4181
      20 6765
      21 10946
      22 17711
      23 28657
      24 46368
      25 75025
      26 121393
      27 196418
      28 317811
      29 514229
      30 832040
      31 1346269
      32 2178309
      33 3524578
      34 5702887
      35 9227465
      36 14930352
      37 24157817
      38 39088169
      39 63245986
      40 102334155
      41 165580141
      42 267914296
      43 433494437
      44 701408733
      45 1134903170
      46 1836311903
      47 2971215073

       F(N) 更好的实现方法(用数组保存已经计算过的值):

      import edu.princeton.cs.algs4.StdOut;
      public class Test {
          public static long F(int N, long[] a) {
              if (N == 0) {
                  return a[0] = 0;
              }
              if (N == 1) {
                  return a[1] = 1;
              }
              return a[N] = a[N - 1] + (a[N - 2]);
          }
          public static void main(String[] args) {
              long[] a = new long[100];
              for (int N = 0; N < 100; N++)
                  StdOut.println(N + " " + F(N, a));
          }
      }

      由于long只能表示-9223372036854775808~9223372036854775807之间(2^64 ~ 2^64  – 1)的数

      所以该题的答案会超出范围,可以采用BigInteger来解决该问题

      public class Test {
          public static BigInteger F(int N, BigInteger[] a) {
              if (N == 0) {
                  return a[0] = BigInteger.valueOf(0);
              }
              if (N == 1) {
                  return a[1] = BigInteger.valueOf(1);
              }
              return a[N] = a[N - 1].add(a[N - 2]);
          }
          public static void main(String[] args) {
              BigInteger[] a = new BigInteger[100];
              for (int N = 0; N < 100; N++)
                  StdOut.println(N + " " + F(N, a));
          }
      }


       


      习题1.1.20

      编写一个递归的静态方法计算 ln(N!) 的值。

      感谢@onepiece指出本文的错误,一开始没有使用递归

      参考答案

      public class Test {
          public static double ln(int N) {
              if (N == 1 || N == 0) return 0;
              else return ln(N - 1) + Math.log(N);//Java中Math.log()默认以e为底
          }
          public static void main(String[] args) {
              System.out.println(ln(3)); //ln(6)的阶乘
          }
      }
      输出:
      1.791759469228055
    • 0
    • 3
    • 0
    • 4.4k
    • 请登录之后再进行评论

      登录
    • 0
      @张甲 不好意思,看错了。不太熟悉Java。 [s-11]
    • 0
      张甲46站长
      @我有大宝贝 嗯?是哪一行代码呢
    • 0
      1.1.13的transposedMatrix是不是笔误了。 [s-29]
    • 单栏布局 侧栏位置: