Re: [理工] [离散]-台大105-资工

楼主: outofyou   2017-09-08 16:49:05
※ 引述《JKLee (J.K.Lee)》之铭言:
: 标题: Re: [理工] [离散]-台大105-资工
: 时间: Tue Sep 5 21:36:49 2017
:
: 复述题目:
: 1 <= x_1 < x_2 < ... < x_n <= r
: 求 x_1 + x_2 + ... + x_n = r 之整数解的数量。
:
: 翻译题目为
: 将正整数r,整数分割为n个相异正整数的方法数。
:
: 假设所求为p(n,r)。
:
: 我目前只算出
: p(n,r) = 1, if n=1;
: p(n,r) = floor[(r-1)/2], if n=2;
: p(n,r) = 0, if n>1 and r < n*(n+1)/2;
: p(n,r) = 1, if r = n*(n+1)/2;
:
: 尝试用生成函数
: (1+yx^1)(1+yx^2)...(1+yx^r)
: 所求为y^n x^r 之系数
:
: 然后就卡住了
:
:
作者: JKLee (J.K.Lee)   2017-09-12 01:06:00
i=0~N是否要改成1~h
楼主: outofyou   2017-09-13 14:02:00
不可,在r-n*(1+n)/2 = 0的情况, F(0,0,n)=1 是必须的。但r-n*(1+n)2不为0时,因F(r - n*(1+n)2,0,n)=0,可不加因为F(N,0,n)=0 by N>h*w,每个input多一次+0的计算还好递回式里=0也要保留,例如F(5,5,3)=F(0,0,2)=1

Links booklink

Contact Us: admin [ a t ] ucptt.com