正数分割の個数
最近、組み分けの問題を考える機会があって、
アルゴリズム辞典を見てみると、「正数分割の個数」(同じ問題と言える)を求めるプログラム(元はPascal)があったのですが、正直言ってなぜこれで求めることができるのか理解できませんでした。
どうしてこのプログラムで、件数を求めることができるのか教えてください。
プログラムは、以下のようなもの(C言語で書き直したもの)
/*
ある正数nを分割する(正数の和で表す表し方の)数を求める
例
4:4,1+3,2+2,1+1+2,1+1+1の5通り
partition(4,4)→5
*/
int partition(int n, int k){
int p,i;
if(n<0) return 0;
if(n<2 || k==1) return 1;
for(p=0,i=1;i<=k;i++){
p+=partition(n-i,i);
}
return p;
}
お礼
(負数)×(負数)=(正数)・・・・・・・(A) を証明する時 (-1)×(-1)=(+1)・・・・・(B) (-2)×(-4)=(+8)・・・・・(C) (B)には”1”が3個でてくる。 (C)には「2,4,8」が出てきて、わかりやすい。 が、まず、(B)を証明する。 複素数体>実数体である。つまり、複素数で成り立つことは、 実数でも成り立つ。一般的にb=0の時、a+bi=a+0i=aとなる。 (B)の証明 (-1)であるが、これを実数とみてはいけない。(-1)=-1+0iとみる。 つまり複素数とみる。 そのまえにオイラーの公式と言うものがある。 (-1)=e^(π)・・・・・(D)これを(B)式へ代入する。 (-1)×(-1) =e^(π)×e^(π) =e^(π+π) =e^(2π) =(+1)これで、(B)式が証明された。 (C)式も同様に証明される。よって(A)式が証明された。
補足
基本的なことなので (負数)×(負数)=(正数) は難しいです。証明が。