Assignment 2

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 3x+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 3x+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