1. You are going to write the h4 function, which will calculate the minimum step
ID: 3550993 • Letter: 1
Question
1. You are going to write the h4 function, which will
calculate the minimum steps to finish the tower of Hanoi using 4 pile.
First pick a value of k and move the k smallest disks to one of the temporary pile. Now
we have n - k disks left and we only have 3 piles available (since any of the remaining n - k disks
are larger than the first k disks and cannot be put on top of them). We can solve this by using the
regular algorithm of tower of Hanoi (using 3 piles). We need to look at all possible values of k
and pick the one that produces the smallest number.
The h4 function, in pseudo code, will look something like this:
Function H4 (n):
if n < = 0 then return 0
else
for k from 0 to n - 1
calculate the value of 2 * H4 (k) + H3 (n - k)
create a list containing these n values
return the minimum value of the list.
Hint: you can use list comprehension to create the list and use the minimum function to find the
minimum value. We have discussed list comprehension in class.
Given:
fib :: Int -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
where fib 0 = 0
fib 1 = 1
fib n = memoized_fib (n-2) + memoized_fib (n-1)
Explanation / Answer
The Towers of Hanoi {- The recursive strategy is as follows: Recipe to move one pile of stones from pillar "A" to pillar "B": 1. If there is no stone, there is nothing to move 2. Otherwise, call the third pillar "C" 3. Recursively move all but the biggest stone from "A" to "C" 4. Move the biggest stone to "B" 5. Recursively move all stones from "C" to "B" 6. Done! -} -- hanoi n computes the number of steps to move one pile with n stones hanoi :: Integer -> Integer hanoi 0 = 0 hanoi n | n > 0 = m + 1 + m where m = hanoi (n-1) {- Recipe to move one pile of stones from pillar "A" to pillar "B", using 4 pillars in total: 1. If there is no stone, there is nothing to move 2. Otherwise, call the third and fourth pillar "C" and "D" 3. Recursively move k stones from "A" to "C", for some 0 0 = m + hanoi (n-k) + m where m = hanoi4 k -- what should k be? -} -- hanoi4 n computes the number of steps to move n stones using 4 pillars, -- using strategy above where k=2 hanoi4 :: Integer -> Integer hanoi4 0 = 0 hanoi4 1 = 1 hanoi4 n | n > 0 = m + 3 + m where m = hanoi4 (n-2) --Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.