iT邦幫忙

1

如何實現每秒移動一步的河內塔遊戲

  • 分享至 

  • xImage

如題,雖然有爬文參考其他前輩們的寫法,但我無法完全理解,不論是遞迴寫法還是迴圈寫法,我自己也不知道卡在哪裡,更無從下手加上timeout,請前輩們大發慈悲指點我一下,感激不盡

遞迴寫法

hanoi(n, source, buffer, target) {
  if (n === 1) {
    const disk = source.data.pop();
    target.data.push(disk);
    console.log(`Move disk ${disk} from ${source.name} to ${target.name}`);
    return;
  }

  this.hanoi(n - 1, source, target, buffer);

  const disk = source.data.pop();
  target.data.push(disk);
  console.log(`Move disk ${disk} from ${source.name} to ${target.name}`);

  this.hanoi(n - 1, buffer, source, target);
}

迴圈寫法

hanoi(n, source, buffer, target) {
  const stacks = [{ from: source, to: target, buf: buffer, n }];

  while (stacks.length > 0) {
    const { from, to, buf, n } = stacks.pop();

    if (n === 1) {
      const disk = from.data.pop();
      to.data.push(disk);
      console.log(`Move disk ${disk} from ${from.name} to ${to.name}`);
    } else {
      stacks.push({ from: buf, to, buf: from, n: n - 1 });
      stacks.push({ from, to, buf, n: 1 });
      stacks.push({ from, to: buf, buf: to, n: n - 1 });
    }
  }
}
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中
0
EeroLai
iT邦新手 5 級 ‧ 2023-09-01 17:06:45

setTimeout() 與 setInterval()這兩個去理解一下, 然後思考一下甚麼時候會印出需要把它包裝起來, 大概就知道能怎麼做了

1
clouddaaiyoga
iT邦新手 5 級 ‧ 2023-09-01 19:36:02

先跟大神說個抱歉!河內塔的部分因為弱弱的我資料結構忘光光所以幫不了您,但弱弱的我最近在自修網站程式設計剛好有學到 setTimout() 和 setInterval(),所以程式碼貼給您,可以用開頭的大寫 Flag 控制,兩個都可以跑

var SET_TIMEOUT = 0;
var SET_INTERVAL = 1;

if (SET_TIMEOUT && (!SET_INTERVAL)) {
    var flag = 0;
    var int = "";

    start ();
    setTimeout (function () {
        alert ("Complete");
        window.clearInterval (int);
    }, 3000)

    function start () {
        if (!flag) {
            S ("myDiv").color = "red";
            flag = 1;
        } else {
            S ("myDiv").color = "green";
            flag = 0;
        }
        int = setTimeout ("start ()", 500);
    }
} else if ((!SET_TIMEOUT) && SET_INTERVAL) {
    setInterval ("start ()", 1000);

    function start () {
        if (S ("myDiv").color != "red") 
            S ("myDiv").color = "red";
        else
            S ("myDiv").color = "blue";
    }
} else {
    O ("myDiv").textContent = "Nothing";
}

弱弱的我知道看程式碼很煩,但這套 code 真的不難,O 和 S 的部分是我看歐萊禮的書抄出來的大神您先不要管它,基本上這套 code 的功能只有變換顏色而已。SET_TIMEOUT 會宣告一個 3 秒結束的計時器,然後然後每隔 0.5 秒換顏色;而 SET_INTERVAL 功能是每隔 1 秒不斷換顏色。

1
小哈片刻
iT邦研究生 4 級 ‧ 2023-09-01 22:46:05

教你一個絕招
首先寫一個等待的全域函式

// 等待一段時間的非同步函式(參數:毫秒)
function wait(duration) {
    return new Promise(resolve => {
        setTimeout(resolve, duration);
    });
}

然後更新你的函式

// 要改宣告成非同步函式
async hanoi(n, source, buffer, target) {
    ...
    while (stacks.length > 0) {
        ...
        // 加上這行,等一秒
        await wait(1000);
    }
}

乾淨又簡單~
總之,就是在你想要讓過程暫停一下的地方,加上await wait(1000)就可以了。

0
淺水員
iT邦大師 6 級 ‧ 2023-09-03 15:24:17

當練習,把遞迴版的 hanoi 改成一個 class
每次呼叫 next 方法就可以輸出一個步驟的結果

使用範例如下
(這範例用 click 觸發,當然也可以改用計時器觸發)

<!-- 下一步的按鈕 -->
<button onclick="getNext()">下一步</button>

<!-- 輸出結果 -->
<div id="result"></div>

<!-- 引入 class Hanoi -->
<script src="hanoi.js"></script>

<!-- 使用範例 -->
<script>
    const hanoiGame = new Hanoi(4); // 4層
    function getNext() {
        let r = hanoiGame.next();
        if(r !== null) {
            let p = document.createElement('p');
            p.textContent = r;
            document.querySelector('#result').appendChild(p);
        } else {
            alert('已經完成');
        }
    }
</script>

hanoi.js 的內容

/**
 * 相當於原本的遞迴版 hanoi 函式實體
 */
class HanoiFunction {
    constructor(n, source, buffer, target) {
        // 記錄內部變數的狀態
        this.n = n;
        this.source = source;
        this.buffer = buffer;
        this.target = target;
        // 紀錄執行到哪個位置
        this.executeIndex = 0;
    }

    /**
     * 執行此函數
     * @returns {string|HanoiFunction|null} string:河內塔移動步驟的敘述
     *                                      HanoiFunction:遞迴呼叫
     *                                      null: 此函數已經執行完畢
     */
    execute() {
        switch (this.executeIndex) {
            case 0:
                if (this.n === 1) {
                    const disk = this.source.data.pop();
                    this.target.data.push(disk);
                    this.executeIndex = -1;
                    return `Move disk ${disk} from ${this.source.name} to ${this.target.name}`;
                }
            case 1:
                this.executeIndex = 2;
                return new HanoiFunction(this.n - 1, this.source, this.target, this.buffer);
            case 2:
                const disk = this.source.data.pop();
                this.target.data.push(disk);
                this.executeIndex = 3;
                return `Move disk ${disk} from ${this.source.name} to ${this.target.name}`;
            case 3:
                this.executeIndex = 4;
                return new HanoiFunction(this.n - 1, this.buffer, this.source, this.target);
            default:
                return null; // 表示程式已經結束,無法再執行
        }
    }
}

/**
 * HanoiFunction 呼叫管理器
 * 這邊處理遞迴函式的堆疊以及回傳值
 */
class Hanoi {
    constructor(n) {
        this.source = { name: 'A', data: Array.from({ length: n }, (x, i) => n - i) };
        this.buffer = { name: 'B', data: [] };
        this.target = { name: 'C', data: [] };
        this.stack = [new HanoiFunction(n, this.source, this.buffer, this.target)];
    }

    next() {
        while (this.stack.length > 0) {
            const currentFunc = this.stack[this.stack.length - 1];
            const returnValue = currentFunc.execute();
            if(typeof returnValue === 'string') {
                return returnValue;
            } else if(returnValue instanceof HanoiFunction) {
                this.stack.push(returnValue);
            } else if(returnValue === null) {
                this.stack.pop();
            }
        }
        return null;
    }
}

我要發表回答

立即登入回答