【基本情報技術者試験平成23年春期午後】問題と解答

[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成23年春期基本情報技術者午後問08

問08　　 必須問題

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

　N 個の要素中から K 個の要素を選ぶ組合せをすべて求める。例えば，５個の要素中から３個の要素を選ぶ組合せの場合，計 10 通りある組合せをすべて求める。

　プログラムでは，N 個の要素（要素番号 1 ～ N ）からなる配列 S を用意し，このうち K 個の要素には１を，残りの要素には０を設定することによって，組合せの一つを表現する。例えば，図１(1) のように５個の要素１～５中から３個の要素２，４，５を選んだ状態は，プログラム中では図１(2) のとおりに表現する。

　　　図１　５個の要素中から３個の要素を選ぶ例とそのプログラム中での表現

〔プログラムの説明〕

　プログラムは，主プログラム Main 並びに組合せを求めるための関数 Init 及び Next からなる。

　主プログラム Main

　機能：N＝５，K＝３として，５個の要素中から３個の要素を選ぶ組合せ計 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) 　主プログラム Main で，配列 S に組合せの一つの状態が得られるたびに，配列 S の内容を印字したい。印字には次の副プログラムを用いる。

副プログラム Dump （整数型：S[ ]，整数型：N）

　引数：S[ ] 及び N は入力用の引数である。

　機能：配列 S の先頭から N 個の要素に格納されている値を，１行に印字する。

　そのためには，主プログラム Main のαの部分をに示す部分と入れ替えればよい。

(2) 　関数 Next は，受け取った配列 S を要素番号の小さい方から検査し，連続する２要素の値がに見つかったものについて，その内容を入れ替える。続いて，配列 S の一部でその2要素の部分について関数 Init を呼ぶ。例えば，関数 Next の実行開始時点で，配列Sの要素番号 1 ～ 5 の内容が 1，0，1，0，1 であったとき，実行終了時点での配列Sの要素番号 1 ～ 5 の内容はとなる。