Poopćeni problem Hanojskih tornjeva

undergraduate thesis

• Title (english): Tower of Hanoi and its Generalizations
• Author: Krešimir Dodig
• Mentor: Tomislav Burić (mentor)
• Committee member: Tomislav Burić (predsjednik povjerenstva)
• Committee member: Anamari Nakić (član povjerenstva)
• Committee member: Ana Anušić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2017-07-10, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovom radu pokazali smo da se problem Hanojskih tornjeva s 3 klina i n diskova može riješiti na više načina, među kojima valja posebno istaknuti rekurzivno rješenje. Svaki od navedenih načina problem rješava optimalno. Nadalje, razmotrili smo poopćenje problema na više od 3 klina. Za slučaj s 4 klina, Frame-Stewartov algoritam daje optimalno rješenje, dok je za slučajeve s više od 4 klina optimalnost algoritma i dalje otvoreni problem. Međutim, treba napomenuti da je 2016. godine Demontis ponudio navodni dokaz optimalnosti Frame-Stewartovog algoritma. Njegov rad još nije potvrđen.

Abstract (english)

In this paper we show that the Towers of Hanoi problem with 3 pegs and n disks can be solved in several ways, using different methods, among which should be specifically mentioned recursive solution. Each of these methods solves the problem optimally. Furthermore, we have generalized the problem by allowing more than 3 pegs. In the 4-peg scenario, Frame-Stewart algorithm gives the optimal solution, while for cases with more than four pegs optimality of this algorithm is still an open problem. However, it should be noted that in 2016. Demontis offered alleged evidence of the algorithm's optimality. His work has not yet been confirmed.

• Keywords: Hanojski tornjevi; Édouard Lucas; Rekurzivna relacija; Rekurzija; Java; Neusmjereni graf; Frame-Stewartov algoritam; BFS(Breadth-first search)
• Keywords (english): Hanoi towers; Édouard Lucas; recurrence relation; Recursion; Java; Undirected graph; Frame-Stewart algorithm; BFS(Breadth-first search)
• Language: croatian
• URN:NBN: urn:nbn:hr:168:387597
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-13 19:57:02