[关闭]
@natsumi 2016-04-15T07:40:43.000000Z 字数 4946 阅读 1373

算法(第四版)第1章部分习题

Algorithms


1.1.19 修改后的fibonacci

F(93)及之后的会溢出

  1. import io.StdOut;
  2. public class Test {
  3. public static long[] fibonacci=new long[100];
  4. public static long F(int N){
  5. if(N==0) fibonacci[N]=0;
  6. else if(N==1) fibonacci[N]=1;
  7. else if(fibonacci[N-1]!=0){
  8. fibonacci[N]=fibonacci[N-1]+fibonacci[N-2];
  9. }else{
  10. fibonacci[N]=F(N-1)+F(N-2);
  11. }
  12. return fibonacci[N];
  13. }
  14. /**
  15. * @param args
  16. */
  17. public static void main(String[] args) {
  18. for(int N=0;N<100;N++){
  19. StdOut.println(N+" "+F(N));
  20. }
  21. }
  22. }

1.1.22 二分查找

eclipse不支持重定向输入流
重定向输出流可以Run-->Run Configuration-->Common选项卡-->Standard Input and Output-->File
program argument:tinyW.txt tinyT.txt

  1. import io.In;
  2. import io.StdIn;
  3. import io.StdOut;
  4. import java.io.FileInputStream;
  5. import java.io.FileNotFoundException;
  6. import java.util.Arrays;
  7. public class Test {
  8. public static int rank(int key, int[] a) {
  9. StdOut.printf("key=%d\n",key);
  10. StdOut.printf("%10s%10s%10s\n", "deep"," lo", "hi");
  11. return rank(key, a, 0, a.length - 1, 0);
  12. }
  13. public static int rank(int key, int[] a, int lo, int hi, int deep) {
  14. if (lo > hi)
  15. return -1;
  16. StdOut.printf("%10d%10d%10d\n", deep, lo, hi);
  17. int mid = lo + (hi - lo) / 2;
  18. if (key < a[mid])
  19. return rank(key, a, lo, mid - 1, deep + 1);
  20. else if (key > a[mid])
  21. return rank(key, a, mid + 1, hi, deep + 1);
  22. else
  23. return mid;
  24. }
  25. /**
  26. * @param args
  27. */
  28. public static void main(String[] args) {
  29. int[] whitelist = new In(args[0]).readAllInts();
  30. Arrays.sort(whitelist);
  31. //eclipse不支持重定向输入流到文件, 故使用setIn函数
  32. try {
  33. FileInputStream fis = new FileInputStream(args[1]);
  34. System.setIn(fis);
  35. } catch (FileNotFoundException e) {
  36. // TODO Auto-generated catch block
  37. e.printStackTrace();
  38. System.out.println("File not found!");
  39. }
  40. while (!StdIn.isEmpty()) {
  41. int key = StdIn.readInt();
  42. if (rank(key, whitelist) < 0) {
  43. StdOut.printf("%d not found\n",key);
  44. }
  45. }
  46. }
  47. }

1.1.27 二项分布

书上的代码~递归次数并不知道咋算。。
百度文库的一份答案写的(100!)

  1. public static double binomial(int N, int k, double p) {
  2. if (N == 0 && k == 0)
  3. return 1.0;
  4. if (N < 0 || k < 0)
  5. return 0.0;
  6. return (1.0 - p) * binomial(N - 1, k, p) + p
  7. * binomial(N - 1, k - 1, p);
  8. }

用数组保存计算过的值~修正版

  1. public static double binomialArrays(int N, int K, double p) {
  2. double[][] a = new double[N + 1][K + 1];
  3. a[0][0] = 1;
  4. for (int j = 1; j < N + 1; j++) {
  5. a[j][0] = a[j - 1][0] * (1 - p);
  6. }
  7. for (int i = 0; i < N + 1; i++)
  8. for (int j = 1; j <= i && j < K + 1; j++) {
  9. a[i][j] = (1 - p) * a[i - 1][j] + p
  10. * a[i - 1][j - 1];
  11. }
  12. return a[N][K];
  13. }

