Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

平成23年度特別基本情報午後問8

情報処理技術者試験 C

平成23年度特別試験 基本情報技術者試験(FE)の午後問題8は、

  • N個の要素中からK個の要素を選ぶ組合せを全て求める

問題でした。

f:id:rahaema:20190110195440p:plain

プログラム例(h23t_fe_pm8.c)

疑似言語をC言語で書き換えたものが以下です。疑似言語では配列のインデックスが1から始まるのに対し、C言語では0から始まりますので、変更したものについてはコメントで「注意」と記しています。

アルゴリズムとしては、以下のような流れのようです。

  1. 配列に対して、最初の(左から)k個分1を立てる。残りは0とする(initの仕事)

  2. 配列を左から見ていき、初めて出会った10(イチゼロ)を01(ゼロイチ)とする。このとき、10(イチゼロ)の左側に1が何個あったかを変数cでカウントしておく。

  3. 上記の10(イチゼロ)の左側の配列に対して、init(s, l, c)を実行。すなわち10(イチゼロ)の左側に左寄せでc個分1を立てる。

実行結果

以下が{}_5C_3の実行結果です。「数字:」で始まる行がプログラムの出力、それ以外の行はアルゴリズムの理解のために書き足した分です。

\begin{eqnarray} {}_5C_3 & = & {}_5C_2 \\ & = & \frac{5\cdot4}{2\cdot1}\\ & = & 10 \end{eqnarray}

ですので、10通り分出力されていることが分かります。

 1: 1 1 1 0 0 
    1 1 0 1 0 
 2: 1 1 0 1 0 
    1 0 1 1 0 
 3: 1 0 1 1 0 
    0 1 1 1 0 
 4: 0 1 1 1 0 // 左から見て最初の10を
    0 1 1 0 1 // 01へ
 5: 1 1 0 0 1 // 2個の1を左に寄せる
    1 0 1 0 1
 6: 1 0 1 0 1
    0 1 1 0 1
 7: 0 1 1 0 1
    0 1 0 1 1
 8: 1 0 0 1 1
    0 1 0 1 1
 9: 0 1 0 1 1
    0 0 1 1 1
10: 0 0 1 1 1

関連