免許皆伝 初見の巻物

師範 / 目安 45分

カメ師範が、最後の巻物を持って現れました。ただし今度は、広げる前にこう言いました。

「この巻は、わしも中身を知らん。ある古い書物から写しただけじゃ。何をする手順なのか、書いてはおらん」

巻物には、名前のない疑似コードだけが記されていました。

手順 不明(a, b)
    x ← a
    y ← b
    n ← 0
    y が 0 でない間、次を繰り返す
        t ← x を y で割った余り
        x ← y
        y ← t
        n ← n + 1
    x と n を返す

師範は続けます。「読み、追い、好きな得物で実装せよ。読めぬコードに出会ったときの作法——それが免許皆伝の条件じゃ」

初見のコードを前にしたとき、上から順に日本語へ訳そうとしても、たいてい霧は晴れません。小さい数を入れて、手で追うのが最短です。

a が 48、b が 18 で追ってみます。最初は x が 48、y が 18。余りは 12 なので、x は 18、y は 12 になりました。次の余りは 6 で、x は 12、y は 6。次の余りは 0 で、x は 6、y は 0。ここで繰り返しが止まり、x は 6 です。

48 と 18 に共通する約数のうち、最も大きいものは 6 です。この手順は最大公約数を求めています。ユークリッドの互除法という、2000年以上前から知られた技です。n は、その割り算を何回繰り返したかを数えています。

変数の役割に名前が付いた瞬間、霧は晴れます。x と y は「まだ調べていない2つの数」、t は「その余り」、n は「手順の数」です。

完成条件

runScroll という関数を1つ定義してください。どの言語で解いても関数名は runScroll にしてください。Python でも snake_case ではなく、この綴りのまま使います。

引数は2つ、a と b です。どちらも1以上の整数しか渡しません。

やることは3つです。

1. 巻物の疑似コードをそのとおりに実装し、最大公約数と、繰り返した回数を求めます
2. その最大公約数を使って、a と b の最小公倍数も求めます
3. 次の形をした1つの文字列を返します

答え 21 / 手順 3 / 応用 23562

答え は最大公約数、手順 は繰り返しの回数、応用 は最小公倍数です。上の例は a が 1071、b が 462 のときの結果です。

最小公倍数は、2つの数の積を最大公約数で割ったものです。ただし先に掛けてから割ると、大きな入力で桁があふれることがあります。先に片方を最大公約数で割ってから、もう片方を掛けてください。答えは同じで、途中の積を小さくできます。型の範囲に収まることも必要です。師範が最後に見たいのは、この一手です。

a より b が大きくても、この手順は正しく動きます。なぜ動くのか、1周目に何が起きるかを追って確かめてください。

進め方

ひな形の「課題」と書かれた部分から始めてください。初期化や補助処理は完成済みです。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。ヒントは必要に応じて使い、書いた処理を自分で追えることを目標にします。

開かずに10分粘って進まないなら、①だけ開けてください。粘る時間そのものには価値がありません。価値があるのは、自分で書いた行が動いた瞬間です。

書き終えたら、必ず手で追った結果と突き合わせてください。48 と 18 なら、答えは 6、手順は 3 回のはずです。合わなければ、代入の順番を疑ってください。x に y を入れてから y に余りを入れる、この順を崩すと、余りを取る前の値が消えます。

師範は巻物を巻き戻し、静かに言いました。

「見事。……次に読めぬコードと出会う場所は、試験場か、現場か。どちらでも、もう恐れることはない」

奥から一枚の紙が差し出されます。そこには アルゴリズム道場・免許皆伝 と記されていました。総和と最大の一周から始まり、探索、整列、再帰、器づくり、計算量を経て、いまあなたは名前も知らない手順を読み解いて動かすところまで来ました。得物は、これからも自由です。

疑似コードを言語に移す足場

% は割った余りです。別の題材として、お菓子17個を5個ずつ袋に詰めると、袋は3つ、余りは2個です。整数の商は Python では //、Java では整数どうしの /、JavaScript と TypeScript では Math.floor を使います。

Python

bags = 17 // 5
left = 17 % 5
while left > 0:
    left -= 1

JavaScript

const bags = Math.floor(17 / 5);
let left = 17 % 5;
while (left > 0) {
  left -= 1;
}

TypeScript

const bags: number = Math.floor(17 / 5);
let left: number = 17 % 5;
while (left > 0) {
  left -= 1;
}

Java

int bags = 17 / 5;
int left = 17 % 5;
while (left > 0) {
    left -= 1;
}

!= は等しくない比較で、JavaScript と TypeScript では !== を使います。疑似コードの矢印は = に移します。余りを一時変数へ保存してから2つの数を更新し、手順の回数を増やしてください。

初期化、最後の最大公約数の受け取り、最小公倍数の箱、文字列の整形は渡しています。書くのは繰り返しと、先に割ってから掛ける式の2か所です。Java の multiplyWide(reduced, value) は掛け算前に long へ広げる補助関数です。第1引数には割った結果を渡します。入力は a、b とも 1〜1000000 で、この範囲の最小公倍数は4言語で正確に扱えます。

1. 関数名は4言語すべてで runScroll にすること(Python も snake_case にしない)
2. 引数は a と b の2つで、どちらも1以上の整数
3. 本文の疑似コードのとおりに実装し、最大公約数を求めること
4. 繰り返しが何回起きたかを数えること
5. その最大公約数を使って a と b の最小公倍数も求めること
6. 最小公倍数は、先に片方を最大公約数で割ってから、もう片方を掛けること(先に掛けない)
7. 戻り値は「答え ○ / 手順 ○ / 応用 ○」の形をした1つの文字列であること
8. a より b が大きい場合も正しく動くこと
9. ひな形の補助処理と出力整形を使い、余りで更新する繰り返しと、先に割って掛ける式を書くこと
10. a と b はともに 1〜1000000 の整数です