1.1.28 修改二分查找 删除重复元素

  1. public class BinarySearch {
  2. //由于删除元素后int数组长度a.length没法修改,添加数组长度形参
  3. public static int rank(int key, int[] a, int length) {
  4. return rank(key, a, 0, length - 1);
  5. }
  6. public static int rank(int key, int[] a, int lo, int hi) {
  7. if (lo > hi)
  8. return -1;
  9. int mid = lo + (hi - lo) / 2;
  10. if (key < a[mid])
  11. return rank(key, a, lo, mid - 1);
  12. else if (key > a[mid])
  13. return rank(key, a, mid + 1, hi);
  14. else
  15. return mid;
  16. }
  17. /**
  18. * 移除有序数组中的重复元素,将后面的元素前移,最后j个元素置零
  19. *
  20. * @param a
  21. * 待处理的整型数组,要求a是已经经过排序的数组
  22. * @return 移除的元素个数j
  23. */
  24. public static int removeDuplicate(int[] a) {
  25. int i = 0;// 当前元素
  26. int j = 0;// 需移除的元素个数
  27. int k = 1;
  28. while (i < a.length) {
  29. if (j != 0) {
  30. a[i - j] = a[i];
  31. }
  32. while (i + k < a.length && a[i] == a[i + k]) {
  33. k++;
  34. }
  35. i = i + k;
  36. j = j + k - 1;
  37. k = 1;
  38. }
  39. for (i = 0; i < j; i++) {
  40. a[a.length - i - 1] = 0;
  41. }
  42. for (i = 0; i < a.length; i++) {
  43. System.out.println(a[i]);
  44. }
  45. return j;
  46. }
  47. /**
  48. * @param args
  49. */
  50. public static void main(String[] args) {
  51. int[] whitelist = new In(args[0]).readAllInts();
  52. Arrays.sort(whitelist);
  53. int rm = removeDuplicate(whitelist);//删除重复元素
  54. // eclipse不支持重定向输入流到文件, 故使用setIn函数
  55. try {
  56. FileInputStream fis = new FileInputStream(args[1]);
  57. System.setIn(fis);
  58. } catch (FileNotFoundException e) {
  59. // TODO Auto-generated catch block
  60. e.printStackTrace();
  61. System.out.println("File not found!");
  62. }
  63. while (!StdIn.isEmpty()) {
  64. int key = StdIn.readInt();
  65. if (rank(key, whitelist, whitelist.length - rm) < 0) {
  66. StdOut.printf("%d not found\n", key);
  67. }
  68. }
  69. }
  70. }

1.1.29 二分查找等值键

修改rank函数返回最小的index
增加count函数返回等于key的元素个数

  1. public class BinarySearch {
  2. public static int rank(int key, int[] a) {
  3. return rank(key, a, 0,a.length-1);
  4. }
  5. public static int rank(int key, int[] a, int lo, int hi) {
  6. if (lo > hi)
  7. return -1;
  8. int mid = lo + (hi - lo) / 2;
  9. if (key < a[mid])
  10. return rank(key, a, lo, mid - 1);
  11. else if (key > a[mid])
  12. return rank(key, a, mid + 1, hi);
  13. else//修正以返回最小的index
  14. while (--mid >= 0 && a[mid] == key);
  15. return mid+1;
  16. }
  17. public static int count(int rank, int[] a){
  18. if(rank<0){
  19. return 0;
  20. }else if(rank<a.length){
  21. int i=1;
  22. while(rank+i < a.length && a[rank]==a[rank+i]){
  23. i++;
  24. }
  25. return i;
  26. }else{
  27. return -1;
  28. }
  29. }
  30. /**
  31. * @param args
  32. */
  33. public static void main(String[] args) {
  34. int[] whitelist = new In(args[0]).readAllInts();
  35. Arrays.sort(whitelist);
  36. // eclipse不支持重定向输入流到文件, 故使用setIn函数
  37. try {
  38. FileInputStream fis = new FileInputStream(args[1]);
  39. System.setIn(fis);
  40. } catch (FileNotFoundException e) {
  41. // TODO Auto-generated catch block
  42. e.printStackTrace();
  43. System.out.println("File not found!");
  44. }
  45. while (!StdIn.isEmpty()) {
  46. int key = StdIn.readInt();
  47. int r=rank(key, whitelist);
  48. int c=count(r,whitelist);
  49. if (r< 0) {
  50. StdOut.printf("%d not found\n\n", key);
  51. }else{
  52. StdOut.printf("%d rank %d\n", key,r);
  53. StdOut.printf("%d count %d\n\n", key,c);
  54. }
  55. }
  56. }
  57. }

1.1.36 乱序检查

  1. public class ShuffleTest {
  2. public static void main(String[] args) {
  3. int M = Integer.parseInt(args[0]);
  4. int N = Integer.parseInt(args[1]);
  5. int[] a = new int[M];
  6. int[][] count = new int[M][M];
  7. for (int k = 0; k < N; k++) {
  8. for (int i = 0; i < M; i++)
  9. a[i] = i;
  10. StdRandom.shuffle(a);
  11. for (int i = 0; i < M; i++) {
  12. count[i][a[i]]++;
  13. }
  14. }
  15. for (int j = 0; j < M; j++) {
  16. for (int i = 0; i < M; i++) {
  17. System.out.print(count[i][j]);
  18. System.out.print("\t");
  19. }
  20. System.out.println();
  21. }
  22. }
  23. }

1.1.37

输出的矩阵偏离N/M比36题的方法大~
为什么这样就是“糟糕的”打乱?

  1. public static void badShuffle(int[] a) {
  2. if (a == null)
  3. throw new NullPointerException("argument array is null");
  4. int N = a.length;
  5. for (int i = 0; i < N; i++) {
  6. int r = StdRandom.uniform(N); // between 0 and N-1
  7. int temp = a[i];
  8. a[i] = a[r];
  9. a[r] = temp;
  10. }
  11. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注