--- In [email protected], shamir shakir <dewswo...@...> wrote:
> Please have a look at these 2 code. These are the solution of this problem,
> http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36...
"You can assume that no operation overflows a 32-bit integer."
They obviously didn't try 159487, 212649, 239231 (et al), or they're
excluding them from the test input.
> code 1:
...
> if(min > max)
> {
> min^=max;
> max^=min;
> min^=max;
> }
Did you miss the thread on swapping variables?
<snip>
> code 2:
> #include <stdio.h>
>
> int algorithm(int input)
There is no guarantee that int is sufficient to store 999,999.
> {
> int cycle ;
>
> cycle = 1 ;
>
> while( input!=1)
> {
> cycle++ ;
> if(input%2)
> input = (3*input) + 1 ;
> else input = input/2 ;
>
> } ;
>
> return cycle ;
> }
You can speed this up greatly by storing the cycle length
as they are computed.
[You can speed it up even more by analysing numbers in the
range 2^n+1..2^n+(2^n-1).
4n + 1 -> 3n + 1
16n + 3 -> 9n + 2
32n + 11 -> 27n + 10
32n + 23 -> 27n + 20
128n + 7 -> 81n + 5
128n + 15 -> 81n + 10
128n + 59 -> 81n + 38
256n + 39 -> 243n + 38
256n + 79 -> 243n + 76
256n + 95 -> 243n + 91
256n + 123 -> 243n + 118
256n + 199 -> 243n + 190
256n + 219 -> 243n + 209
256n + 175 -> 243n + 167
...
]
> int main()
> {
> int i,j ;
> int key, temp,temp2 ;
>
> while((scanf("%d %d", &i, &j)))
while (scanf("%d %d", &i, &j) == 2)
scanf may return EOF, 0, 1 or 2 here. If it returns EOF, which
is negative, you get an infinite loop.
> {
>
> temp = 0 ;
> key = 0 ;
> temp2 = i ;
>
> for(i; i<=j ;i++)
uva3n+1_shamir.c:33: warning: statement with no effect
Why not something readable, like...
for (max = 0, n = start; n <= end; n++)
{
cycle = algorithm(n);
if (cycle > max) max = cycle;
}
> {
> temp = algorithm(i) ;
> if(key <temp) key = temp ;
> }
>
> printf("\n%d %d %d", temp2, j, key) ;
>
> }
>
> return 0 ;
> }
--
Peter
