跳到主要內容

臺灣博碩士論文加值系統

(44.221.73.157) 您好!臺灣時間:2024/06/23 00:04
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王裕國
研究生(外文):Yu-Kuo Wang
論文名稱:平行移動「河內塔問題」之反覆式演算法分析
論文名稱(外文):Analysis on an Iterative algorithm of “The Tower of Hanoi problem” with Parallel Moves
指導教授:吳哲賢吳哲賢引用關係
指導教授(外文):Jer-Shya Wu
學位類別:碩士
校院名稱:中華大學
系所名稱:資訊工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:英文
論文頁數:74
中文關鍵詞:河內塔問題
外文關鍵詞:The tower of Hanoi ProblemCyclic movesParallel movesCyclic parallel moves
相關次數:
  • 被引用被引用:0
  • 點閱點閱:592
  • 評分評分:
  • 下載下載:30
  • 收藏至我的研究室書目清單書目收藏:0
「河內塔問題」是一個古老而且著名的數學問題,1883年由Lucas提出以後,距今已超過100年,一直受到廣泛討論與研究。1971年,Dijkstra首先提出「河內塔問題」之遞迴式演算法的最佳解。接著Atkinson在1981年提出一個新的變形問題:「循環式河內塔問題」,並提出遞迴式演算法的最佳解。1992年,Wu 和 Chen提出另外一種新的變型問題:「平行式河內塔問題」,與其遞迴式最佳解;隨後於1993年,又提出了一個複合式變形:「平行循環式河內塔問題」及其遞迴式演算法的最佳解。
本論文主要討論及分析「河內塔問題」其反覆式演算法之最佳解。在1980年,Buneman 提出了「河內塔問題」之反覆式演算法最佳解,接著於1983年Walsh對「循環式河內塔問題」也提出反覆式演算法的最佳解。我們在本論文中將針對 「平行式河內塔問題」,設計出一種簡單且有效率的反覆式演算法,並證明其搬動次數為最佳解。

“The Tower of Hanoi problem” is an ancient and famous mathematical problem. It has over 100 years since Lucas presented in 1883. In 1971, Dijkstra first presented the optimal solution. And then, Atkinson in 1981 proposed a variant, known as “The cyclic Tower of Hanoi problem” and its recursive optimal solution. In 1992, Wu and Chen propose another new variant: “The parallel Tower of Hanoi problem” and its recursive solution; continuing in 1993, proposed another compose variant: “The cyclic parallel Tower of Hanoi problem” and its recursive solution.
In this thesis we are aimed at this problem to discuss the iterative optimal solutions. In 1980, Buneman presented the iterative optimal solutions for the problem. And then, Walsh presented the iterative optimal solutions for “The cyclic Tower of Hanoi problem” in 1983. We will design a simple and effective iterative algorithm to implement “The parallel Tower of Hanoi problem”, and prove its moving is an optimal solution.

中 文 摘 要 I
ENGLISH ABSTRACT II
ACKNOWLEDGEMENTS III
CONTENTS IV
LIST OF FIGURES VII
CHAPTER 1 INTRODUCTION 1
1.1 Ancient Legend 1
1.2 History 3
1.3 Outline of the Paper 5
CHAPTER 2 RECURSIVE ALGORITHM ON "THE TOWER OF HANOI PROBLEM" 6
2.1 The Problem and Its Origin 6
2.2 Hanoi Graph 14
CHAPTER 3 RECURSIVE ALGORITHM OF THREE VARIANTS 20
3.1 Cyclic Moves of “The Tower of Hanoi problem” 20
3.2 Parallel Moves of “The Tower of Hanoi Problem” 23
3.3 Cyclic Parallel Moves of “The Tower of Hanoi Problem” 29
CHAPTER 4 ITERATIVE ALGORITHM ON "THE TOWER OF HANOI PROBLEM" 39
4.1 Introduction 39
4.2 Deriving an Iterative Algorithm For “The Tower of Hanoi problem” 40
4.3 Program and Result 44
CHAPTER 5 ITERATIVE ALGORITHM OF CYCLIC MOVES 50
5.1 Introduction 50
5.2 Iterative Algorithm of Cyclic Moves 51
CHAPTER 6 ITERATIVE ALGORITHM OF PARALLEL MOVES 63
6.1 Introduction 63
6.2 Iterative Algorithm of Parallel Moves 65
CHAPTER 7 CONCLUSION 72
7.1 Result of Our Research 72
7.2 Studying Topic in the Future 74
REFERENCE 75

