fb一题求解答 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

fb一题求解答

fb一题求解答# JobHunting - 待字闺中

j*b2012-03-21 07:03

1 楼

不是面试题，只是hr发的热身题，限时45分钟，我是想不出来了，求高手解答
汗诺塔问题的变形。现在有k个塔，3<=k<=5, n个碟子，1<=n<=8
每个碟子初始位置和目标位置作为参数给出
问要如何挪动最少的步数把每个碟子归位。
还有一个重要提示是假设最多只需要挪动6步就可以达到目的

a*22012-03-21 07:03

2 楼

hr也这么变态

【在 j****b 的大作中提到】

: 不是面试题，只是hr发的热身题，限时45分钟，我是想不出来了，求高手解答
: 汗诺塔问题的变形。现在有k个塔，3<=k<=5, n个碟子，1<=n<=8
: 每个碟子初始位置和目标位置作为参数给出
: 问要如何挪动最少的步数把每个碟子归位。
: 还有一个重要提示是假设最多只需要挪动6步就可以达到目的

b*t2012-03-21 07:03

3 楼

这个不是 interviewstreet上的某个练习题么
BFS啊

【在 a****2 的大作中提到】

: hr也这么变态

s*n2012-03-21 07:03

4 楼

无语了，幸亏没投F，自取其辱

t*e2012-03-21 07:03

5 楼

Brute force: since there are just max 6 steps, at each steps, try all
possible valid moves, max 10 valid moves at each step because only one
direction is valid between 2 towers. Hard part is how to optimize.

a*22012-03-21 07:03

6 楼

Why there are max 6 steps? I don't understand the question.

【在 t********e 的大作中提到】

: Brute force: since there are just max 6 steps, at each steps, try all
: possible valid moves, max 10 valid moves at each step because only one
: direction is valid between 2 towers. Hard part is how to optimize.

j*b2012-03-21 07:03

7 楼

说最多6步可能是因为它测试用的输入是特殊制定的。。。不是啥input都能6步搞定。
。。
有道理啊 brute force，反正只有6步，学习了！