荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: Minatl ([3;38H[]到本站一游。), 信区: Program
标 题: Re: 编程？！
发信站: BBS 荔园晨风站 (Sun Mar 19 23:14:30 2000), 转信
实际上还是回溯好！！！特别是n很大的时候
因为这个问题有很强的局部性
边回溯边判断
(当然有更好的，不过要付出很大的空间代价，特别是n很大时）
r【 在 tang (独孤九剑〖玄铁重剑〗) 的大作中提到: 】
: 其实这种方法等价于深度为N的二元树的深度遍历！
: 需要遍历所有的2^N+1个结点！
: 用二元树来分析的话，很容易就能得到一些剪枝的方法！
: 象编号以111打头的子树的所有结点都不用搜索了，这样可以
: 大幅减少搜索结点数！
: 【 在 onedot (小点) 的大作中提到: 】
: : 打个比方，以前有个编程小题目，说
: : 往一些坑里埋废料
: : 有N个坑，如果相邻的连续3个坑里面都埋就会引发爆炸
: : 要求编程求出N坑可以有多少种不爆炸的埋法！
: : 也许大多数人第一次一想就用数学的排列组合求，然后编程实现
: : 而往往忽略了计算机的强于计算的能力，而且组合公式也由于不
: : 少人考虑欠周全，写的是不正确的
: : 而有一种解法就是把N个坑看作N位的2进制，如果这个坑里有则
: : 看作这位为1，否则为0，这样每种埋法一一对应一个2进制的数
: : 如：10011（第1、4、5个坑埋了废料）。N个坑共用2的N次种埋法
: : 而爆炸就是那种有连续3位为1，这个用计算机处理特别方便。
: : 所以要求等价于求从1到2的N次方这么多2进制数里，有多少种连续
: : 3位为1，这个很方便，每次除2求模，是1记数一次，对商继续/2
: : 求模，是1再记数,是0，则记数清为0，这样如果一个数这样处理
: : 记数达到3表示是一种爆炸情况。如7=0111，就是一种。
: : 这种处理放在1。。2的N次的循环里，再设个计数器，自然就可以
: : 得解，而且不会出现公式错误
--
※ 修改:·Minatl 於 Mar 19 23:17:53 修改本文·[FROM: 192.168.0.90]
※ 来源:·BBS 荔园晨风站 bbs.szu.edu.cn·[FROM: 192.168.0.90]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店