指定されたn個の異なる数(自然数)の中から任意の個数の数を選択し、それらの合計が指定された目標Xに最も近くなる数の組合せを1組選択する。その際、合計はXよりも大きくても小さくてもよい。ただし、同じ数は1回しか選択できないものとする。例えば、指定されたn個の数が(10, 34, 55, 77)、目標Xが100とすると、選択した数の組合せは(10, 34, 55)、選択した数の合計(以下、合計という)は99となる。この問題を解くためのアルゴリズムを考える。指定されたn個の数の中から任意の個数を選択することから、各数に対して、選択する、選択しない、の二つのケースがある。数を一つずつ調べて、次の数がなくなるまで"選択する"、"選択しない"の分岐を繰り返すことで、任意の個数を選択する全ての組合せを網羅できる。この場合分けを図1に示す。
図1の場合分けをプログラムで実装するために、必要となるデータ構造を検討する。まず、図1の場合分けを木構造とみなしたときの各ノード(状態)を構造体Statusで表す。構造体Statusは要素として"合計","選択した数","次の数"をもつ必要がある。プログラムで使用する配列、変数及び構造体を表1に示す。
図2中のオ、カに入れる適切な字句を答えよ。
(1) 【探索の手順】での記述どおり、データ構造にキューを使用した場合 (2) 本文中のキューを全てスタックに置き換えた場合
解答群から適切な字句を選択
事前処理の内容と理由を述べよ