傻逼学习之——算法第四版 1.1

初学算法，不会Java，各种捉急，用的算法第四版，跟着百度文库瞎掰。。。。。。。。一题一题的埋坑，，，，

下面给出可以测试多题的代码（要有Sedgewick老先生的一手安排，去网站下载库和相应的文件：http://algs4.cs.princeton.edu/code/ ）

public class test {
 public static int lg(int N){
  int count = 0;
  for(int i = 2; i <= N; i *= 2)
   count++;
  return count;
 }
 
 public static int[] histogram(int[] a, int M){
  int[] b = new int[M];
  int N = a.length;
  for(int j = 0; j < N; j++)
   for(int i = 0; i < M; i++){
    if(i == a[j])
    {
     b[i]++;
    }
   }
  return b;
 }
 
 public static String exR1(int n){
  if(n <= 0) return "";
  return exR1(n-3) + n + exR1(n-2);
 }
 
 public static int mystery(int a, int b){//神秘的函数，其实就是add(a,b)函数，
  if(b == 0) return 0;    //至于题意中说的将代码中+换成*，return 0换成return 1，并没看出来啥效果
  if(b % 2 == 0) return mystery(a+a, b/2);
  return mystery(a+a, b/2) + a;
 }
 
 public static void fibonacci(long[] a){
  int N = a.length;
  a[0] = 0;
  a[1] = 1;
  for(int i = 2; i < N; i++)
   a[i] = a[i-1] + a[i-2];
  return;
 }
 
 public static double lnn(int n){
  if(n == 0) return 0;
  return lnn(n-1) + Math.log(n);
 }
 
 //其中迭代中，利用的是r(余数)为零时，取b(除数)为结果，递归中用的是q(除数)为零时，p（被除数）为结果，，，其实大同小异，可以相互转换
 public static int gcd(int p, int q){//应该是默认p > q
  StdOut.printf("p=%d q=%d  ", p, q);//这一句代码是留题目1.1.24用的，他会影响1.1.30，所以没让其输出
  if(q == 0) return p;
  int r = p % q;
  return gcd(q, r);
 }
 
 public static boolean[][] testarray(boolean[][] a){
  int N = a.length;//行数
  int M = a[0].length;//列数
  for(int i = 0; i < N; i++){
   for(int j = 0; j < M; j++){
    if(gcd(i,j) == 1)
     a[i][j] = true;
    else
     a[i][j] = false;
   }
  }
  return a;
 }
 
