3.26. Write a function that takes the time as three integer arguments (hours, minutes and seconds) and returns a number of seconds since the last time the clock "struck 12". Use this function to calculate the amount of time in seconds between two times, both of which are within 12-hour cycle of the clock.
3.31. Write a function that takes an integer value and returns the number with its digits reversed. For example given the number 7631, the function should return 1367.
3.32. The greatest common divisor (GCD) of two integers is the largest integer that evenly divides each of the numbers. Write a function GCD that returns the greatest common divisor of two integers.
3.40. Write a recursive function power(base, exponent) that, when invoked, returns
base ^ exponent
For example, power(3, 4)=3 x 3 x 3 x 3. Assume that exponent is an integer greater than or equal to 1.
Hint: The recursive step would use the relationship
base ^ exponent = base x (base ^ (exponent-1))
and the terminating condition occurs when exponent is equal to 1 because
base ^ 1 = base.
3.42. (Towers of Hanoi) ... (avvalesh y 'aalame mozakhrafat dare) ... We wish to develop an algorithm that prints the percise sequence of peg-to-peg disk transfers.
If we were to approach this problem with conventional methods, wo would rapidly find ourselves hopelessly knotted up in managing the disks. Instead, if we attack the problem with recursion in mind, i immediately becomes tracable. Moving n disks can be viewed in terms of moving only n-1 disks (hence, recursion),, as follows:
a) Move n-1 disks from peg 1 to peg 2, using peg 3 as a temporary holding area.
b) Move the last disk (the largest) from peg 1 to peg 3.
c) Move the n-1 disks from peg 2 to peg 3, using peg 1 as a temorary holding area.
The process ends when the last task involves moving n=1 disk, i.e. the base case. This is accomplished by trivially moving the disk without the need for a teomporary holding area. Write a problem to solve the Towers of Hanoi problem. Use a recursive function with four parameters:
a) The number of disks to be moved
b) The peg on which these disks are initially threaded
c) The peg to which this stack of disks is to be moved
d) The peg to be used as a temporary holding area
Your program should print percise instructions it will take to move the disk from the starting peg to the destination peg. For example, to move a stack of three disks from peg 1 to peg 3 , your program should print the following series of moves:
1 -> 3 (This means move one disk from peg 1 to peg 3.)
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3
3.44. (Visualizing Recursion) It is interesting to watch recursion in action. Modify the Factorial function of fig.3.14 to print its local variable and recursive call parameter. For each recursive call display the outputs on a seperate line and add a level of indentation. Do your utmost to make the output clear, interesting and meaningful. Your goal here is to design and implement an output format that helps a person undestands recursion better. You may want to add such display capabilities to the many other recursion examples and exercises throughout the text.
11
12 unsigned long factorial( unsigned long ); //function prototype
13
14 int main()
15 {
16 // Loop 10 times. During each iteration, calculate
17 // factorial i and display result.
18 for ( int i = 0 ; i <= 10 ; i++ )
19 cout << setw( 2 ) << i << "! = "
20 << factorial( i ) << endl;
21
22 return 0; // indicates successful termination
23
24 } // end main
25
26 // recursive definition of function factorial
27 unsigned long factorial( unsigned long number )
28 {
29 // base case
30 if (number <= 1 )
31 return 1;
32
33 // recursive step
34 else
35 return number * factorial( number - 1 );
36
37 } // end function factorial
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
Fig. 3.14 Factorial calculation with a recursive function. (Part 2 of 2.)
3.45. (Recursive Greatest Common Divisor) The geatest common divisor of integers x and y is the largest integer that evenly divides both x and y. Write a recursive function GCD that returns the greatest common divisor of x and y, which is defines recursively as follows:
If y is equal to 0 then gcd(x, y) is x; otherwise, gcd(x, y) is gcd(x, x%y), where % is the modulus operator.
