The Problem
Consider the following algorithm:
1. input n 2. print n
3. if n = 1 then STOP
4. if n is odd then n = 3*n+1
5. else n = n/2
6. GOTO 2
Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j
**Normal non recursive method**
#include
nt Definitions */ @font-face {font-family:“Cambria Math”; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-1610611985 1107304683 0 0 159 0;}@font-face {font-family:Calibri; panose-1:2 15 5 2 2 2 4 3 2 4; mso-font-charset:0; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:-1610611985 1073750139 0 0 159 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin-top:0in; margin-right:0in; margin-bottom:10.0pt; margin-left:0in; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:“Calibri”,“sans-serif”; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Calibri; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:“Times New Roman”; mso-bidi-theme-font:minor-bidi;}.MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Calibri; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:“Times New Roman”; mso-bidi-theme-font:minor-bidi;}.MsoPapDefault {mso-style-type:export-only; margin-bottom:10.0pt; line-height:115%;}@page Section1 {size:8.5in 11.0in; margin:1.0in 1.0in 1.0in 1.0in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;}div.Section1 {page:Section1;}–>using namespace std;
int main()
{
unsigned int i, j;
int count, cmax;
int process(int x);
cout«"Enter range:\nFrom:";
cin»i;
cout«”\nTo: “;
cin»j;
cout<_«” “<_
_for(;i<=j;i++) {
count=process(i); _
_if(count>cmax)
cmax=count;
}
cout«” “<
return 0;
}
int process(int x)
{
int count;
_
_for(count=1;x!=1;++count)
{
if(x%2==0)
x/=2;
**else
** x=3*x+1;
}
return count;
}_
_Recursive Solution
_
_#include <stdio**.**h\>
#define SIZE 1000001
**static** unsigned **short** table**\[**SIZE**\]****;**
unsigned **short** calcCycleLength**(**register unsigned **long** n **)**
**{**
**if****(**n < SIZE && table**\[**n**\]****)**
**return** table**\[**n**\]****;**
**if****(**n & 1**)****{** _/\* if n is odd \*/_
**if****(** n < SIZE**)** **{**
table**\[**n**\]** \= 2 + calcCycleLength**(** **(**3\*n+1**)** \>\> 1 **)****;** _/\* calc two steps at one \*/_
**return** table**\[**n**\]****;**
**}**
**else**
**return** 2 + calcCycleLength**(** **(**3\*n+1**)** \>\> 1 **)****;**
**}**
**else** **{**
**if****(** n < SIZE**)** **{**
table**\[**n**\]** \= 1 + calcCycleLength**(** n \>\> 1 **)****;** _/\* n/2 \*/_
**return** table**\[**n**\]****;**
**}**
**else**
**return** 1 + calcCycleLength**(** n \>\> 1 **)****;**
**}**
**}**
**int** main**(****)**
**{**
unsigned **long** i**,** fstIn**,** sndIn**;**
**short** out \= 0**,** temp**;**
table**\[**1**\]** \= 1**;**
**while** **(** scanf**(**"%lu %lu"**,** &fstIn**,** &sndIn **)** !\= EOF **)**
**{**
**if****(** fstIn \> sndIn**)** **{**
**for****(** i \= sndIn**;** i <\= fstIn**;** ++i **)**
**{**
temp \= calcCycleLength**(** i **)****;**
**if****(** temp \> out**)**
out \= temp**;**
**}**
**}**
**else** **{**
**for****(** i \= fstIn**;** i <\= sndIn**;** ++i **)**
**{**
temp \= calcCycleLength**(** i **)****;**
**if****(** temp \> out**)**
out \= temp**;**
**}**
**}**
printf**(**"%lu %lu %hdn"**,** fstIn**,** sndIn**,** out**)****;**
out \= 0**;**
**}**
**return** 0**;**
**}**_
```