 public static void main(String[] args){
  //1.1.2.c
  StdOut.println("1.1.2.c:");
  if(4.1 >= 4)
  StdOut.println("True"); //测试结果为：True
  //1.1.2.d
  StdOut.println("1.1.2.d:");
  StdOut.println(1 + 2 + "3");//测试结果为：33
  //1.1.3
  StdOut.println("1.1.3:");
  int a = Integer.parseInt(args[0]);
  int b = Integer.parseInt(args[1]);
  int c = Integer.parseInt(args[2]);
  if(a == b && b == c)
   StdOut.println("equal");
  else
   StdOut.println("Not equal");
  //1.1.6
  StdOut.println("1.1.6");
  int f = 0;
  int g = 1;
  for(int i = 0; i <= 15; i++){
   StdOut.printf("%d ", f);
   f = f + g;
   g = f - g;
  }
  StdOut.printf("\n");
  //1.1.7.a
  StdOut.println("1.1.7.a");
  double t = 9.0;
  while(Math.abs(t - 9.0 / t) > .001){
   t = (9.0 / t + t) / 2.0;
  }
  StdOut.println(t);
  //1.1.7.b
  StdOut.println("1.1.7.b");
  int sum = 0;
  for(int i = 1; i < 1000; i++)
   for(int j = 0; j < i; j++)
    sum++;
  StdOut.println(sum);
  //1.1.7.c
  StdOut.println("1.1.7.c");
  sum = 0;
  for(int i = 1; i < 1000; i *= 2)
   for(int j = 0; j < 1000; j++)
    sum++;
  StdOut.println(sum);
  //1.1.8
  StdOut.println("1.1.8");
  System.out.println('b');
  System.out.println('b' + 'c');
  System.out.println((char)('a' + 4));
  //1.1.9
  StdOut.println("1.1.9");
  String s = "";
  for(int n = 10; n > 0; n /= 2)
   s = (n % 2) + s;//新得到的字符，该是由字符串前方加入
  StdOut.println(s);
  //另一种Java内置方法
  //Integer.toBinaryString(N);//将N转换成二进制
  //1.1.12
  StdOut.println("1.1.12");
  int[] a12 = new int[10];//同一节题目中出现同样的标识符的测试代码，在标识符后面加题号区分
  for(int i = 0; i < 10; i++)
   a12[i] = 9 - i;
  for(int i = 0; i < 10; i++)
   a12[i] = a12[a12[i]];
  for(int i = 0; i < 10; i++)
   System.out.printf("%d ", i);
  StdOut.println();
  //1.1.13
  StdOut.println("1.1.13");
  int [][]a13 = {{1, 2, 3},{4, 5, 6}};
  int [][]b13 = new int[3][2];//b13是a13的转置
  for(int i = 0; i < 2; i++)
   for(int j = 0; j < 3; j++)
    b13[j][i] = a13[i][j];
  for(int i = 0; i < 3; i++){
   for(int j = 0; j < 2; j++)
    StdOut.printf("%d ", b13[i][j]);
   StdOut.println();
  }
  //1.1.14
  StdOut.println("1.1.14");
  int N = 8;
  StdOut.println(lg(N));
  //1.1.15
  StdOut.println("1.1.15");
  int[] a15 = {1, 2, 0, 1, 2, 0, 1, 2, 0, 1};
  int M = 3;
  int[] b15 = new int[M];
  b15 = histogram(a15, M);
  for(int i = 0; i < M; i++)
   StdOut.printf("%d ", b15[i]);
  StdOut.println();
  //1.1.16
  StdOut.println("1.1.16");
  N = 6;
  StdOut.println(exR1(N));
  //1.1.18
  StdOut.println("1.1.18");
  StdOut.println(mystery(2, 25));
  StdOut.println(mystery(3, 11));
  //1.1.19      //Fibonacci更好的实现
  StdOut.println("1.1.19");
  N = 100;
  long[] a19 = new long[N];
  fibonacci(a19);
  for(int i = 0; i < N; i++){
   StdOut.printf("%d ", a19[i]);//Java学的差，这点不会输出长整型
  }
  StdOut.println();
  //1.1.20
  StdOut.println("1.1.20");
  N = 10;
  StdOut.println(lnn(N));
  //1.1.22另见 BinarySearch1122
  //1.1.24
  StdOut.println("1.1.24");
  a = 105;
  b = 24;
  StdOut.println(gcd(a, b));
//迭代法——最大公约数（最小公倍数为最大公约数乘两数中小的那个）
//  int r = a % b;//大数余小数
//  while(r != 0){//余数不为零，除余向前移（a / b = ? ... r   b,r向前移取代a,b）;
//   a = b;
//   b = r;
//   r = a % b;
//  }
//  StdOut.println(b);
  //1.1.28见BinarySearch
  //1.1.29见BinarySearch
  //1.1.30
  StdOut.println("1.1.30");
  N = 4;
  M = 4;
  boolean[][] a30 = new boolean[N][M];
  testarray(a30);
  for(int i = 0; i < N; i++){
   for(int j = 0; j < M; j++){
    if(a30[i][j] == true)
     StdOut.printf("true  ");
    else
     StdOut.printf("false ");
   }
   StdOut.println();
  }
  //1.1.31见RandomSearch1122
  //1.1.32见histogram1132
  //1.1.33学线性代数后回来补充
  //1.1.36和1.1.37没懂题意，
  //1.1.38跳过
  //1.1.39见RandomMatching
  
  
 }//main()
}

