本記事の内容
本記事は、基本情報技術者試験におけるアルゴリズムの基本について情報及びコンピュータの素人目線から説明する記事です。
本記事を読むに当たり、特別必要な知識はありません。
前回の記事(データの構造)は以下をご覧ください！
イントロ(アルゴリズムとは)
アルゴリズム
アルゴリズムとは、問題を解決するときの手順を指す。一般社会ではあまり聞き慣れないかも知れませんが、コンピュータの世界ではとても重要な用語です。
基本情報技術者試験では「流れ図」が頻出です。
アルゴリズムの表現方法
アルゴリズムは以下の4つの方法で表現されます。
- 文章：文字による表現
- 流れ図：図による表現
- 数式：関数による表現
- プログラム言語：コンピュータが理解できる言語による表現
今回は、「与えられた数値に対して、絶対値を返すアルゴリズム」を例に述べます。
文章
「与えられた数値に対し、絶対値を返すアルゴリズム」を文章で書けば、以下です。
① \(x<0\)ならば②へ、\(x\geq0\)ならば③へ。
② \(-x\rightarrow x\)
③ \(x\)を返す。
②の手順の中にある「\(\rightarrow\)」は代入を表します。
例えば、\(x=3\)ならば、\(x\)に\(-3\)を代入せよ、と言うことになります。
文章によるアルゴリズムの表現のメリットとしては、数学記号と文字さえ読めれば、その他の知識がなくてもアルゴリズムを理解できることです。
流れ図
流れ図(フローチャート)とは、アルゴリズムを視覚的にわかりやすく表現した図を指す。
「与えられた数値に対して、絶対値を返すアルゴリズム」を流れ図で表せば、次です。
流れ図で使用する記号
流れ図で使用する記号はJIS(日本産業規格)によって規格化されています。
基本情報技術者試験でよく出題されるのは、以下の5種類です。
記号を問題として問われることはありませんが、形状と役割は覚える必要があります。
ループ端の表記法は暗記不要
ループ端の中には繰り返し処理の条件が記入されています。
しかし、条件の記入方法は問題文中に必ず注記されますので、暗記不要です。
例えば、先程の図の例では、「変数名：初期値、増分、終値」という意味です。
すなわち、
- 変数\(i\)は「1」からはじまり(初期値)、
- ループ処理を繰り返すたびに「値は1ずつ増加」(増分)し、
- 「\(i\)が100になったとき」(終値)にループ処理が終わる
という意味です。
数式
「与えられた数値の絶対値を返すアルゴリズム」を数式で表せば、
$$
f(x)=
\begin{cases}
-x&(x<0)\\
x&(x\geq0)\end{cases}
$$
です(そりゃそうだ)。
関数
アルゴリズムにおける関数というのは、複数の処理をひとまとめにしたものです。
例えば、以下のような関数があります。
- 数値の絶対値を求める関数
- 数値を3倍する関数
- 現在の日付を表示する関数
などなどです。
「絶対値を求める関数」を利用すれば、いつでも任意の数値の絶対値を求めることが出来ますし、同様にして「数値を3倍する関数」を用いればその関数を呼び出すことでいつでも任意の数値を3倍することが出来ます。
関数を用いる上で、2つの用語を覚える必要があります。
- 引数：関数に渡す値。\(y=f(x)\)における\(x\)。
- 戻り値：関数が返す結果。\(y=f(x)\)における\(y\)。
プログラム言語
「与えられた数値の絶対値を返すアルゴリズム」をプログラム言語で表すと、以下です。
f(x):
if x<0 then
return -x
else
return xこの関数\(f(x)\)を流れ図で表すと、以下です。
また、この関数の書式は以下です。
f(x):
if 条件 then
条件が真なるときの処理
else
条件が偽なるときの処理尚、基本情報技術者試験においてアルゴリズムをプログラム言語で表すときは、以下のように1行で表されることが多いです。
f(x) : if x<0 then return -x else return x基本情報技術者試験では特定のプログラム言語(C言語やらJava言語やら)の書式は問われません。
故に、「if」「then」「else」「return」の4つの意味を理解しておくだけで読み解けます。
| キーワード | 意味 |
| if | 後ろに「条件」を書く。 |
| then | 後ろに「条件が正しいときの処理」を書く。 |
| else | 後ろに「条件が正しくないときの処理」を書く。 |
| return | 後ろに「戻り値」を書く。 |
復習問題
関数\(f(x,y)\)が次の通り定義されているとき、\(f(775,527)\)の値は幾らか。ここで、x mod yはxをyで割った余りを返す。
f(x,y): if y=0 then return x else return f(x, x mod y)
- 0
- 31
- 248
- 527
答え
2単純に計算すればOKです。
プログラムの意味としては、
- y=0が正しい場合はxを返す。
- y=0が正しくない場合は、f(y, x mod y)を返す。
です。
\begin{eqnarray}
f(775,527)&=&f(527,775\ {\rm mod }\ 527)\\
&=&f(527,248)\\
&=&f(248,527\ {\rm mod }\ 248)\\
&=&f(248,31)\\
&=&f(31,248\ {\rm mod }\ 31)\\
&=&f(31,0)\\
&=&31
\end{eqnarray}
結
今回は、基本情報技術者試験におけるアルゴリズムの基本について、情報及びコンピュータの素人目線から説明しました。
問題が解けるということに重きを置き説明しました。
アルゴリズムというのは問題を解決するときの手順を指すのでした。
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、この記事に限らず、「定理〇〇の△△が分からない！」などいただければお答えします！
Twitterでもリプ、DM問わず質問、コメントを大募集しております！
コメントをする