这是一个创建于 4384 天前的主题，其中的信息可能已经有所发展或是发生改变。
大家好。非常冒昧到这里来问一道算法题。
我有一个棋盘，10×10大小的。现在我要依次在格子内放棋子，棋子有编号的，1 到 100。
要求是：
1. 编号为1的棋子只能放在最左上角的格子里。接下里一次放相应编号的棋子。
2. 接下来的棋子可以水平相隔两个格子或者竖直相隔两个格子放入。或者……
3. 接下来的棋子可以在对角线的线路上放，和上次的棋子相隔一个格子。
4. 目的是100个棋子都能放进棋盘。
问题是按照这个规则能有多少种结果。用程序怎么实现呢？
我自己简化过问题到5×5，包括可以重复的组合一共有500+种结果。但是同样的程序跑6×6已经一个多小时出不来结果了。我想知道在算法上应该选择什么样的策略。谢谢。
我有一个棋盘，10×10大小的。现在我要依次在格子内放棋子，棋子有编号的，1 到 100。
要求是：
1. 编号为1的棋子只能放在最左上角的格子里。接下里一次放相应编号的棋子。
2. 接下来的棋子可以水平相隔两个格子或者竖直相隔两个格子放入。或者……
3. 接下来的棋子可以在对角线的线路上放，和上次的棋子相隔一个格子。
4. 目的是100个棋子都能放进棋盘。
问题是按照这个规则能有多少种结果。用程序怎么实现呢？
我自己简化过问题到5×5，包括可以重复的组合一共有500+种结果。但是同样的程序跑6×6已经一个多小时出不来结果了。我想知道在算法上应该选择什么样的策略。谢谢。
 |
1
laskuma 2012-11-22 00:05:40 +08:00
要求有点没看懂 2 3条件是任何时刻选一个满足？还是说只能交替满足？另外3有点没看懂
|
 |
3
fanzeyi 2012-11-22 02:18:27 +08:00
感觉可能是动态规划，目测不在能力范围内
大概想了下状态 f[i][j] 表示 (i,j) 格子（左上为 (0,0)）的结果.. === 以上删除 === 尝试写动态转移方程的时候发现，还可以竖直放，也就是说第 (i,j) 格子可以从 (i+1,j)个格子放过来…… 所以不满足动态规划的无后效性…… 或者是比较高级的动态规划…… 不会呢 （其他同学继续想吧…… ） |
 |
4
qiukun 2012-11-22 08:50:48 +08:00
将起点和终点连接起来。就是寻找汉密尔顿回路的问题。http://zh.wikipedia.org/zh/%E5%93%88%E5%AF%86%E9%A1%BF%E5%9B%BE
baidu之下，木有求总数的算法（实际上只能构造出特定的回路的样子）。 |
Select Language