上面代码的答案：
1.1.2.c:
True
1.1.2.d:
33
1.1.3:
equal
1.1.6
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
1.1.7.a
3.00009155413138
1.1.7.b
499500
1.1.7.c
10000
1.1.8
b
197
e
1.1.9
1010
1.1.12
0 1 2 3 4 5 6 7 8 9
1.1.13
1 4
2 5
3 6
1.1.14
3
1.1.15
3 4 3
1.1.16
316142
1.1.18
50
33
1.1.19
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994 190392490709135 308061521170129 498454011879264 806515533049393 1304969544928657 2111485077978050 3416454622906707 5527939700884757 8944394323791464 14472334024676221 23416728348467685 37889062373143906 61305790721611591 99194853094755497 160500643816367088 259695496911122585 420196140727489673 679891637638612258 1100087778366101931 1779979416004714189 2880067194370816120 4660046610375530309 7540113804746346429 -6246583658587674878 1293530146158671551 -4953053512429003327 -3659523366270331776 -8612576878699335103 6174643828739884737 -2437933049959450366
1.1.20
15.104412573075518
1.1.24
p=105 q=24 p=24 q=9 p=9 q=6 p=6 q=3 p=3 q=0 3
1.1.30
p=0 q=0 p=0 q=1 p=1 q=0 p=0 q=2 p=2 q=0 p=0 q=3 p=3 q=0 p=1 q=0 p=1 q=1 p=1 q=0 p=1 q=2 p=2 q=1 p=1 q=0 p=1 q=3 p=3 q=1 p=1 q=0 p=2 q=0 p=2 q=1 p=1 q=0 p=2 q=2 p=2 q=0 p=2 q=3 p=3 q=2 p=2 q=1 p=1 q=0 p=3 q=0 p=3 q=1 p=1 q=0 p=3 q=2 p=2 q=1 p=1 q=0 p=3 q=3 p=3 q=0 false true false false
true true true true
false true false true
false true true false

个别分开的题目：

import java.util.Arrays;

public class BinarySearch {
 
 //（排名）常规查找，，，返回查找到的下标和没找到时的-1
// public static int rank(int key, int[] a) {
//  int lo = 0;
//  int hi = a.length - 1;
//  while(lo <= hi) {
//   int mid = lo + (hi - lo) / 2;
//   if  (key < a[mid]) hi = mid - 1;
//   else if (key > a[mid]) lo = mid + 1;
//   else      return mid;
//  }
//  return -1;
// }
 
 //（排名）返回数组中，，，小于该键的元素数量
 public static int rank(int key, int[] a){
  int lo = 0;
  int hi = a.length - 1;
  while(lo <= hi){
   int mid = lo + (hi - lo) / 2;
   if  (key < a[mid]) hi = mid - 1;
   else if (key > a[mid]) lo = mid + 1;
   else{
    while(mid > 0 && a[mid] == a[mid-1])
     mid--;
    return mid;
   }
  }
  return -1;
 }
 
 //count(key， a)函数，返回和key相等的元素数量
 public static int count(int key, int[] a){
  int cnt = 0;
  int i = rank(key, a);
  while(i < a.length -1 && a[i] == a[i+1] ){
   cnt++;
   i++;
  }
  cnt++;
  return cnt;
 }
 
  public static int countc(int[] a){
   int cnt = 0;
   for(int i = 0; i < a.length - 1; i++){
    if(a[i] == a[i+1])
     cnt++;
   }
   return cnt;
  }
  
  public static int[] remove(int[] a, int cnt){//结合countc函数，删去（已排序）数组中重复元素，实现的很不错
   int s = 0;
   int[] b = new int[a.length - cnt];
   b[0] = a[0];  //不要忘记先将第一个元素放入数组
   for(int i = 0; i < a.length - 1; i++){
    if(a[i] == a[i+1])
     s++;
    else{
     b[i-s+1] = a[i+1];
    }
   }
   return b;
  }



