平成20年 春期 基本情報技術者 午前 問15
次の流れ図は、２数Ａ、Ｂの最大公約数を求めるユークリッドの互除法を、引き算の繰返しによって計算するものである。
Ａが８７６、Ｂが２０４のとき、何回の比較で処理は終了するか。
ア ４ イ ９ ウ １０ エ １１
【キーワード】
・ユークリッドの互除法
【キーワードの解説】
- ユークリッドの互除法
２つの自然数（整数）の最大公約数を求める手法。
２つの数（自然数、整数）ａとｂ（ａ≧ｂ）について、ａのｂによる剰余をｒとすると、ａとｂの最大公約数はｂとｒの最大公約数に等しいという性質が成り立ち、この性質を利用して最大公約数を求める方法。
スポンサードリンク
ユークリッドの互除法も用いた最大公約数を求める処理のフローチャートについての問題です。
フローチャートの処理を確認する問題は、出題されることが多いので、机上でフローチャートをシミュレートする練習をしましょう。
この種の問題は、実際にフローチャートの処理を一つずつ確認していく以外に解く方法がありませんので、あわてずにシミュレートしましょう。
なお、ユークリッドの互除法を用いたプログラムを実際に作るときは、剰余演算を用います。処理としては「Ｌ−Ｓ→Ｌ」が「（ＬをＳで割った時の余り）→Ｌ」になります。
