免許皆伝 初見の巻物

師範 / 目安 45分

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

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

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

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

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

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つの文字列を返します

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

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

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

進め方

白紙から書いてください。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。1つも開けずに通せたら、その問題は自分のものです。

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

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

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

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

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

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