プログラムは分割して作る
プログラムはある目的を達成するために、コンピュータに実行して欲しい処理を記述したものです。プログラムはメインルーチンとサブルーチンに分けて記載します。
メインルーチンはプログラムの最初に実行する部分で、主な処理の流れを記載します。
サブルーチンはプログラムを小さな機能毎に分解したもので、メインルーチンや他のサブルーチンから呼び出されます。
下の図で言うと、サブルーチン①とサブルーチン③はメインルーチンから呼び出され、
サブルーチン②はサブルーチン①から呼び出されます。
・・・と言われても、イメージが湧かないと思うので、「子供と大人の数を入力したら入園料を計算してくれるプログラム」を例にメインルーチンとサブルーチンを見てみましょう。
メインルーチンはCalculateEntranceFee、
サブルーチンはCalculateTotalFeeとMessegeShowで、両方ともメインルーチンから呼び出されています。CalculateTotalFeeは入園料の計算をするサブルーチンで、MessegeShowは計算した入園料を表示するサブルーチンです。
メインルーチン(CalculateEntranceFee)には、
「ユーザから入力された値を受け取る→入園料の計算をする(CalculateTotalFee)
→計算結果を表示する(MessegeShow)」という処理の流れを記載しています。
サブルーチンは1つの機能のみを実装しているのでサブルーチンだけではプログラムとして成立しません。
サブルーチンには関数と手続がある
サブルーチンには、「受け取る値」と「処理した結果を元に返す値」が登場します。
入園料の計算をするCalculateTotalFeeはメインルーチンから子供の数と大人の数を受け取り、入園料を計算してメインルーチンに返しています。
このようにサブルーチンが他のサブルーチンやメインルーチンから受け取る値を「引数」と言い、呼び出し元に返す値を「戻り値」と言います。
サブルーチンの中には計算した入園料を表示するMessegeShowのように、処理の実行だけを行い、呼び出し元に戻り値を返さないものがあります。
戻り値を返すサブルーチンを「関数」、戻り値を返さないサブルーチンを「手続き」と言います。（プログラミング言語によって呼び方が異なりますが、基本情報での呼び方で解説しています。）
関数の書き方
関数は「f(n)=2n+1」のような書き方をします。この書き方をした場合、カッコ内に書かれたnが引数、2n+1が戻り値になります。
例えば、n=5の場合、f(5)=2×5+1=11となり、引数=5、戻り値=11となります。
特別な性質を持つ関数やプログラム
関数やプログラムには、特別な性質を持つものがあります。
再帰的(リカーシブ)
処理中に自分自身を呼び出すような関数の性質を「再帰的」と言います。
再帰的な関数の例を見てみましょう。
「1からnまでの整数を足し算した結果を返す関数」はこのようになります。
f(n)：if n≦1 then return 1 else return n＋f(n－1)
・n=1の時、戻り値f(1)=1
・n=1以外の時、戻り値f(n)=n+f(n-1)
n=1以外の時の戻り値の中には、f(n-1)と自分自身が含まれています。このような関数を再帰的な関数と呼びます。
n=5の時を例に上の関数の実際の処理を見てみましょう。
n=1~5の時の戻り値はそれぞれこのようになります。
・n=5のときf(5)=5+f(4)
・n=4のときf(4)=4+f(3)
・n=3のときf(3)=3+f(2)
・n=2のときf(2)=2+f(1)
・n=1のときf(1)=1
f(5)=5+f(4)なので、
f(5)=5+(4+f(3))=9+f(3)=9+(3+f(2))=12+f(2)=12+(2+f(1))=14+f(1)
=14+1=15となります。
BNF記法
プログラミングで構文を再帰的に定義する方法にBNF記法があります。
下の定義では1桁の数字の足し算を表現しています。この例を元にBNF記法を見てみます。
<Number>::=0|1|2|3|4|5|6|7|8|9
<Formula>::=<Number>”+”<Number>|<Formula>”+”<Number>
「<S>::=〇」は「Sは〇と定義する」を、「|」は「または」を意味します。
なので、【<Number>::=0|1|2|3|4|5|6|7|8|9】は、【Numberには0,1,2,3,4,5,6,7,8,9のどれかが入ること】を意味し、
【<Formula>::=<Number>”+”<Number>|<Formula>”+”<Number>】は、【FormulaにはNumber+NumberまたはFormula+Numberが入ること】を意味します。
FormulaにはNumber+Numberが入るので、例えば、2+3や8+5が入ります。
また、Formula＋Numberが入るので、例えば、Formula=2+3、Number=9の場合は、2+3+9が入ります。Formula=2+3+9、Number=1とすれば、Formula=2+3+9+1になり、足す数をどんどん増やしていくことが出来ます。
このようにBNF記法ではプログラムの構文を定義することが出来ます。
再入可能(リエントラント)
同時に複数の箇所から呼び出されても、お互いに干渉することなく正しい結果を返すような関数の性質を「再入可能」と言います。
基本情報技術者試験での出題例
サンプル問題問8、令和元年度秋期問11
基本情報技術者
科目A サンプル問題問8、午前試験 令和元年度秋期問11
自然数nに対して，次のとおり再帰的に定義される関数f(n)を考える。f(5)の値はどれか。
f(n)：if n≦1 then return 1 else return n＋f(n－1)
ア 6 イ 9 ウ 15 エ 25
正解は”ウ”
関数f(n)の戻り値は
・引数が1の場合、1
・引数が1以外の場合、n+f(n－1)
f(5)
=5+f(4) 【引数が5なので、f(5)=5+f(4)】
=5+(4+f(3)) 【引数が4なので、f(4)=4+f(3)】
=9+f(3)
=9+(3+f(2)) 【引数が3なので、f(3)=3+f(2)】
=12+f(2)
=12+(2+f(1)) 【引数が2なので、f(2)=2+f(1)】
=12+2+1 【引数が1なので、f(1)=1】
=15
よって、答えは15です。
令和元年度秋期問4
基本情報技術者
午前試験 令和元年度秋期問4
a及びbを定数とする関数 f(t)＝\(\displaystyle \frac{a}{t+1}\)及び g(t)＝\(\displaystyle \frac{b}{t²-1}\)に対して，\(\displaystyle \lim_{t \to \infty}\frac{g(t)}{f(t)}\)はどれか。ここで，a≠0，b≠0，t＞1とする。
ア 0 イ 1 ウ \(\frac{b}{a}\) エ \(\infty\)
正解は”ア”
まず、\(\displaystyle \lim_{t \to \infty}\frac{g(t)}{f(t)}\)の記号の意味について解説しておきます。\(\displaystyle \lim_{t \to \infty}f(t)\)は関数f(t)の引数であるtを無限大にした時の戻り値を意味します。
例えば、f(t)=t+2の場合、tを無限大にすればf(t)も無限大になるので、\(\displaystyle \lim_{t \to \infty}f(t)\)=\(\infty\)となります。
f(t)=\(\displaystyle \frac{1}{t+2}\)の場合、tを無限大にすればf(t)は0になります。t=8の場合はf(t)=\(\displaystyle \frac{1}{10}\)=0.1で、t=9998の場合はf(t)=\(\displaystyle \frac{1}{10000}\)=0.0001でになります。tを大きくすれば大きくする程、f(t)は小さくなっているので、tを無限大にすればf(t)は0になりそうですよね。
tを無限大にすると言われても想像しにくいと思うので、t=10、100、1000と大きくしたときに戻り値がどうなるかを考えれば良いと思います。
では、問題を実際に解いていきましょう。
\(\displaystyle \frac{g(t)}{f(t)}\)
=\(\displaystyle \frac{b}{t²-t}\)×\(\displaystyle \frac{t+1}{a}\)
=\(\displaystyle \frac{b(t+1)}{a(t²-t)}\)・・・①
a、b、tに具体的に数字を入れてみましょう。
aとbは0以外ならなんでも良いので、両方1だとして考えてみます。
t=10を①に代入してみましょう。
①=\(\displaystyle \frac{11}{90}\)=約0.12
次にt=100を①に代入してみましょう。
①=\(\displaystyle \frac{101}{9900}\)=約0.0102
次にt=10000を①に代入してみましょう。
①=\(\displaystyle \frac{10001}{99990000}\)=約0.0001
tを大きくすれば戻り値は小さくなっていますね。このことから、tを無限大にすれば最終的に戻り値が0になるだろうと想像できます。よって答えはアです。
令和元年度秋期問6
基本情報技術者
午前試験 令和元年度秋期問6
Random(n)は，0以上n未満の整数を一様な確率で返す関数である。整数型の変数A，B及びCに対して次の一連の手続を実行したとき，Cの値が0になる確率はどれか。
A＝Random(10)
B＝Random(10)
C＝A－B
ア \(\frac{1}{100}\) イ \(\frac{1}{20}\) ウ \(\frac{1}{10}\) エ \(\frac{1}{5}\)
正解は”ウ”
Random(10)は0以上10未満の整数を返すので、0,1,2,3,4,5,6,7,8,9を返します。
AとBの組み合わせは、
A=0のとき、B=0~9の10通り、
A=1のとき、B=0~9の10通り、
・
・
・
A=9のとき、B=0~9の10通り、で100通りあります。
このうち、C=0になるパターンは、
A=0のとき、B=0の1通り、
A=1のとき、B=1の1通り、
・
・
・
A=9のとき、B=9の1通り、で10通りあります。
よって、Cの値が0になる確率は\(\frac{10}{100}\)=\(\frac{1}{10}\)となります。
令和元年度秋期問7
基本情報技術者
午前試験 令和元年度秋期問7
次のBNFで定義される＜変数名＞に合致するものはどれか。
＜数字＞::＝ 0｜1｜2｜3｜4｜5｜6｜7｜8｜9
＜英字＞::＝ A｜B｜C｜D｜E｜F
＜英数字＞::＝＜英字＞｜＜数字＞｜_
＜変数名＞::＝＜英字＞｜＜変数名＞＜英数字＞
ア _B39 イ 246 ウ 3E5 エ F5_1
正解は”エ”
BNF記法では「<S>::=〇」は「Sは〇と定義する」を、「|」は「または」を意味します。
なので、
<数字>には、0~9のどれか1文字
<英字>には、A~Fのどれか1文字
＜英数字＞には、数字または英字または_のどれか1文字
＜変数名＞には、英字1文字または変数名の後ろに英数字1文字を付けたもの
が入ります。
変数名は英字1文字か変数名の後ろに英数字1文字を付けたものです。ア～エは全て2文字以上なので、変数名だとしても変数名の後ろに英数字1文字を付けたものになります。
ア～エの選択肢が変数名になり得るか確かめてみましょう。
【ア】
「_B39」が変数名ということは、「_B3」が変数名、「9」が英数字と言うことです。
「9」は数字1文字なので英数字でOKですね。では、「_B3」は変数名でしょうか？
「_B3」は英字1文字ではないので、変数名だとしたら変数名の後ろに英数字1文字を付けたものになるはずです。これも分解してみましょう。
「_B3」が変数名ということは、「_B」が変数名、「3」が英数字と言うことです。「3」は英数字でOKですね。では、「_B」は変数名でしょうか？これも英字1文字ではないので分解してみましょう。
「_B」が変数名ということは、「_」が変数名、「B」が英数字と言うことです。「B」は英数字でOKですね。では、「_」は変数名でしょうか？
「_」は英字1文字でもなければ、変数名の後ろに英数字1文字を付けたものでもありません。ということは「_」は変数名ではないということです。
「_」が変数名ではないということは「_B」は変数名ではないということで、
「_B」が変数名ではないということは「_B3」は変数名ではないということで、
「_B3」が変数名ではないということは「_B39」は変数名ではないということになります。
よって、アは間違いです。
他の選択肢もこのように分解して考えてみると答えはエになります。
実際にエの選択肢を見てみましょう。
【エ】
「F5_1」が変数名ということは、「F5_」が変数名、「1」が英数字と言うことです。
「1」は数字1文字なので英数字でOKですね。では、「F5_」は変数名でしょうか？
「F5_」は英字1文字ではないので、変数名だとしたら変数名の後ろに英数字1文字を付けたものになるはずです。これも分解してみましょう。
「F5_」が変数名ということは、「F5」が変数名、「_」が英数字と言うことです。「_」は英数字でOKですね。では、「F5」は変数名でしょうか？これも英字1文字ではないので分解してみましょう。
「F5」が変数名ということは、「F」が変数名、「5」が英数字と言うことです。「5」は英数字でOKですね。では、「F」は変数名でしょうか？
「F」は英字1文字なので変数名です。
「F」が変数名だということは「F5」は変数名だということで、
「F5」が変数名だということは「F5_」は変数名だということで、
「F5_」が変数名だということは「F5_1」は変数名だということになります。
よってエが正しいことが分かります。
平成31年度春期問8
基本情報技術者
午前試験 平成31年度春期問8
複数のプロセスから同時に呼び出されたときに，互いに干渉することなく並行して動作することができるプログラムの性質を表すものはどれか。
ア リエントラント
ウ リユーザブル
イ リカーシブ
エ リロケータブル
正解は”ア”
複数から呼び出されても互いに干渉することなく、正しい結果を返す性質をリエントラントと言います。
平成29年度秋期問6
基本情報技術者
午前試験 平成29年度秋期問6
再帰呼出しの説明はどれか。
ア あらかじめ決められた順番ではなく，起きた事象に応じた処理を行うこと
イ 関数の中で自分自身を用いた処理を行うこと
ウ 処理が終了した関数をメモリから消去せず，必要になったとき再び用いること
エ 処理に失敗したときに，その処理を呼び出す直前の状態に戻すこと
正解は”イ”
関数の中で自分自身を呼び出して処理する性質を再帰呼出しと言います。
平成29年度春期問6
基本情報技術者
午前試験 平成29年度春期問6
関数 f(x，y)が次のように定義されているとき，f(775，527)の値は幾らか。ここで，x mod yはxをyで割った余りを返す。
f(x，y): if y = 0 then return x else return f(y，x mod y)
ア 0 イ 31 ウ 248 エ 527
正解は”イ”
関数f(x，y)の戻り値は
・引数yが0の場合、x
・引数yが0以外の場合、f(y, x mod y)
f(775，527)
=f(527, 775 mod 527) 【引数yが0ではないので】
=f(527, 248) 【775÷527=1余り248】
=f(248, 527 mod 248) 【引数yが0ではないので】
=f(248, 31) 【527÷248=2余り31】
=f(31, 248 mod 31) 【引数yが0ではないので】
=f(31, 0) 【248÷31=8余り0】
=31 【引数yが0なので戻り値はx】
よって、答えは31です。
