※ 引述《DickG (龍龍)》之銘言：
: 這是一個老掉牙的問題
: 記得上學期在寫 acm on-line problems 有個 Hanoi Tower
: 可它的題意有了改變
: 輸入 num, step
: num -> disk number
: step -> move step
: 求出在 move step 後的 Tower distribution
: x1 x2 x3
: x(n) = disk num in tower n
: ex.
: num = 3
: step = 3
: output:
: 0 1 2
: 你覺得有什麼方法能很快求到解呢?
: (step's type is long)
: Dick Guan
//know fact:moving n disks from a tower to another requires 2^n-1 moves.
void movedisk(int &tfrom, int &tto, int &ttemp, int tmove, int stepleft)
{
int halfmove = 2 ^ (tmove - 1);
if (halfmove <= stepleft)
{
tfrom -= tmove;
tto++;
tmove += tmove - 1;
if (halfmove < stepleft)
movedisk(ttemp, tto, tmove, tmove - 1, stepleft - halfmove);
} else
movedisk(tfrom, ttemp, tto, tmove - 1, stepleft);
}
int initial(int disknum, int stepnum)
{
if (2 ^ disknum >= stepnum)
return ERROR_TOO_MANY_MOVES;
int x1 = disknum, x2 = 0, x3 = 0;
movedisk(x1, x3, x2, disknum, stepnum);
printresult(x1, x2, x3);
}
--
這樣是Ｏ(log2(stepnum))或Ｏ(disknum)吧！
應該可以不用遞迴的，算了。
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: ccsun4.ee.ntu.e
--
嘖！大數……
反正只是隨手寫的。