Unofficial C Solution to Problem 3.4 in Cracking the Coding Interview (5th Edition)

13 Oct

Before solving this problem, we introduce a simple library of stack with integers. Many following questions need an integer stack. Not to reinvent the wheel in our following solutions, we make a standalone integer stack library. Actually, we should do it at the very beginning of this chapter. This library includes the following functions: init, push, pop, peek, shrink, extend, isEmpty, isFull, and clean. We much call init function before using it and clean function at the end. The header file is as following:

 The implementation is:

This is a very classic problem: the Tower of Hanoi. In the book, the solution is recursive. And we need stacks to mimic the pegs and store the plate information in each peg. The recursive is short and easy to understand. But it requires more space for recording function callings.  The following is the recursive solution for Tower of Hanoi in C:

A non-recursive method seems more complex, but is more efficient. Wikipedia lists many iterative methods. And we implement one, mentioned here. Firstly, we label the plates from smallest to biggest with 1, 2, and 3 and so on. Therefore, the #1 plate means the smallest one.  If we count the steps of moving from 1, we could get the relationship as:

$$! step=ptimes 2^{k}+2^{k-1}=left( 2p+1right) times 2^{k-1} $$

where p is the number of previous moving for this plate, and k is the plate ID/label. For example, in the fourth step, with the equation, we could get p being 0, and k being 3. Therefore, we could know, we are moving the plate #3. And we do not moved it before (the number of previous moving is zero). In addition, we lable the first peg with 0, the second 1, and the third 2. We could estimate the current position as:

$$! current-position={_{p%3,hspace{16mm} if hspace{8mm} left( N+kright) %2=1}^{left( 2times pright) %3,hspace{16mm} if hspace{8mm} left( N+kright) %2=0} $$

where the N means the total number of plates in this game. Similarly, the next postion is:

$$! next-position={_{left( p + 1right) %3,hspace{16mm} if hspace{8mm} left( N+kright) %2=1}^{left( 2times p + 2right) %3,hspace{16mm} if hspace{8mm} left( N+kright) %2=0} $$

These results could be proven in an induction method. In this method, we do not need to use the stacks. In each step, we know all the information before taking any action. The source code of the non-recursive method is:

Leave a Reply

Your email address will not be published. Required fields are marked *