 public static void main(String[] args) {
//  还是不知道这个In.readInts(args[0]);怎么用的，，，还有命令行
  //int[] whitelist = In.readInts(args[0]);//虽然不知咋地了，不过要输入命令行参数，可行，然而在eclipse中，不知
  //这样的测试成功了，删除重复元素，感觉不算低效的解决
  int[] whitelist = {23,50,10,99,18,23,98,84,11,10,48,77,13,54,98,77,77,68};
  Arrays.sort(whitelist);
  
  int key = 77;
  int r = rank(key, whitelist);
  StdOut.printf("rank=%d\n", r);
  StdOut.printf("count=%d\n", count(key, whitelist));
  
  int cnt = countc(whitelist);
  int[] whitelist2 = new int[whitelist.length - cnt];
  whitelist2 = remove(whitelist, cnt);
  for(int i = 0; i < whitelist2.length; i++)
   StdOut.printf("%d ", whitelist2[i]);
 
 
  
  //原白名单过滤测试程序
//  while(!StdIn.isEmpty()){
//   int key = StdIn.readInt();
//   if(rank(key, whitelist) < 0)
//    StdOut.println(key);
//  }
  
  
 }

}

其答案：

rank=11
count=3
10 11 13 18 23 48 50 54 68 77 84 98 99

//题目1122，凑合着用，基本出结果了
public class BinarySearch1122 {
  public static int rank(int key, int[] a){
   return rank(0, key, a, 0, a.length - 1);
  }
  
  public static int rank(int order, int key, int[] a, int lo, int hi){
   order += 1;
   if(lo > hi) return -1;
   int mid = lo + (hi - lo) / 2;
   StdOut.printf("order:%d  lo:%d  mid:%d  hi:%d\n", order, lo, mid, hi);
   if   (key < a[mid]) return rank(order, key, a, lo, mid - 1 );
   else if(key > a[mid])  return rank(order, key, a, mid + 1, hi);
   else      return mid;
  }
  
  //@SuppressWarnings("deprecation")
  public static void main(String[] args){
   int[] whitelist = {10, 11, 12, 16, 18, 23, 29, 33, 48, 54, 57, 68, 77, 84, 98};
   //以下方法并未试成功
   //int[] whitelist = In.readInts(args[0]);
   //int N = 18;
   //int[] whitelist = new int[N];
   //whitelist = StdIn.readAllInts();
   int a = 23;
   int b;
   b = rank(a, whitelist);
   StdOut.printf("b=%d\n", b);
  }
 }

其答案：

order:1 lo:0 mid:7 hi:14
order:2 lo:0 mid:3 hi:6
order:3 lo:4 mid:5 hi:6
b=5

public class RandomAccess1131 {
 public static void drawcircle(double x, double y, double r, double[][] a){
  StdDraw.setXscale(0, x * 2);//设置画面的X范围
  StdDraw.setYscale(0, y * 2);//设置画面的Y范围
  StdDraw.setPenRadius(0.005);//设置画笔的粗细
  StdDraw.setPenColor(StdDraw.RED);//设置画笔的颜色
  StdDraw.circle(x, y, r);
  
  int N = a.length;
  for(int i = 0; i < N; i++){//这个for循环是在圆上间隔相同的位置画上点
   StdDraw.setPenRadius(0.05);
   StdDraw.setPenColor(StdDraw.BLACK);
   double m = x - x * Math.cos(Math.PI * 2 * i / N);//点横坐标的计算
   double n = y + y * Math.sin(Math.PI * 2 * i / N);//点纵坐标的计算——计算的很好
   StdDraw.point(m, n);
   a[i][0] = m;  //数组中[0]号位存放，横坐标
   a[i][1] = n;   //数组中[1]号位存放，纵坐标，，，作为画线用的参数
   StdDraw.setPenColor(StdDraw.RED);
  }
  
 }
 
 public static void Randomline(double x, double y, double p, double[][] a){
  StdDraw.setXscale(0, x * 2);
  StdDraw.setYscale(0, y * 2);
  StdDraw.setPenRadius(0.01);
  StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
  int N = a.length;
  for(int i = 0; i < N; i++){
   for(int j = 0; j < N; j++){
    if(StdRandom.bernoulli(p))//返回真的概率为P的函数
     StdDraw.line(a[i][0], a[i][1], a[j][0], a[j][1]);
   }
  }
 }
 
