0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

ユークリッドの互除法で最大公約数を求める

Posted at

※ユークリッドの互除法

  • 1,(関数ONE)
    まず、二つの変数a、bのうち、片方が0の場合、3(関数THREE)に送る。どちらも0でない場合、2の(関数TWO)に送る。
  • 2、(関数TWO)
    変数aとbの大きい方の数字を小さい方の数字で割り、その余りを求め。その数値を大きかった変数に書き替える。もしその数値が0の場合、二つの変数を3の(関数THREE)に送る。
    そうでない場合、もう一度、関数TWOに送り返す。
  • 3、(関数THREE)
    変数aとbのうち、0でない方が元の二つの数字の最大公約数になっている。
<?php
    $x=0;
    $y=0;
    [$a,$b]=preg_split('/ /', trim(fgets(STDIN)));

//関数one    
function one($a,$b){ 
    if($a==0 || $b==0){
        return three($a,$b);
    }elseif($a!=0 && $b!=0){
        return two($a,$b);
    }    
}

//関数two
function two($a,$b){
    if($a>$b){
        $x=$a%$b;
        $a=$x;
        if($a==0){
            return three($a,$b);
        }else{
            return two($a,$b);
        }
    }elseif($a<$b){
        $y=$b%$a;
        $b=$y;
        if($b==0){
            return three($a,$b);
        }else{
            return two($a,$b);
        }
    }
}

//関数three    
function three($a,$b){
    if($a==0){
        return $b;
    }elseif($b==0){
        return $a;
    }    
}
echo one($a,$b);
?>

数値の入力はコンソールから取得するため、 trim(fgets(STDIN))にしてあります。

0
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?