黑马程序员技术交流社区

标题: 最大公约数 学解释 [打印本页]
作者: 爱hao者    时间: 2015-12-18 16:10
标题: 最大公约数 学解释

static public int gcd1_1(int x, int y)   
{
  int temp;
  
  do{
  temp = x % y;
  x = y;
  y = temp;
  }while(temp != 0);
  
  return x;
}
作者: ash午夜阳光    时间: 2015-12-18 21:03
辗转相除法
作者: 洪志豪1994    时间: 2015-12-19 21:53
表示不懂~~~
作者: sorryjsy    时间: 2015-12-20 10:23

  2. public class Test {

  4.         /**
  5.          * 最大公约数
  6.          */
  7.         public static int gcd1_1(int x, int y) {
  8.                 int temp;

  10.                 do {
  11.                         temp = x % y;
  12.                         x = y;
  13.                         y = temp;
  14.                 } while (temp != 0);

  16.                 return x;
  17.         }

  19.         /**
  20.          * 上面方法也可以写成下面这种写法
  21.          */
  22.         public static int gcd(int x, int y) {
  23.                 if (x % y == 0) {
  24.                         return y;
  25.                 } else {
  26.                         return gcd(y, x % y);
  27.                 }

  29.         }

  31. }

  33. /**
  34. * 分析gcd1_1方法
  35. * 我们先假设x和y的最大公约数为T
  36. *
  37. * 情况1.如果x<y do代码块相当于把x和y的值互换，然后转到下面的情况2：
  38. *
  39. * 情况2.如果x>=y，只会有下面两种情况：
  40. *  ->>2.1 如果x和y的最大公约数T== y的话
  41. *   那么 x%y=0；返回y即可
  42. *   
  43. *  ->>2.2 如果x和y的最大公约数T<y的话 那么x = mT，y=nT （并且m>n）
  44. *      那么x%y=temp，此时temp一定也是T的整数倍，假设temp=qT，则q一定小于n。此时temp和y的公约数也即是所求的公约数。
  45. *      如此递归进行2.2步骤，则最终q会越来越小，直至q==1的时候，x%y==0，则此时y的值即为所求最大公约数。
  46. *
  47. *
  48. *
  49. */
复制代码






欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2