プログラミングで頭の体操（１）
どうも。また例によって認証ネタとして「公開鍵認証でも説明しようかなー」などと予定していたのですが、今日ちょっとした頭の体操をしてみたのでそちらを記事にしてみようかなと。
パッと思いついただけの問題なのでここで導き出した解答に対して信用できるソースはないです。
勿論十分な自信があるから記事にしているわけですが、もし間違ってたら「このクソ間抜けが」などの言葉と共に正解を教えていただきたいなーくらいのアレです(えぇ…)
問題：ある物体がn個ある。このn個の物体を任意に隣接させても良いとして、これらを一列に並べた際の組み合わせ数を出力するプログラムを書け。※順列と組み合わせの違いに注意されたし。
例：入力値=4のとき
1+1+1+1
1+1+2
1+3
2+2
4
今回は独自の表現として、隣接数をそのまま数字で表し、それらを「+」で区切るものとする。
組み合わせでは1+2+1と1+1+2などを区別しないためこれら5通りが答えとなる。
※以下解答
物体xがn個の場合において
0+n
1+(n-1) 1+1+(n-2) ・・・
2+(n-2) ・・・
3+(n-3) ・・・
・・・
と書いてみる。
以下では便宜上、左端の数字がｍの行を階層ｍと呼ぶ。
また、本格的に問題について考える前に、いくつかルール(?)を設ける。
ルール1：階層ｍにおいて、ｍ個未満の隣接は許されない。
？？？？なんだこのルール？？？って思ったかもしれません。
しかし、よく考えてみれば、階層mの時点でm個の隣接が含まれるパターンは網羅されています。つまり、階層m+1でm個の隣接を許してしまうと階層mと階層m+1で重複するパターンが発生します。このルールは例えば、n=5の階層2において、2+3は許しても2+2+1は許さないことを意味します。2+2+1という組み合わせは階層1ですでに1+2+2として挙げられていますので。
ルール2：階層におけるｍの最大値Mは入力値ｎを2で割って少数点以下切り捨てとする。
まあこれはルール1と合わせて考えれば自明ですね。
入力値が11なら階層は5までしかないということです。階層6だと開始が6+5でルール1に反するので。
ちなみに、ルールではありませんが、ここでは入力値nに対して問題を解く関数をfunc(n)と表記していきます。
では長くなりましたが上記ルールを前提に解答していきます。
まず階層0については入力値に関わらず1となるのが自明。
続いて階層1についてですが、まずはルール1を思い出してみましょう。この階層では1個の隣接が1つ以上含まれているすべての組み合わせが含まれます。
入力値nの階層1において最も簡単な組み合わせは1+(n-1)です。
気づいた方もいるかもしれませんが、これは1+{(n-1)個の物体の任意な配置パターン}と置き換えることができ、つまりはfunc(n-1)がそのまま階層1の組み合わせ数となります。
入力値nの階層2以降についても階層1と同じ理屈+αで再帰処理できます。
なぜプラスアルファかといいますと、func(n-1)は階層1なので気にしなくても良かったのですが、階層2以降では重複を避ける必要があります。func(n-2)をそのまま使うとfunc(n-2)におけるすべての組み合わせが引っかかるので当然階層1の内容が含まれてしまいます。func(n-3)も同様で、今度は階層1,2が含まれないように工夫する必要があります。
疑似コードよくわからないのですがそれっぽく書きますと、
階層2 for(2->(n-2)/2) -> func(n-2)
階層3 for(3->(n-3)/2) -> func(n-3)
階層4 for(4->(n-4)/2) -> func(n-4)
・・・
これらを定式化すると
階層m for(m->(n-m)/2) -> func(n-m) ・・・(１)
これを踏まえ全体をJavaプログラムで書くなら、
private int pattern = 0;//数え上げ用
//入力用関数
public int func ( int obj ) {
return func ( obj ,1 ) ;
}
//再帰用関数
private int func (int obj , int m ) { // obj=入力値 , m=階層
pattern++; //数え上げ処理
// 定式化した(1)式
for ( int current=m ; current <= obj/2 ; current++ ){
func ( obj – current , current );
}
return pattern; //出力
}
となります。入力用の関数に好きな値を入れれば表題の組み合わせ数が出力されます。 例： System.out.print( func(11) ) ; → 56
どうでしたか？驚くほど簡単なコードに収まって僕もびっくりです。
大体こういうのって解き方だけならそうでもないのですが、説明したり、コードに書き起こしたりが難しいんですよねぇ。多分今回の説明クソですし