Java 求最大公约数

发表于:2017-7-20 09:38

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:zxcvbnmzsedr    来源:51Testing软件测试网采编

#
java
分享:
  求最大公约数有三种方式
  1.暴力穷举法
  2.辗转相除法
  3.更相减损术
  暴力穷举法
  暴力穷举法的思路:从两个数之间找最小的数,然后用这个数往下减,若是两个数都能够被整除,那个数就是最大公约数
      int maxNumber(int m, int n) {
          int temp = m > n ? n : m;
          for (int i = temp; i > 0; i--) {
              if (m % i == 0 && n % i == 0) {
                  return i;
              }
          }
          return 0;
      }
  这种算法的效率太慢。要是笔试写这个分分钟回去等通知。
  辗转相除法
  辗转相除法有两种方式,维基百科和百度百科对于辗转相除法的定义有些出入
  百度百科:最大公约数等于a除以b的余数c和b之间的最大公约数。
      int maxNumber(int m, int n) {
          int temp;
          if (n > m) {
              temp = n;
              n = m;
              m = temp;
          }
          if (m % n == 0) {
              return n;
          }
          return maxNumber(n, m % n);
      }
  维基百科:最大公约数等于其中较小的数和两数的差的最大公约数。
      int maxNumber(int m, int n) {
          int temp;
          if (n > m) {
              temp = n;
              n = m;
              m = temp;
          }
          if (m % n == 0) {
              return n;
          }
          return maxNumber(m - n, n);
      }
  更相减损术
  更相减损术出自《九章算术》
  原文描述:可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。
  白话文译文:如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用2来约分)。如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,一直到减数与差相等为止,用这个相等的数字来约分。
  1.任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
  2.以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
  3.则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
      int maxNumber(int m, int n) {
          if (m == n) {
              return n;
          }
          if (n > m) {
              return maxNumber(n,m);
          }else {
              // 同为偶数
              if((m&1) == 0 && (n&1)==0){
                  return maxNumber(m >> 1, n >> 1) << 1;
              }else if((m&1) == 0 && (n&1) !=0){
                  return maxNumber(m >>1,n);
              }else if((m&1) != 0 && (n&1) ==0){
                  return maxNumber(m,n>>1);
              }else {
                  return maxNumber(n,m - n);
              }
          }
      }
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号