The 3n + 1 problem
Consider the following algorithm:
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then n <- 3n + 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.
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
You can assume that no opperation overflows a 32-bit integer.
100 200
201 210
900 1000
100 200 125
201 210 89
900 1000 174
问题直接用暴力法就可以解出来,唯一要注意的一点就是i不一定小于j。
#include <iostream>
#include <cstdio>
using namespace std; int inline countTimes(int n)
{
int times = 1;
do
{
if(n & 0x1 == 1)
{
n = 3 * n + 1;
}
else
{
n = n >> 1;
}
++times;
}while(n != 1);
return times;
}
int main()
{
int i, j;
while (scanf ("%d%d", &i, &j) != EOF)
{
int bi1, bi2, bi3;
if (i > j)
{
bi1 = j;
bi2 = i;
}
else
{
bi1 = i;
bi2 = j;
}
int maxTimes;
maxTimes = countTimes (i);
for (int k = bi1 + 1; k <= bi2; k++)
{
bi3 = countTimes(k);
if (bi3 > maxTimes)
maxTimes = bi3;
}
cout << i << ' ' << j << ' ' << maxTimes << endl; }
system ("pause");
return 0; }