CS13002 Programming and Data Structures
Section: 5/E, Spring 2006
Suppose that you are given a positive proper fraction a/b. Your problem is to write this fraction as
For example, consider the representations of the following two fractions:
Here is how such a representation can be computed. Follow an iterative procedure, where in each iteration the fraction a/b is decreased by 1/n for a suitable value of n. This value is chosen to be the positive integer satisfying the following:
Repeat the process until the fraction a/b reduces to zero.
Write a program that reads two integers a,b so that a/b is a positive proper fraction. Apply the above iterative algorithm. During each iteration, report the value of n for which 1/n is subtracted.
Report the output of your program on the following four fractions.11/31 17/34 17/53 41/43
As a bonus exercise you may try running your program on the fraction 71/73. Use a calculator to check if your program gave the correct result. I believe it didn't!
Sample outputSupply a proper positive fraction. Enter the numerator : 4 Enter the denominator : 9 The sequence of values of n is: 3 9 Supply a proper positive fraction. Enter the numerator : 11 Enter the denominator : 89 The sequence of values of n is: 9 81 7209
Theoretical questions (Not for submission)
Mathematically inclined students may try to answer the following questions.
- Does the above algorithm print the values of n in strictly increasing order?
- Is the above algorithm guaranteed to terminate after only a finite number of iterations?
- If yes, what is the maximum number of iterations that may be required? If not, provide an example for which the algorithm does not terminate.