## CS13002 Programming and Data Structures | ## Section: 5/E, Spring 2006 |

## Assignment 2

Suppose that you are given a positive proper fraction

a/b. Your problem is to write this fraction aswhere

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/bis decreased by 1/nfor a suitable value ofn. This value is chosen to be the positive integer satisfying the following:Repeat the process until the fraction

a/breduces to zero.Write a program that reads two integers

a,bso thata/bis a positive proper fraction. Apply the above iterative algorithm. During each iteration, report the value ofnfor which 1/nis subtracted.

Report the output of your program on the following four fractions.11/31 17/34 17/53 41/43As 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
nin 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.