基本情報技術者 2011年 春期 午後 問08
次のプログラムの説明及びプログラムを読んで、設問に答えよ。
N個の要素中からK個の要素を選ぶ組合せをすべて求める。例えば、5個の要素中から3個の要素を選ぶ組合せの場合、計10通りある組合せをすべて求める。
プログラムでは、N個の要素（要素番号1〜N）からなる配列Sを用意し、このうちK個の要素には1を、残りの要素には0を設定することによって、組合せの一つを表現する。例えば、図1(1)のように5個の要素1〜5中から3個の要素2、4、5を選んだ状態は、プログラム中では図1(2)のとおりに表現する。
〔プログラムの説明〕
プログラムは、主プログラムMain並びに組合せを求めるための関数Init及びNextからなる。
主プログラムMain
機能：N = 5、K = 3として、5個の要素中から3個の要素を選ぶ組合せ計10通りを順次求めて、配列Sに設定する。
整数型関数：Init(整数型：S[], 整数型：N, 整数型：K)
引数：S[]は出力用、N及びKは入力用の引数である。
機能：1 ≦ K ≦ Nの場合、配列Sの先頭からK個の要素に1を、続くN − K個の要素に0をそれぞれ設定し、返却値として0を返す。それ以外の場合、配列Sには値を設定せずに、返却値として−1を返す。
整数型関数：Next(整数型：S[], 整数型：N)
引数：S[]は入出力用、Nは入力用の引数である。
機能：渡された配列Sの先頭からN個の要素には、直近に求めた組合せの状態が設定されている。この渡された組合せの状態に対して所定の操作を行い、次の組合せの状態を求めて配列Sに設定し、返却値として0を返す。ただし、渡された組合せの状態が、この関数のアルゴリズムで得られる最終形である場合、配列Sには値を設定せずに、返却値として−1を返す。
設問1：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
(1) 主プログラムMainで、配列Sに組合せの一つの状態が得られるたびに、配列Sの内容を印字したい。印字には次の副プログラムを用いる。
副プログラムDump(整数型：S[], 整数型：N)
引数：S[]及びNは入力用の引数である。
機能：配列Sの先頭からN個の要素に格納されている値を、1行に印字する。
そのためには、主プログラムMainのαの部分をaに示す部分と入れ替えればよい。
(2) 関数Nextは、受け取った配列Sを要素番号の小さい方から検査し、連続する2要素の値がbに見つかったものについて、その内容を入れ替える。続いて、配列Sの一部でその2要素cの部分について関数Initを呼ぶ。例えば、関数Nextの実行開始時点で、配列Sの要素番号1〜5の内容が1, 0, 1, 0, 1であったとき、実行終了時点での配列Sの要素番号1〜5の内容はdとなる。
(3) このプログラムを実行して、関数Initが関数Nextから呼ばれるとき、関数Initが受け取るNの値の範囲はe、Kの値の範囲はfである。したがって、関数Initが受け取るNとKの値は、1 ≦ K ≦ Nを満たさない場合がある。
(4) 主プログラムMainの実行終了時点において、配列Sの要素番号1〜5の内容はgとなっている。
aに関する解答群
bに関する解答群
ア：0, 1で最後
イ：0, 1で最初
ウ：1, 0で最後
エ：1, 0で最初
cに関する解答群
ア：及びその後
イ：及びその前
ウ：より後
エ：より前
dに関する解答群
ア：0, 1, 1, 0, 1
イ：1, 0, 0, 1, 1
ウ：1, 0, 1, 1, 0
エ：1, 1, 0, 0, 1
e, fに関する解答群
ア：0〜2
イ：0〜3
ウ：1〜3
エ：1〜4
オ：2〜4
カ：2〜5
gに関する解答群
ア：0, 0, 0, 0, 0
イ：0, 0, 1, 1, 1
ウ：1, 1, 1, 0, 0
エ：1, 1, 1, 1, 1
模範解答
a：ア、b：エ、c：エ、d：ア、e：イ、f：ア、g：イ
解説
解答の導き方
配列は、番号の付いた場所にデータを並べて保存するものです。このプログラムでは、選んだ要素に対応する場所へ1を、選ばなかった要素に対応する場所へ0を入れます。
(1) 組合せをすべて印字する方法
最初にInitを実行すると、先頭から個に1が設定されます。なので、配列は1, 1, 1, 0, 0になります。
印字したいのは、最初の組合せと、その後にNextで求める組合せです。そのため、繰返しの中では、まず現在の配列をDumpで印字し、その後にNextで次の組合せを求めます。
この順序なら、最初の組合せも印字できます。最後の組合せを印字した後、Nextが−1を返して繰返しが終わります。したがって、αには、繰返しの中でDumpを実行してからNextを実行するアを入れます。
(2) Nextが探す並びと、配列の変化
Nextでは、を1から順に増やしながら、隣り合う2要素を調べます。で、の並びが見つかると、その2要素を入れ替えます。
最初に見つかった「1, 0」を入れ替えるため、bは「1, 0で最初」のエです。
入れ替えた後、Initには、、を渡します。Initは渡された個の要素だけを書き換えるので、この場合は配列の先頭から個、つまり入れ替えた2要素より前の部分を書き換えます。したがって、cは「より前」のエです。
dの例では、実行開始時の配列は1, 0, 1, 0, 1です。最初ので、かつなので、この2要素を入れ替えます。
- 入れ替え後：0, 1, 1, 0, 1
- Initに渡す値：、
Initは「1≦K」を満たさないとき、配列に値を設定しません。ここではなので、配列はそのままです。よって、実行終了時の配列は0, 1, 1, 0, 1となり、dはアです。
(3) NextからInitに渡されるNとKの範囲
NextからInitが呼ばれるのは、最初の「1, 0」を見つけて入れ替えたときです。次の表は、Mainの実行中に起こる入れ替えと、Initに渡される値を並べたものです。表の「Initの引数」は、、の順です。
この表で、Initに渡されるの最小値は0、最大値は3です。したがって、eは0〜3のイです。
の最小値は0、最大値は2です。したがって、fは0〜2のアです。
表には、例えば、のように、Initの条件「1≦K≦N」を満たさない呼出しもあります。その場合、Initは配列を書き換えずに−1を返します。ただし、NextではInitの返却値を変数に代入せず、その後にを実行します。そのため、Initが−1を返しても、Nextの返却値がそれによって−1になるわけではありません。
(4) Mainの実行終了時の配列
表の最後の配列は0, 0, 1, 1, 1です。この状態では、左から調べても「1, 0」は見つかりません。したがって、次のNextは配列を書き換えずに−1を返し、Mainの繰返しが終わります。
そのため、実行終了時の配列も0, 0, 1, 1, 1のままです。gはイです。
誤りやすいポイント
- DumpをNextの後に置くと、最初の組合せを印字できません。印字したい状態を先に表示してから、次の状態を求めます。
- Nextが探すのは「0, 1」ではなく「1, 0」です。また、を小さい方から調べるため、最初に見つかった並びを入れ替えます。
- Initに渡すは、Mainで使うではありません。Nextが渡す値はです。も、Mainのではなく、Next内で数えたです。
- Initが−1を返したとき、配列に値を設定しない点に注意してください。値を設定しないので、入れ替え後の配列はそのまま残ります。
FAQ
Q: Initが−1を返したのに、Nextが0を返すことがあるのはなぜですか？
A: Nextは、Initの呼出し結果を変数に代入していません。その後にを実行するため、Initが−1を返しても、Nextの返却値は0になります。
Q: は何を数えていますか？
A: Nextが見つけた「1, 0」のうち、1の位置より前にある1の個数です。Nextはその数を使い、入れ替えた2要素より前の部分をInitで設定します。
Q: 最後の組合せの後、なぜ配列が変わらないのですか？
A: 最後の配列0, 0, 1, 1, 1には「1, 0」がありません。Nextは配列を書き換える処理をせずに−1を返すため、最後の配列がそのまま残ります。
関連キーワード: 配列、組合せ、擬似言語、ループ、条件分岐
