- 最后登录
- 2017-10-10
- 在线时间
- 88 小时
- 阅读权限
- 20
- 注册时间
- 2008-3-19
- 积分
- 421
- 帖子
- 233
- 精华
- 2
- UID
- 25681
- 性别
- 保密

- 积分
- 421
- 帖子
- 233
- 精华
- 2
- UID
- 25681
- 性别
- 保密
|
<P><CITE>Cielo,你真强!你的解答很令人满意,<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> </CITE></P>
<P><CITE></CITE> </P>
<P><CITE>我昨天翻了一下《组合数学基础》,找到了解决这个问题的方法,如下:</CITE></P>
<P><CITE></CITE> </P>
<P><CITE>如果不缺那个角,这个问题相当与从0~4中取五次数,理解方法可以看附件中的图。</CITE></P>
<P><CITE></CITE> </P>
<P><CITE>设取出的0~4的个数分别为x0,x1,x2,x3,x4,则问题变为 x0+x1+x2+x3+x4=5</CITE>的非负解的个数。</P>
<P> </P>
<P>对于x1+...+xn=r,非负解的个数为C(n+r-1,r),对于本题为C(5+5-1,5)=C(9,5)。</P>
<P> </P>
<P>原理是:相当于往r个球当中放入n-1个挡板,比如本题相当于往5个球中放4个挡板,也就是9个位置选4个</P>
<P> </P>
<P>O|O|O|O|O,代表了x0=1,x1=1,x2=1,x3=1,x4=1,也就是01234。</P>
<P>|OOOO||O|,代表了x0=0,x1=4,x2=0,x3=1,x4=0,也就是11113。</P>
<P> </P>
<P>最后问题的解是A-B的路径数减去A-C的路径数,因为经过C再到B的肯定也是最短路径</P>
<P>C(5+5-1,5)-C(5+2-1,2)=C(9,5)-C(6,2)=C(9,4)-C(6,2)=9*8*7*6/4/3/2-6*5/2=126-15=111</P>
<P> </P>
<P>相对我的这个方法还是Cielo的方法理解简单一些。</P>
[ 本帖最后由 金眼睛 于 2008-5-22 15:02 编辑 ] |
|