1. You are going to write the h4 function, which will calculate the minimum step

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

• Browse (All)
• Browse 1
• Subjects

---