師大學報：數理與科技類

Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/180

Browse

Subject: search.filters.subject.二元搜尋樹

Search Results

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    利用電腦探討中國古代益智遊戲
    (國立臺灣師範大學研究發展處, 1999-10-??) 魏仲良; 林順喜; Chun-Ling Wei and Shun-Shii Lin
    在本文中，我們嘗試設計演算法，利用電腦找出中國古代流傳下來的益智遊戲-「華容道」的最少步數，以驗證前人資料上所記載的最少步數是否正確。此遊戲中許多盤面之解答的移動步數超過100步，因此不能直接用暴力法搜尋，目前文獻上尚未見到電腦之解法，只有一些人為的解法有記錄，也有一些程式將這些人為的、不是最佳的解法作展示。因此我們構思如何解決此困難之問題。在此論文中，我們發展了一些技術，目標是求出完全的最佳解，並實際撰寫程式測試，要求在可容忍的時間內解出。程式的執行結果與先前得到的前人資料有所出入，有些與資料記載吻合，有的則較記錄為多，還有一些比資料上的少上三至五步之多。驗證了一下程式輸入到檔案的最佳解，發現程式所求得比資料記載還要少的結果應是正確的。至於程式求得較資料為多的部分，可能是前人的文獻資料有誤，因為資料上只記載著各盤面最少步數的解題記錄，並無參考的解法。