Ex_1_1_24.md

title	date	draft	tags	categories
算法4 Java解答 1.1.24	2019-03-02 19:38:48 +0800	false	JAVA	技术 归档

1.1.24

问题：

Give the sequence of values of p and q that are computed when Euclid’s algo- rithm is used to compute the greatest common divisor of 105 and 24. Extend the code given on page 4 to develop a program Euclid that takes two integers from the command line and computes their greatest common divisor, printing out the two arguments for each call on the recursive method. Use your program to compute the greatest common divisor or 1111111 and 1234567.

分析：

  public static int gcd(int p, int q, int recurLevel) {
    printIndent(recurLevel);
    StdOut.printf("p = %d, q = %d\n", p, q);

    if (q == 0) {
      return p;
    }
    int r = p % q;
    return gcd(q, r, recurLevel+1);
  }

//    level 0: p = 105, q = 24
//    level 1: --p = 24, q = 9
//    level 2: ----p = 9, q = 6
//    level 3: ------p = 6, q = 3
//    level 4: --------p = 3, q = 0
//    gcd = 3
//    level 0: p = 1111111, q = 1234567
//    level 1: --p = 1234567, q = 1111111
//    level 2: ----p = 1111111, q = 123456
//    level 3: ------p = 123456, q = 7
//    level 4: --------p = 7, q = 4
//    level 5: ----------p = 4, q = 3
//    level 6: ------------p = 3, q = 1
//    level 7: --------------p = 1, q = 0
//    gcd = 1

参考：