论坛 › 柯哀联盟 › 柯哀趣味问题及《柯南外传》最近没空写，大家先去品味主论坛萌侦探柯南的活动吧！

澈～雲の向こう 发表于 2008-8-19 17:38:35

我由衷地想说句：楼主同学你太有才了。。。。。。
话说这里的工藤真的不是一般的bt

qq648173215 发表于 2008-8-19 21:42:14

顶了.....超级爱哀

黑夜彩虹 发表于 2008-8-19 21:48:18

想看答案所以发帖,大家54

銀翼の天使 发表于 2008-8-20 10:27:13

m1 (4)k 这个帖居然还是这么火爆啊= =

菲藏新崎 发表于 2008-8-21 10:27:13

有某些地方不是很懂啊`m1 (46)k

芙纱绘 发表于 2008-8-21 17:03:23

啊啊啊...好想看答案啊~!
先看看再说~

autumnjianli 发表于 2008-8-22 00:28:39

汗一个，看看答案m1 (40)k

云小天 发表于 2008-8-22 00:41:30

21题拖了好长时间....
23题解决,那么该24题了

可爱的哀,强大的LZm1 (45)k

mashaoranjay521 发表于 2008-8-22 00:52:10

回复就有答案？看看
LZ可不要欺骗莪们的心呐

DrogonSon 发表于 2008-8-24 09:42:54

我要看答案
阿 阿阿阿m1 (48)k

小星海Aptx 发表于 2008-8-24 15:44:17

第24题回答：

本题是相当经典的汉诺塔问题及其拓展。本题是找规律题，输出方案的话需要递归相关知识。
对于3个铜环的情况：共2^10-1=1023步，楼下是搬运过程~~~
对于4个铜环的情况比较麻烦：共49步。
有规律：
1:   0+2^0=1;
2:   1+2^1=3;
3:   3+2^1=5;
4:   5+2^2=9;
5:   9+2^2=13;
6:   13+2^2=17;
7:   17+2^3=25;
8:   25+2^3=33;
9:   33+2^3=41;
10:41+2^3=49;
11:49+2^4=65;

或者用动态规划解：令f表示i个汉诺塔4个柱的解，g表示3个的解，[ x ] 表示对 x 取下整，则
f [ i ] := 2 * f [ i - k ] + g [ k ]   ( k <= [ n / 2 ] + 1 )
预处理 g 数组，则时间复杂度 O ( N )

[ 本帖最后由 小星海Aptx 于 2008-8-24 15:49 编辑 ]

小星海Aptx 发表于 2008-8-24 15:46:00

当当当~~~3个柱子N=10的解法，令 a, b, c表示3个柱子最顶端的盘子。

a -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> bc -> ab -> cb -> ac -> ac -> ba -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> cb -> ac -> ac -> ba -> bc -> ab -> cb -> ac -> ab -> ca -> ba -> cb -> ca -> bc -> ac -> ba -> ba -> cb -> cb -> ac -> ab -> ca -> ba -> cb -> c

[ 本帖最后由 小星海Aptx 于 2008-8-24 19:00 编辑 ]

小星海Aptx 发表于 2008-8-24 15:46:57

下面弱弱地问一下...楼主是不是搞过OI...出的题怎么都这么熟...

突然发现偶滴注册时间比LZ还早5个月...

[ 本帖最后由 小星海Aptx 于 2008-8-24 15:51 编辑 ]

小星海Aptx 发表于 2008-8-24 16:21:59

更一般地，
设 f [ i ] [ j ] 表示有 i 个盘子 j 个柱子时至少需要多少次移动才可以将所有盘子从A盘移动到B盘.
状态转移方程： f[ i ][ j ] = f[ i – k ][ j ] + f[ k ][ j – 1 ] + f[ i – k ] [ j ]
这样可以在 O( NM ) 时间完美解决本问题。

孤影飞鹰 发表于 2008-8-24 19:48:40

汉诺塔!想起了文曲星游戏....
来晚了,291都答了就懒的在写了,等待25题ing

qazsasa1 发表于 2008-8-24 20:18:01

题目好丰富啊

qq394668152 发表于 2008-8-25 22:32:52

toukuim1 (50)k

IwfWcf 发表于 2008-8-25 22:42:09

汗......经典的汉诺塔问题......

ming1228 发表于 2008-8-26 13:20:11

25题
孙子算经的题吧，MS数都没变

三人同行七十稀
五树梅花廿一枝
七子团员正半月
除百零五便得知
程大位——《算法统宗》

大衍求一术
x=2*70+3*21+2*15=233≡23 (mod 105)

孙子定理,直和分解

逆转の推理 发表于 2008-8-26 13:52:00

为了看下去，顶下吧！m1 (43)k

查看完整版本: 柯哀趣味问题及《柯南外传》最近没空写，大家先去品味主论坛萌侦探柯南的活动吧！