|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 to 0, and A, A, A, ... 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 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 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 to 7, A to 6, A to 5, A to 4, A to 3 and A to 2. There is no need to reassign A 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|