Poopćeni problem Hanojskih tornjeva

završni rad

• Naslov (engleski): Tower of Hanoi and its Generalizations
• Autor: Krešimir Dodig
• Mentor: Tomislav Burić (mentor)
• Član povjerenstva: Tomislav Burić (predsjednik povjerenstva)
• Član povjerenstva: Anamari Nakić (član povjerenstva)
• Član povjerenstva: Ana Anušić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2017-07-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: Hanojski tornjevi; Édouard Lucas; Rekurzivna relacija; Rekurzija; Java; Neusmjereni graf; Frame-Stewartov algoritam; BFS(Breadth-first search)
• Ključne riječi (engleski): Hanoi towers; Édouard Lucas; recurrence relation; Recursion; Java; Undirected graph; Frame-Stewart algorithm; BFS(Breadth-first search)
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:387597
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-03-13 19:57:02