ユークリッドの互除法の呼び出し回数
アルゴリズム難易度: ★★★☆☆
関数gcd(m, n)が次のように定義されている。m=135, n=35のとき、gcd(m, n)は何回呼ばれるか。ここで、最初のgcd(135, 35)の呼出しも、1回に数えるものとする。また、m, n (m > n ≧ 0) は整数とし、m mod nはmをnで割った余りを返すものとする。
出典: 平成24年度春期 応用情報技術者 午前 問8
関数gcd(m, n)が次のように定義されている。m=135, n=35のとき、gcd(m, n)は何回呼ばれるか。ここで、最初のgcd(135, 35)の呼出しも、1回に数えるものとする。また、m, n (m > n ≧ 0) は整数とし、m mod nはmをnで割った余りを返すものとする。