Ｈ２３_ｈａｒｕ_ＦＥ_ＰＭ Ｑ０８ Ｑｕｓ．

平成２３年 春期 基本情報技術者 午後 問８

問　８　次のプログラムの説明及びプログラムを読んで、設問に答えよ。

Ｎ個の要素中からＫ個の要素を選ぶ組合せをすべて求める。
例えば、５個の要素中から３個の要素を選ぶ組合せの場合、計１０通りある組合せをすべて求める。
プログラムでは、Ｎ個の要素（要素番号　１～Ｎ）からなる配列Ｓを用意し、このうちＫ個の要素には１を、残りの要素には０を設定することによって、組合せの一つを表現する。
例えば、図１（１）のように５個の要素１～５中から３個の要素２，４，５を選んだ状態は、プログラム中では図１（２）のとおりに表現する。

［プログラムの説明］
プログラムは、主プログラム　Ｍａｉｎ　並びに
組合せを求めるための関数　Ｉｎｉｔ　及び　Ｎｅｘｔ　からなる。

主プログラム　Ｍａｉｎ
機能：Ｎ＝５，Ｋ＝３　として、５個の要素中から３個の要素を選ぶ組合せ
計１０通りを順次求めて、配列　Ｓ　に設定する。
整数型関数：　Ｉｎｉｔ（整数型：Ｓ［］，整数型：Ｎ，整数型：Ｋ）
引数：Ｓ［］　は出力用、Ｎ　及び　Ｋ　は入力用の引数である。
機能：１≦Ｋ≦Ｎ　の場合、配列　Ｓ　の先頭から　Ｋ　個の要素に　１　を、
続く　Ｎ－Ｋ　個の要素に　０　をそれぞれ設定し、返却値として　０　を返す。
それ以外の場合、配列　Ｓ　には値を設定せずに、返却値として　－１　を返す。
整数型関数：　Ｎｅｘｔ（整数型：Ｓ［］，整数型：Ｎ）
引数：Ｓ［］　は入出力用、Ｎ　は入力用の引数である。
機能：渡された配列　Ｓ　の先頭から　Ｎ　個の要素には、
直近に求めた組合せの状態が設定されている。
この渡された組合せの状態に対して所定の操作を行い、
次の組合せの状態を求めて配列　Ｓ　に設定し、返却値として　０　を返す。
ただし、渡された組合せの状態が、
この関数のアルゴリズムで得られる最終形である場合、
配列　Ｓ　には値を設定せずに、返却値として　－１　を返す。

設問
次の記述中の［　　］に入れる正しい答えを、解答群の中から選べ。

（１）
主プログラム　Ｍａｉｎ　で、配列　Ｓ　に組合せの一つの状態が得られるたびに、
配列　Ｓ　の内容を印字したい。
印字には次の副プログラムを用いる。

副プログラム　Ｄｕｍｐ（整数型：Ｓ［］，整数型：Ｎ）
引数：Ｓ［］　及び　Ｎ　は入力用の引数である。
機能：配列　Ｓ　の先頭から　Ｎ　個の要素に
格納されている値を、１行に印字する。

そのためには、主プログラム　Ｍａｉｎ　の　α　の部分を
［　ａ　］に示す部分と入れ替えればよい。

（２）
関数　Ｎｅｘｔ　は、受け取った配列　Ｓ　を要素番号の小さい方から検査し、
連続する２要素の値が［　ｂ　］に見つかったものについて、その内容を入れ替える。
続いて、配列　Ｓ　の一部でその２要素［　ｃ　］の部分について関数　Ｉｎｉｔ　を呼ぶ。
例えば、関数　Ｎｅｘｔ　の実行開始時点で、
配列　Ｓ　の要素番号１～５が、１，０，１，０，１　であったとき、
実行終了時点での配列　Ｓ　の要素番号１～５の内容は［　ｄ　］となる。

（３）
このプログラムを実行して、関数　Ｉｎｉｔ　が関数　Ｎｅｘｔ　から呼ばれるとき、
関数　Ｉｎｉｔ　が受け取る　Ｎ　の値の範囲は［　ｅ　］
Ｋ　の値の範囲は［　ｆ　］である。

（４）
主プログラム　Ｍａｉｎ　の実行終了時点において、
配列　Ｓ　の要素番号１～５の内容は［　ｇ　］となっている。

ａ　に関する解答群

ｂ　に関する解答群
ア　０，１で最後
イ　０，１で最初
ウ　１，０で最後
エ　１，０で最初

ｃ　に関する解答群
ア　及びその後
イ　及びその前
ウ　より後
エ　より前

ｄ　に関する解答群
ア　０，１，１，０，１
イ　１，０，０，１，１
ウ　１，０，１，１，０
エ　１，１，０，０，１

ｅ，ｆ　に関する解答群
ア　０～２
イ　０～３
ウ　１～３
エ　１～４
オ　２～４
カ　２～５

ｇ　に関する解答群
ア　０，０，０，０，０
イ　０，０，１，１，１
ウ　１，１，１，０，０
エ　１，１，１，１，１

解答と解説