 public static void main(String[] args){
  double x = 50;
  double y = 50;
  double r = 50;
  int N = 8;
  double p = 0.5;
  double[][]  a = new double[N][2]; 
  drawcircle(x, y, r, a);
  Randomline(x, y, p, a);
 }
 
 
}

答案：图，，，，

public class histogram1132 {
 public static double[] segmentation(int N, double l, double r, double[] a){
  if(N == 0)  return a;
  double s = (r - l) / N;
  a[0] = l;
  for(int i = 1; i < a.length; i++){
   a[i] = a[i-1] + s;
  }
  return a;
 }
 
 public static void makehistogram(double[] a, double[] b, double l, double r){
  int[] c = new int[a.length-1];
  for(int i = 0; i < b.length; i++){
   for(int j = 0; j < a.length; j++){
    if(b[i] >= a[j] && b[i] < a[j+1]){
     c[j]++;
     break;//continue;//应该是break吧
    }
   }
  }
  
  int N = c.length;
  StdDraw.setXscale(0, (r-l) * 1.2);
  StdDraw.setYscale(0, b.length / N * 1.5);
  for(int i = 0; i < N; i++){
   double x = l + (r - l) * i / N;
   double y = c[i] / 2.0;
   double rw = (r - l) / (2 * N);
   double rh = c[i] / 2.0;
   StdDraw.filledRectangle(x, y, rw, rh);
   StdOut.print(c[i] + " ");
  }
 }
 
 public static void main(String[] args){
  int N = 10;
  double l = 2;
  double r = 20;
  double[] a = new double[N+1];
  double[] b = new double[N*N*N];
  a = segmentation(N, l, r, a);
  for(int i = 0; i < b.length; i++){
   b[i] = StdRandom.uniform(l, r);
  }
  makehistogram(a, b, l, r);
 }
 
 
}

答案：图。。。。

public class rollTheDice1135 {
 public static double[] simulation(double[] a, int N, int SIDES){
  for(int i = 0; i < N; i++){
   int n = 1 + StdRandom.uniform(SIDES);
   int m = 1 + StdRandom.uniform(SIDES);
   a[n+m] = a[n+m] + 1.0;
  }
  
  for(int k = 2; k <= 2 * SIDES; k++){
   a[k] = a[k] / N;
  }
  return a;
 }
 
 public static void match(double[] dist, double[] dist2, int SIDES, int N){
  for(int n = N; n <= 10000000; n = n * 10){//n = n + n / 10;是干什么用的
  dist2 = simulation(dist2, n, SIDES);
   boolean ismatch = true;
   for(int k = 2; k <= 2 * SIDES; k++){
    if(Math.abs(dist[k] - dist2[k]) <= 0.0005){//单纯的利用差的绝对值并不能确保答案正确性，先将就着用，，，
     continue;
    }
    else{
     ismatch = false;
     break;
    }
   }
   
   if(ismatch){
    StdOut.printf("true   ");
   }
   else{
    StdOut.printf("false  ");
   }
   
   StdOut.println("n=" + n);
   Print(dist2, SIDES);
  }
 }
 
 public static void Print(double[] a, int SIDES){
  for(int k = 2; k <= 2 * SIDES; k++){
   StdOut.print("k=" + k + " " + a[k] + " ");
   if((k - 1) % 6 == 0)
    StdOut.println();
 }
  StdOut.println();
 }
 
 public static void main(String[] args){
  int SIDES = 6;
  int N = 10;
  double[] dist = new double[2*SIDES+1];
  double[] dist2 = new double[2*SIDES+1];
  for(int i = 1; i <= SIDES; i++)
   for(int j = 1; j <= SIDES; j++){
    dist[i+j] += 1.0;
   }
  
  for(int k = 2; k <= 2 * SIDES; k++){
   dist[k] /= 36.0;
  }
  
  StdOut.println("dist:");
  Print(dist, SIDES);
  
  match(dist, dist2, SIDES, N);
  
 }
}//class

答案：