[1] J. P. Allouche, “Note on the Cyclic Towers of Hanoi”, TCS 123 (1), pp.3-7, 1994.
[2] M. D. Atkinson, “The cyclic towers of Hanoi”, Information Processing Letters 13, pp.118-119, 1981.
[3] P. Buneman & L. Levy, “The towers of Hanoi problem”, Information Processing Letters 10, pp.243-244, 1980.
[4] W. C. Chang & G. J. Chang, “Study on Tower of Hanoi”, Master Thesis, Submitted to Department of Applied Mathematics, National Chiao Tung University Engineering, 1998.
[5] F. B. Chedidand Toshiya Mogi, “A simple iterative algorithm for The Tower of Hanoi Problem”, IEEE Trans. Ed. 39, no. 2, pp. 274-275, 1996.
[6] E. W. Dijkstra, “A short introduction to the art of programming”, EWD 316, 1971.
[7] B. Eggers, “The towers of Hanoi: Yet another nonrecursive solution”, SIG-PLAN Notices 20, no. 9 (September), pp.32-42, 1985.
[8] M. C. Er, “A general algorithm for finding a shortest path between two n-configurations”, Inform. Sci. 42, pp.137-141, 1987.
[9] M. C. Er, “A generalization of the cyclic towers of Hanoi: An iterative solution”, Internat. J. Comput. Math. 15, pp.129-140, 1984.
[10] M. C. Er, “A loop less approach for constructing a fastest algorithm for the Towers of Hanoi problem”, Internat. J. Comput. Math. 20, pp.49-54, 1986.
[11] M. C. Er, “A loop less and optimal algorithm for the cyclic towers of Hanoi problem”, Inform. Sci. 42, pp.283-287, 1987.
[12] M. C. Er, “A minimal space algorithm for solving the towers of Hanoi problem”, J. Inform. Optim. Sci 9, pp.183-191, 1988.
[13] M. C. Er, “A representation approach to the tower of Hanoi problem”, Comput. J. 25, no. 4, pp.442-447, 1982.
[14] M. C. Er, “An algorithmic solution to the multi-tower of Hanoi problem”, J. Inform. Optim. Sci. 8, no. 1, pp.91-100, 1987.
[15] M. C. Er, “An analysis of the Generalized Tower of Hanoi Problem”, Bit 23 (4), pp. 429-435, 1983.
[16] M. C. Er, “An iterative algorithm for the cycle towers of Hanoi problem”, Internat. J. Comput. Inform. Sci. 13, no. 2, pp.123-129, 1984.
[17] M. C. Er, “An iterative solution to the Generalized Tower of Hanoi Problem”, Bit 23 (4), pp.295-302, 1983.
[18] M. C. Er, “An optimal algorithm for Revel’s puzzle”, Inform. Sci 45, pp.39-49, 1988.
[19] M. C. Er, “Counter examples to adjudicating a tower of Hanoi contest”, Internat. J. Comput. Math. 21, pp.123-131, 1987.
[20] M. C. Er, “Performance evaluations of recursive and iterative algorithms for the towers of Hanoi problem”, Computing 37, PP.93-102, 1986.
[21] M. C. Er, “The colour towers of Hanoi-An iterative solution”, J. Inform. Optim Sci. 5, no. 2, pp.95-104, 1984.
[22] M. C. Er, “The complexity of the generalized cyclic towers of Hanoi problem”, J. Algorithms 6, pp.351-358, 1985.
[23] M. C. Er, “The Cyclic Tower of Hanoi: A representation Approach”, The Computer Journal 27 (2), pp.171-175, 1984.
[24] M. C. Er, “The cyclic towers of Hanoi and pseudo ternary code”, J. Inform. Optim. Sci. 7, no. 3, pp.271-277, 1986.
[25] M. C. Er, “The Generalized colour Tower of Hanoi Problem: An iterative algorithm”, The Computer Journal 27 (3), pp.278-282, 1984.
[26] M. C. Er, “The generalized towers of Hanoi problem”, J. Inform. Optim. Sci 5, no. 1, pp.89-94, 1984.
[27] M. C. Er, “The tower of Hanoi problem-a further reply”, Comput. J. 28, no.5, pp.543-544, 1985.
[28] M. C. Er, “The towers of Hanoi and binary numerals”, J. Inform. Optim. Sci. 6, no. 2, pp.147-152, 1985.
[29] M. C. Er, “Towers of Hanoi with black and white disks”, J. Inform. Optim. Sci. 6, no. 1, pp.87-94, 1985.
[30] D. Gault & M. Clint: “A Fast Algorithm for the Towers of Hanoi”, The Computer Journal 30 (4), pp.376-378, 1987.
[31] T. Gedeon, The “Cyclic Tower of Hanoi: An Iterative Solution Produced by Transformation”, The Computer Journal 39 (4), pp.353-356, 1996.
[32] T. D. Gedeon, “The Reve`s puzzle:An iterative solution produced by transformation”, The Computer Journal 35 (2), pp.186-187, 1992.
[33] P. J. Hays, “A note on The Tower of Hanoi problem”, Computer Journal 20, pp. 282-285, 1977.
[34] A. M. Hinz, “An iterative algorithm for the Tower of Hanoi with four pegs”, Computing 42, pp.133-140, 1989.
[35] X. —M Lu & T. S. Dillon, “Nonrecursive solution to parallel multipeg Towers of Hanoi: A decomposition approach”, Math. Comput. Modelling 24, no. 3, pp.29-35, 1996.
[36] W. Lunnon, “The Reve’s Puzzle”, Comput. J. 29, p.478, 1986.
[37] A. A. K. Majumdar, “A note on the iterative algorithm for the Reve’s puzzle”, The Computer Journal. 37(5)pp.463-464, 1994.
[38] A. A. K. Majumdar & M. Kaykobad, “An iterative algorithm for the 5-peg tower of Hanoi problem”, J. Bangladesh Acad. Sci. 20, no. 2, pp.119-128, 1996.
[39] A. A. K. Majumdar, “A note on the generalized multi-peg tower of Hanoi problem”, Prpc. Pakistan Acad. Sci. 33, no. 1-2, pp.129-130, 1996.
[40] A. A. K. Majumdar, “A note on the iterative algorithm for the four peg tower of Hanoi problem”, Bangladesh Acad. Sci. 18, no2, pp.241-250, 1994
[41] A. A. K. Majumdar, “Frame's conjecture and the tower of Hanoi problem with four pegs”, Indian J. Math. 36, no. 3, pp. 215-227, 1994
[42] A. A. K. Majumdar, “Generalized multi-peg tower of Hanoi problem”, J. Austral. Math. Soc. Ser. B 38, Q.O. 2, pp 201-208, 1996.
[43] A. A. K. Majumdar, “The divide-and-conquer approach to the generalized p-peg tower of Hanoi problem”, Optimization 34, pp.373-378, 1995.
[44] A. A. K. Majumdar, A note on the cyclic towers of Hanoi, Proc. Pakistan A ad. Sci. 33, no. 1-2, pp.131-132, 1996.
[45] A. A. K. Majumdar, “The generalized four-peg tower of Hanoi problem”, Optimization, vol 29, pp.349-360, 1994.
[46] A. A. K. Majumdar, “The generalized p-peg tower of Hanoi problem”, Optimization, vol 32, pp 175-183, 1995.
[47] S. Margarita, “The towers of Hanoi: a new approach”, AI Expert 8,no. 3 (March), pp.22-27, 1993.
[48] S. Minsker, “The Towers of Antwerpen problem”, Information Processing Letters 38, pp.107-111, 1991.
[49] R. Newman-Wolfe, “Observations on multipeg Tower of Hanoi”, TR187, University of Rochester, 1986.
[50] A. Pettorossi, “Tower of Hanoi Problem: Deriving Iterative Solutions by Program Transformations”, Bit 25, pp.327-334, 1985.
[51] J. S. Rohl, “Tower of Hanoi: The Derivation of Some Iterative Versions”, The Computer Journal 30 (1), pp.70-76, 1987.
[52] U. k. Sakar, “On the design of a constructive algorithm to solve the multi-peg towers of Hanoi problem”, Theoretical Computer Science 237, pp.407-421, 2000.
[53] B. M. Stewart, “Solution to 3918”, Amer. Math. Monthly 48, pp.217-219, 1941.
[54] P. k. Stockmeyer, “The Tower of Hanoi: A History Survey and Bibliography”, Department of Computer Science College of William and Mary, 2001.
[55] T. R. Walsh, “Iteration strikes back — at the cyclic towers of Hanoi”, Information Processing Letters 16, pp.91-93, 1983.
[56] T. R. Walsh, “The towers of Hanoi revisited: moving the rings by counting the moves”, Information Processing Letters 15, pp.64-67, 1982.
[57] J.-S. Wu & R. -J. Chen, “The towers of Hanoi problem with parallel moves”, Information Processing Letters 44, pp.241-243, 1992.
[58] J.-S. Wu & R. -J. Chen, “The towers of Hanoi problem with cyclic parallel moves”, Information Processing Letters 46, pp.1-6, 1993.
[59] R .L. Wu & R. J. Chen, “Parallel Tower of Hanoi”, Master Thesis, Submitted to Department of Computer Science and Information Engineering, National Chiao Tung University, 1999.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top