令和5年度 I-2-2

解説

この問題で問われていること

自然数A, Bの最大公約数を求めるユークリッド互除法のアルゴリズムを表す流れ図において、余りRを0と比較した後の分岐条件(ア: 継続する条件、イ: 終了する条件)と、終了時に出力する値(ウ)を求める問題。

解き方

① 互除法: 余りRが0でない間は「A←B、B←R」をくり返し、R=0になったときのBが最大公約数
② ア(続ける側)=R≠0、イ(終わる側)=R=0、ウ(出力)=B
③ ④。⑤のRは終了時点で0

正解が正しい理由

流れ図では、RをAをBで割った余りとして計算した後、Rと0を比較し、(ア)の分岐では「A←B, B←R」と更新して計算を継続し、(イ)の分岐では(ウ)を出力して終了する。ユークリッド互除法は余りが0になるまで割り算を繰り返すアルゴリズムであるため、余りR≠0のときは計算を継続する必要があり、ア=R≠0である。一方、R=0になった時点で終了して結果を出力するため、イ=R=0である。R=0になった時点でのBの値が、GCD(A,B)=GCD(B,R)の関係より最大公約数そのものであるため、出力する値はウ=Bである。したがってア=R≠0、イ=R=0、ウ=Bの組合せである④が正しい。

各選択肢について

• ① アとイの条件が逆になっている。計算を継続すべきなのは余りが0でない(R≠0)ときであり、終了すべきなのは余りが0(R=0)になったときである。
• ② ア=R≠0、イ=R=0は正しいが、ウが「A」となっている点が誤り。終了時点でA←B, B←Rの更新前のBが最大公約数を保持しているため、出力すべきはAではなくBである。
• ③ アとイの条件が逆になっている上に、ウも「B」ではなく問題の趣旨と整合しない可能性がある組合せであり誤り(継続条件と終了条件の取り違えが根本的な誤り)。
• ④ ア=R≠0(余りが0でなければ計算を継続)、イ=R=0(余りが0になれば終了)、ウ=B(終了時のBの値が最大公約数)の組合せが、ユークリッド互除法のアルゴリズムと一致しており、これが正答。
• ⑤ ア=R≠0、イ=R=0は正しいが、ウが「R」となっている点が誤り。終了時点(直前の計算でR=0となった時点)ではRの値は0であり、最大公約数を表すのはBの値である。

覚えるべきポイント

ユークリッド互除法のアルゴリズムでは、余りが0になるまで「A←B, B←R」の更新と剰余計算を繰り返し、余りが0になった時点でのBの値が最大公約数となる。流れ図の分岐を読み解く際は、ループを継続する条件と終了する条件を取り違えないよう注意する。