How to find the greatest common divisor of two integers?

本文所选的例子来自于《Advanced Bash-scripting Gudie》一书，译者 杨春敏 黄毅

 1 #!/bin/bash 2  #求两个整数的最大公约数 3   4  E_BADARGS=65 5   6  #如果参数个数不为2，以参数错误退出 7  if [ $# -ne 2 ] 8  then 9      echo "Usage: `basename $0` first-number second-number"10      exit $E_BADARGS11  fi12 13  #如果参数非整数或参数值为0，以参数错误退出14  for i in $@15  do16      if [ $i=~[0-9]+ ]                                         #"=~"后面表示要跟正则表达式，+在正则表达式中表示前面的内容至少匹配一次17      then18         if [ $i -eq 0 ]19         then20             echo "Usage: `basename $0` parameter can't be zero"21             exit $E_BADARGS22         fi23      else24             echo "Usage: `basename $0` parameter must be integer"25 　　　　　　  exit $E_BADARGS26       fi27  done28 29  #设计一个gcd()函数，利用辗转相除法（欧几里德算法）求最大公约数30  gcd()31  {32      remainder=133      dividend=$134      divisor=$235  36      until [ $remainder -eq 0 ]37      do38          let "remainder=$dividend % $divisor"39          dividend=$divisor40          divisor=$remainder41      done42  }43  44  gcd $1 $245  46  echo "gcd of $1 and $2 is: $devidend"47  48  exit 0

在改编这个脚本的时候，我的考虑点主要有以下：

1. 所传的参数是不是要排除非整数的情况?

非整数的情况第一次我用echo $i | sed '/s/^[0-9]*$/''/g' && echo $?来排除，如果第一条命令正确执行，$?应该返回0，但是我们有更好的方法，即“=~"后面跟正则的方式

2. 参数值为0的情况是不是要排除在外？

在判断$i为整数的判断下再嵌套一个判断[ $i -eq 0 ]

3. 参数个数怎么控制？

[ $# -eq 2 ]或[ $# -ne 2 ]就可以排除空参数或参数个数不为2

4. 欧几里德算法中对于$1<$2的情况的处理？

先看$1>$2的情况

$1=65 $2=15

第一个循环：5=65 % 15

　　　　　　dividend=15

　　　　　　divisor=5

第二次循环　0=15%5

　　　　　　dividend=5

　　　　　　divisor=0

退出循环，gcd=$dividend=5

再看$1<$2的情况

$1=15 $2=65

第一次循环：15=15 % 65

　　　　　　dividend=65

　　　　　　divisor=15

第二次循环：5=65 % 15

　　　　　　dividend=15

　　　　　　divisor=5

第三次循环：0=15 % 5

　　　　　　dividend=5

　　　　　　divisor=0

退出循环，gcd=$dividend=5

可知$1<$2的情况比$1>$2的情况多了一个循环，结果是一样的

    

 

The above is the detailed content of How to find the greatest common divisor of two integers?. For more information, please follow other related articles on the PHP Chinese website!