dist:
k=2 0.027777777777777776 k=3 0.05555555555555555 k=4 0.08333333333333333 k=5 0.1111111111111111 k=6 0.1388888888888889 k=7 0.16666666666666666
k=8 0.1388888888888889 k=9 0.1111111111111111 k=10 0.08333333333333333 k=11 0.05555555555555555 k=12 0.027777777777777776
false n=10
k=2 0.1 k=3 0.0 k=4 0.1 k=5 0.1 k=6 0.1 k=7 0.1
k=8 0.1 k=9 0.4 k=10 0.0 k=11 0.0 k=12 0.0
false n=100
k=2 0.040999999999999995 k=3 0.1 k=4 0.091 k=5 0.051 k=6 0.161 k=7 0.141
k=8 0.091 k=9 0.154 k=10 0.1 k=11 0.06 k=12 0.02
false n=1000
k=2 0.032041 k=3 0.0511 k=4 0.077091 k=5 0.102051 k=6 0.139161 k=7 0.16914099999999999
k=8 0.126091 k=9 0.11315399999999999 k=10 0.0851 k=11 0.06706000000000001 k=12 0.03902
false n=10000
k=2 0.0301032041 k=3 0.053105110000000004 k=4 0.0813077091 k=5 0.1112102051 k=6 0.14111391610000001 k=7 0.1696169141
k=8 0.1406126091 k=9 0.10891131540000001 k=10 0.08060851 k=11 0.056006705999999996 k=12 0.027503902
false n=100000
k=2 0.027750301032040996 k=3 0.055490531051099995 k=4 0.083150813077091 k=5 0.11127111210205101 k=6 0.14022141113916098 k=7 0.166691696169141
k=8 0.13980140612609102 k=9 0.11016108911315402 k=10 0.08228080608510001 k=11 0.05594056006706 k=12 0.027250275039019996
false n=1000000
k=2 0.027825027750301032 k=3 0.05573105549053105 k=4 0.08338608315081308 k=5 0.11145311127111211 k=6 0.13907014022141112 k=7 0.16652016669169614
k=8 0.13889013980140613 k=9 0.1105041101610891 k=10 0.08317608228080609 k=11 0.055837055940560064 k=12 0.027608027250275037
true n=10000000
k=2 0.027797902782502777 k=3 0.05559300557310556 k=4 0.08314980833860831 k=5 0.11105081114531112 k=6 0.13896731390701403 k=7 0.16676491665201668
k=8 0.13890211388901397 k=9 0.11105771105041101 k=10 0.08337660831760822 k=11 0.05554030558370559 k=12 0.027799602760802723

import java.util.Arrays;

public class RandomMatching {
 private static int M = 1000000;
 
 public static int[] RandomArray(int N){
  int[] a = new int[N];
  for(int i = 0; i < N; i++){
   a[i] = StdRandom.uniform(M);
  }
  return a;
 }
 
 public static int rank(int key, int[] a){
  int lo = 0; 
  int hi = a.length - 1;
  while(lo <= hi){
   int mid = lo + (hi - lo) / 2;
   if  (key < a[mid]) hi = mid - 1;
   else if (key > a[mid]) lo = mid + 1;
   else      return mid;
  }
  return -1;
 }
 
 public static void main(String[] args){
  int T = 3;
  for(int i = 10; i <= 1000000;  i *= 10){
   StdOut.println("i=" + i + ":");
   int[] a = new int[i];
   int[] b = new int[i];
   int cnt = 0;
   for(int j = 0; j < T; j++){
    a = RandomArray(i);
    Arrays.sort(a);
    b = RandomArray(i);
    Arrays.sort(b);
    for(int k = 0; k < i; k++){
     if(rank(b[k], a) >= 0)
      cnt++;
    }
   }
   StdOut.println("avergae time of the same number:"+ cnt/T);  
   
  }
 }
}

答案：

i=10:
avergae time of the same number:0
i=100:
avergae time of the same number:0
i=1000:
avergae time of the same number:1
i=10000:
avergae time of the same number:103
i=100000:
avergae time of the same number:9472
i=1000000:
avergae time of the same number:631881

额。。。。乱糟糟的样子，，，惨不忍睹啊

傻逼学习之——算法 第四版 1.1

傻逼学习之——算法第四版 1.1