アルゴリズム(全91問中4問目)

スタディング 応用情報技術者講座
次の流れ図において,
 ①→②→③→⑤→②→③→④→②→⑥
の順に実行させるために,①においてmとnに与えるべき初期値aとbの関係はどれか。ここで,a,bはともに正の整数とする。
47.gif

出典:令和2年秋期 問47

  • a=2b
  • 2a=b
  • 2a=3b
  • 3a=2b
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
指定の順序通りに進むと次のように処理されていきます。
  1. m ← a,n ← b
  2. m<n で⑤の処理に進む
    n ← n-m
  3. m>n で④の処理に進む
    m ← m-n
  4. m=nとなり処理終了
⑤でnを1回更新、④でmを1回更新して、⑥の段階でm=nとなります。

まず直前の④の処理について考えます。
「m ← m-n」という処理をしているので、"更新前のm"の値は、"更新後のm"と"n"の和です。④の処理後は m=n になっていますから、"更新前のm"の値は 2n で表すことができます。

次に⑤の処理について考えます。
「n ← n-m」という処理をしているので、"更新前のn"の値は、"更新後のn"と"m"の和です。m=2n ですから、"更新前のn"の値は 3n で表すことができます。

これより前にはm及びnを更新する処理はないので、処理開始時に m:n=2:3 であれば最終的に m=n となることがわかります。mはa、nはbが代入される変数なので初期値aとbの関係は a:b=2:3、これを式に変換した「3a=2b」が正解です。

【別解】
① m←a、n←b
②→③→⑤ m<n(⇔a<b)より n←(n-m)=b-a
この時点で m=a、n=b-a
②→③→④ m>n(⇔a>b-a)より m←m-n=a-(b-a)=2a-b
この時点で m=2a-b、n=b-a
②→⑥ m=n⇔2a-b=b-a⇔3a=2b

この問題の出題歴


Pagetop