CS19002 Programming and Data Structures Laboratory |
Spring 2010, Section 5 |

This exercise is a continuation of Assignment 1.
In brief, you read from the user a bound *B*, and print the numbers
of iterations in a specific fashion. Proceed as follows.

Inside the `main()` function, declare an array to store the iteration
lengths. Call this array *A*. Initialize *A*[1] to 0, and
*A*[2], *A*[3], *A*[4], `...` to -1. Call a function
to compute the number of iterations for *n* = 2, 3, 4, `...` (in that
sequence). Both *n* and the array *A* should be passed to the
function.

Write the function as follows. It starts the 3*x*+1 loop on *n*.
As soon as a value of *n* is reached for which *A*[*n*] >= 0,
the iteration is stopped, because the number of iterations starting from this
value of *n* is already stored in the array, so there is no need to
recompute this again. Note that in the worst case your program will reach
*n* = 1, and *A*[1] was initialized to 0. After the
iteration count for the parameter *n* is determined with the help of
the array *A*, the function restarts with the original value of
*n*, runs the 3*x*+1 loop, and populates the array until there
is no need to proceed further.

As an example, let us look at the computation in the function for *n* = 3.
Before this call, only the first and second locations of *A* are set. The function
runs 6 iterations with *n* = 3, 10, 5, 16, 8, 4.
The next value of *n* is 2, but the array location *A*[2]
is already set to 1. So the function knows that the initial value of 3
requires 6 + 1 = 7 iterations. It then reruns the
loop, and sets *A*[3] to 7, *A*[10] to 6, *A*[5] to 5,
*A*[16] to 4, *A*[8] to 3 and *A*[4] to 2. There is no need
to reassign *A*[1] again to 1.

Finally, the function returns the iteration length for the input value
of *n*.

The `main()` function, after getting the return value, finds out
whether this *n* gives a sequence larger than those previously
discovered. If so, the value of *n* and the iteration length for
*n* are printed.

Here is a sample output.

Enter bound: 25 len[ 1] = 0 len[ 2] = 1 len[ 3] = 7 len[ 6] = 8 len[ 7] = 16 len[ 9] = 19 len[ 18] = 20 len[ 25] = 23

Submit the output of your program for the bound *B* = 1000.

Lab Home | Submission Site | My Home |