作者link31204 (link)
看板Examination
标题Re: [考题] 计概/资料结构
时间Wed Apr 3 12:44:58 2013
※ 引述《dragoken (流星)》之铭言:
: 请问二元搜寻树插入顺序要如何求?
: 麻烦各位大大解惑。
: http://miupix.cc/pm-5CNFDU
如果答案是八十的话 可能是这样算的
第一个选4这就不用说了
选4後选2和选6可以得到一样多种可能(因为图形对称)
也就是一开始插入4,2,x,x,x,x,x 的可能如果有P种
一开始插入4,6,x,x,x,x,x 也有P种可能
所以只找一个继续算下去
我用先选4後选2 继续说下去
选4选2後面临三条路径 1 or 3 or 6
此时可以选1或选3 如果插入的顺序是 4,2,1,x,x,x,x 有Q种可能
和4,2,3,x,x,x,x 也有Q种 (差不多同上P种的意义)
但4,2,6,x,x,x,x会有不同可能 W种 (等等会计算出来)
接下来就是解决Q种到底是多少种!?
以4,2,1,x,x,x.x 来说下一个x 选3 有两种可能 4,2,1,3,6,5,7 和 4,2,1,3,6,7,5两种
若4,2,1,x,x,x,x下一个选六 会有六种可能能 4,2,1,6,x,x,x (此时三个x谁也不会
挡到谁为3!种可能=6)
也就是前面所述Q=2+6=8
若走4,2,3,x,x,x 也是Q种我就不再计算
接下来是4,2,6,x,x,x,x 的W种
後面的X谁也不会挡到谁(4!=24种)
接下来计算P种 一开始我先选4,2,x,x,x,x,x 会有P种可能
如果他接下来走1 会有Q种可能 走3也有Q种可能 走6有W种可能 (没别的其他路了...)
P=Q+Q+W=8+8+24=40
4之後选2或6都有P种可能ANSWER=P+P=80
因为我不会做图所以用写的就很复杂 有兴趣的人参考一下
可能要稍微画出树状结构才能知道我在说啥 如果有错请指正 谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.167.118.170
1F:推 dragoken:我了解了,谢谢大大解惑~ 04/03 13:52