黄昏より暗きもの、血の流れより赤きもの

読者です 読者をやめる 読者になる 読者になる

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

【アルゴリズム】プログラミングコンテストチャレンジブック[第2版] P34の部分和問題を、boolを使わないで解いてみた

実務でプログラミングをしていると、どうしても基礎力が足りなくて手詰まりになる事が多い。又Project Eulerのような扱う整数も大きく、それなりの計算量の予想される場合に必要になって来るのがアルゴリズムに関する知識だ。

上記のような事態に備え、この日はプログラミングコンテストチャレンジブック(第2版) P34の部分和問題を復習した。以下問題を紹介したい。

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

P34の問題はこちら(一部改変)

n個の整数からなる数列a_1,a_2,,,a_nがある。この中からいくつか選び、その和をちょうどkにする事が出来るかを判定せよ。尚このような問題の事を部分和問題と言う。

制約条件

1 \leq n \leq 20
-10^8 \leq a_i \leq 10^8
-10^8 \leq k \leq 10^8

別解

部分和問題を解くコツは数列a[i]を使うか使わないかで場合分けし、それを上手く振り分けて再帰させて行く事だ。筆者もノートでソースコードを書いて、何度も何度も間違えた。

話変わってこの本のP52にはナップサック問題とその解答が書かれていて、練習の為にそのやり方でやってみた。最後に、そのソースコードを紹介したい。

ソースコード(C言語版)

実行結果

実行結果は以下の通り。このように無事に上手く動作している。

max=13
YES

別解(Python版)

機械学習などについて調べていると、どこもかしこもRubyPython。Web系企業の求人を見てみても、Ruby On Rails等を採用する企業も少なくない。自分はその内Pythonを覚え、scikit-learnと言ったライブラリを使いこなそうと思い練習に励んだ。

Pythonを使ってみて...

Pythonの悪い点はインタプリタで動作している為、本問で言うなら配列の要素数nが大きいときに処理時間がかかると言う点。良い点は後発に登場した言語なのもあり、関数やライブラリが整備されていて、気軽にアイデアを試しやすい点だ。numpyを使ってみても、ベクトルの内積の計算をnumpy.dot関数*1一発で出来るし、情報も充実しているのも良い。

本問の場合でもlen関数で配列の要素数を取得でき、変数が少なく見通しが良い点も良い。C言語だと「sizeof id /sizeof a[0]」*2と言うように配列そのものが占有しているメモリ容量から要素数を割り出さねばならず、この作業が省略される点も良い。

ソースコードのみ掲載

最後に

自分自体やる気も起きないが、アルゴリズムにおける再帰の仕組みなどを詳しく勉強したいと言う場合は関数型言語(PascalHaskell、OCML、Scala等)を使いたい。大学等で関数型言語を扱うのも、こうした再帰を使ったアルゴリズムを理解させる事にある事を今更気づいた。従ってこういう問題を解く上では、for文ループを出来る限り封印する事も大切だと常々思う。