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

qq648173215

杯户小学生

0 主题	0 好友	0 积分

帖子: 2
精华: 0
积分: 0
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 6 ℃
注册时间: 2008-8-19

发消息

282楼

发表于 2008-8-19 21:42:14 |只看该作者

顶了.....超级爱哀

柯南20周年纪念事务所专题站开放

黑夜彩虹

杯户小学生

0 主题	0 好友	0 积分

帖子: 1
精华: 0
积分: 0
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 0 ℃
注册时间: 2008-7-23

发消息

283楼

发表于 2008-8-19 21:48:18 |只看该作者

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

銀翼の天使

资源情报科成员
水区热心会员

89 主题	40 好友	1万积分

昵称: 天使
帖子: 16979
精华: 25
积分: 11502
威望: 315
ＲＰ: 27543
金钱: 69668 柯币
人气: 14676 ℃
注册时间: 2007-6-16
来自: 悲催的五楼

发消息

284楼

发表于 2008-8-20 10:27:13 |只看该作者

这个帖居然还是这么火爆啊= =

柯南20周年纪念事务所专题站开放

菲藏新崎

杯户小学生

0 主题	0 好友	0 积分

帖子: 4
精华: 0
积分: 0
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 0 ℃
注册时间: 2008-8-20

发消息

285楼

发表于 2008-8-21 10:27:13 |只看该作者

有某些地方不是很懂啊`

芙纱绘

杯户中学生

0 主题	0 好友	1 积分

帖子: 67
精华: 0
积分: 1
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 0 ℃
注册时间: 2008-8-6

发消息

286楼

发表于 2008-8-21 17:03:23 |只看该作者

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

柯南20周年纪念事务所专题站开放

autumnjianli

杯户小学生

0 主题	0 好友	0 积分

帖子: 1
精华: 0
积分: 0
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 2 ℃
注册时间: 2008-8-22

发消息

287楼

发表于 2008-8-22 00:28:39 |只看该作者

汗一个，看看答案

云小天

最后的银色子弹

主论坛荣誉版主
浪子回头的小天

30 主题	2 好友	2434 积分

帖子: 6564
精华: 31
积分: 2434
威望: 804
ＲＰ: 3910
金钱: 29329 柯币
人气: 3795 ℃
注册时间: 2007-8-3

发消息

288楼

发表于 2008-8-22 00:41:30 |只看该作者

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

可爱的哀,强大的LZ

mashaoranjay521

杯户小学生

0 主题	0 好友	0 积分

帖子: 2
精华: 0
积分: 0
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 0 ℃
注册时间: 2008-8-17

发消息

289楼

发表于 2008-8-22 00:52:10 |只看该作者

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

DrogonSon

杯户小学生

0 主题	0 好友	0 积分

帖子: 48
精华: 0
积分: 0
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 12 ℃
注册时间: 2008-8-20

发消息

290楼

发表于 2008-8-24 09:42:54 |只看该作者

我要看答案
阿阿阿阿

杯户小学生

0 主题	0 好友	0 积分

帖子: 37
精华: 0
积分: 0
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 42 ℃
注册时间: 2005-7-17

发消息

291楼

发表于 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 编辑 ]

ConanAi Forever~~
www.starea.cn
柯哀王道！

杯户小学生

0 主题	0 好友	0 积分

帖子: 37
精华: 0
积分: 0
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 42 ℃
注册时间: 2005-7-17

发消息

292楼

发表于 2008-8-24 15:46:00 |只看该作者

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

a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b c -> a b -> c b -> a c -> a c -> b a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c b -> a c -> a c -> b a -> b c -> a b -> c b -> a c -> a b -> c a -> b a -> c b -> c a -> b c -> a c -> b a -> b a -> c b -> c b -> a c -> a b -> c a -> b a -> c b -> c

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

ConanAi Forever~~
www.starea.cn
柯哀王道！

杯户小学生

0 主题	0 好友	0 积分

帖子: 37
精华: 0
积分: 0
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 42 ℃
注册时间: 2005-7-17

发消息

293楼

发表于 2008-8-24 15:46:57 |只看该作者

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

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

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

ConanAi Forever~~
www.starea.cn
柯哀王道！

杯户小学生

0 主题	0 好友	0 积分

帖子: 37
精华: 0
积分: 0
威望: 0
ＲＰ: 0
金钱: 0 柯币
人气: 42 ℃
注册时间: 2005-7-17

发消息

294楼

发表于 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 ) 时间完美解决本问题。

ConanAi Forever~~
www.starea.cn
柯哀王道！