応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。
カテゴリ:

2.プログラミング > 2.3 アルゴリズム

過去問(H25秋AP午前問9)を見てみましょう。
問9 未整列の配列α[i] (i=1,2, …,n)を,流れ図で示すアルゴリズムによって昇順に整列する。n=6でa[1]〜a[6]の値がそれぞれ, 21,5,53,71,3,17の場合,流れ図において,a[j-1]とa[j]の値の入替えは何回行われるか。
流れ図

ア 3  イ 6  ウ 8 エ 15

この問題を使って、流れ図の記号の意味を解説します。
loop

流れ図に関する過去問(H27秋AP午前問6)を見てみましょう。

問6 次に示すユークリッドの互除法(方法1,方法2)で,正の整数a, bの最大公約数は,それぞれmとnのどちらの変数に求まるか。ここで,mod nは,mをnで割った余りを表す。
flow



フローチャートに関して過去問(H27春IP問59)では、「プログラムの処理手順を図式を用いて視覚的に表したもの」と述べられています。

過去問(H27春IP問48)では、以下の流れ図があります。
問48 表に示す構成のデータを,流れ図の手順で処理する場合について考える。流れ図中のx,y,zをそれぞれデータ区分A, B, Cと適切に対応させれば,比較(“xか?”,“yか?”',“zか?”)の回数の合計は,最低何回で済むか。
流れず

ア 170  イ 190  ウ 230  工 250

問6 次の流れ図の処理で,終了時のxに格納されているものはどれか。ここで,与えられたa,bは正の整数であり,mod(x,y)はxをyで割った余りを返す。問6_1



実際に数字を入れてみるといいでしょう。
mod(x,y)はxをyで割った余りを返す。とありますから、xの方を大きくしましょう。
たとえば、a=10、b=3とします。
x=10、y=3

ループ1の1回目(y=0ではないので)
t=1(10÷3=3 余り1)
x=3
y=1

ループ1の2回目(y=0ではないので)
t=0
x=1
y=0
つまり、x=1であることが分かります。では、選択肢の4つを見ると
ア aとbの最小公倍数 ⇒30なので×
イ aとbの最大公約数 ⇒1なので○
ウ aとbの小さい方に最も近い素数 ⇒1なので○
エ aをbで割った商 ⇒3なので×
よって、イかウです。

イではないかとあたりをつけて、a=12、b=8、xが最大公約数である4になるかを確かめましょう。
たとえば、a=12、b=8とします。
x=12、y=8

ループ1の1回目(y=0ではないので)
t=4(12÷8=1 余り4)
x=8
y=4

ループ1の2回目(y=0ではないので)
t=0
x=4
y=0
と、xが最大公約数である4になりました。これは、選択肢ウのaとbの小さい方に最も近い素数である2とも違います。よって、イが正解です。

過去に似たような問題が出題されていますので、このアルゴリズムは最大公約数を求めるものだと覚えておくとよいでしょう。

このページのトップヘ