My experience in Assignment 1(About Recursion)

Assignment 1 is a typical Hanoi tower problem. Luckily, I learned some thing about it by myself. So I can easily write the recursion. However, when I was writing the recursion part, I found myself in trouble. The problem is that there is really something trouble me in the handout. In the handout, the recursion description is as follows:

1. Move n -i cheese rounds to an intermediate stool using all four stools.

2. Move i cheese rounds from the origin stool to the destination stool, using the (now) only three

available stools and her TOAH method.

3. Move the n-i smallest cheese rounds from the intermediate stool to the destination stool, using

all four stools

And my first reaction is WTF?!!?!

See the step3? "Move the n-i smallest cheese rounds", I thought it means move the n-i smallest cheese round, not plural. And that's why I got into trouble.

I really hope, that the instruction can be more specific. It can be just say the same stuff as the first statement.

Ok, now let's talk about the recursion. I actually google it. Ok, never mind, it's not cheating. I just want to know the recursion because of the trouble I got into from above. And in my words, I will describe the recursion as follows:

 1. we cut the whole bunch of cheese into two part. 

Part1(Down): k cheese. k is a integer between 1 and n(of course, n is the number of cheese!)

Part2(Up): n-k cheese. 

2. Ok then we move these n-k cheese to an intermediate stool.

3.Then we use the three cheese method, and move the  k cheese to the destination stool.

4 Then we move the n-k cheese from intermediate stool to the destination stool.

However, how to choose k?

I first think it should be related to n. And I try k = n//2

Which is not the best answer, but it is actually really close.

How to know the best answer?

You know the k should vary due to the n. But every n has a best answer.

Then I try to using the recursion function teacher give us to calculate the best answer. I find it really painful.

To calculate M(8) for example, we have to calculate M(7)M(6)M(5)M(4)M(3)...M(1).
And we choose the best answer for k=1-7 about M(8)
And we choose that k for this partition.
These are the best step for every n<10.
[[1, 1], [3, 1], [5, 2], [9, 2], [13, 2], [17, 3], [25, 3], [33, 3], [41, 3], [49, 4]]
The first element in that list inside the list is the step, second element is k.

I hope I can get good mark in A1...