HOME»基本情報技術者平成23年特別問題»午後問8
基本情報技術者過去問題 平成23年特別 午後問8
⇄問題文と設問を画面2分割で開く⇱問題PDF問8 データ構造及びアルゴリズム
次のプログラムの説明及びプログラムを読んで,設問に答えよ。
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個の要素中から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に設定する。
- 引数:
- S[ ]は出力用,N及びKは入力用の引数である。
- 機能:
- 1≦K≦Nの場合,配列Sの先頭からK個の要素に1を,続くN-K個の要素に0をそれぞれ設定し,返却値として0を返す。それ以外の場合,配列Sには値を設定せずに,返却値として-1を返す。
- 引数:
- S[ ]は入出力用,Nは入力用の引数である。
- 機能:
- 渡された配列Sの先頭からN個の要素には,直近に求めた組合せの状態が設定されている。この渡された組合せの状態に対して所定の操作を行い,次の組合せの状態を求めて配列Sに設定し,返却値として0を返す。ただし,渡された組合せの状態が,この関数のアルゴリズムで得られる最終形である場合,配列Sには値を設定せずに,返却値として-1を返す。
設問
次の記述中の に入れる正しい答えを,解答群の中から選べ。
- 主プログラムMainで,配列Sに組合せの一つの状態が得られるたびに,配列Sの内容を印字したい。印字には次の副プログラムを用いる。
副プログラムDump(整数型: S[ ],整数型: N)- 引数:
- S[ ]及びNは入力用の引数である。
- 機能:
- 配列Sの先頭からN個の要素に格納されている値を,1行に印字する。
- 関数Nextは,受け取った配列Sを要素番号の小さい方から検査し,連続する2要素の値がbに見つかったものについて,その内容を入れ替える。続いて,配列Sの一部でその2要素cの部分について関数Initを呼ぶ。例えば,関数Nextの実行開始時点で,配列Sの要素番号1~5の内容が1,0,1,0,1であったとき,実行終了時点での配列Sの要素番号1~5の内容はdとなる。
- このプログラムを実行して,関数Initが関数Nextから呼ばれるとき,関数Initが受け取るNの値の範囲はe,Kの値の範囲はfである。したがって,関数Initが受け取るNとKの値は,1≦K≦N を満たさない場合がある。
- 主プログラム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:
解答
- a=ア
- b=エ
- c=エ
- d=ア
- e=イ
- f=ア
- g=イ
解説
この設問の解説はまだありません。