3n+1 problem of acm

[iuz]

Dear group,

The below given link which I want to implement in C.

http://online-judge.uva.es/p/v1/100.html

The code which I wrote does not even reaches the near to the
given problem.(I am just learning) [..]

Once the n gets the even number it just divides it by two
and, at the end n reaches with even number and terminates.
Can any one give me some clue or hint for correct implementation.
of the above?

this seems to work..
#include <stdio.h>

int is_odd (int n)
{
return n%2;
}

int main (void)
{
int number;
scanf("%d", &number);
if (number > 0) {
while (1) {
printf("%d ", number);
if (number == 1) {
break;
}
if (is_odd(number)) {
number = 3 * number + 1;
} else {
number = number / 2;
}
}
}
exit(0);
}

 

[sathyashrayan]

Dear group,

The below given link which I want to implement in C.

http://online-judge.uva.es/p/v1/100.html

The code which I wrote does not even reaches the near to the
given problem.(I am just learning)

#include<stdio.h>
#include<stdlib.h>

unsigned evn,odd;

void odd_evn(unsigned int number)
{
if((number % 2) == 0)
{
evn = 1;
odd = 0;
}
evn = 0;
odd = 1;
}

int main(int argv, char *argc[])
{
unsigned long n;
unsigned int i,j;
int counter=0;
if(argv == 0 && argv >=3)
{
printf("eror\n");
exit(EXIT_FAILURE);
}

i=atoi(argc[1]);
j=atoi(argc[2]);
for(n=i; n<j;n++)
{
odd_evn(n);
if(odd == 1 && evn == 0)
n = (3 * n) + 1;
if(odd == 0 && evn == 1)
n = n / 2;
counter++;
printf("%lu and %d\n",n, counter);
}
return 0;
}

Once the n gets the even number it just divides it by two
and, at the end n reaches with even number and terminates.
Can any one give me some clue or hint for correct implementation.
of the above?

 

[osmium]

:

The below given link which I want to implement in C.

http://online-judge.uva.es/p/v1/100.html

The code which I wrote does not even reaches the near to the
given problem.(I am just learning)

#include<stdio.h>
#include<stdlib.h>

unsigned evn,odd;

void odd_evn(unsigned int number)
{
if((number % 2) == 0)
{
evn = 1;
odd = 0;
}
evn = 0;
odd = 1;
}

The function above does nothing except use up some time. change it to:

int odd(unsigned int number)

and then return 1 to signify odd. A name such as odd/even is simply
annoying. Which is it? odd? Even?

int main(int argv, char *argc[])
{
unsigned long n;
unsigned int i,j;
int counter=0;
if(argv == 0 && argv >=3)
{
printf("eror\n");
exit(EXIT_FAILURE);
}

i=atoi(argc[1]);
j=atoi(argc[2]);
for(n=i; n<j;n++)
{
odd_evn(n);
if(odd == 1 && evn == 0)

Don't do this belt and suspenders thing. Write

if(odd( ...) )

n = (3 * n) + 1;
if(odd == 0 && evn == 1)
n = n / 2;
counter++;
printf("%lu and %d\n",n, counter);
}
return 0;
}

Once the n gets the even number it just divides it by two
and, at the end n reaches with even number and terminates.
Can any one give me some clue or hint for correct implementation.
of the above?

I don't know if that is all you need to make it work. Doing things wrong is
a huge part of the learning process so being helpful is not, in case like
this, very helpful.

 

[osmium]

The below given link which I want to implement in C.

http://online-judge.uva.es/p/v1/100.html

The code which I wrote does not even reaches the near to the
given problem.(I am just learning)

#include<stdio.h>
#include<stdlib.h>

unsigned evn,odd;

void odd_evn(unsigned int number)
{
if((number % 2) == 0)
{
evn = 1;
odd = 0;
}
evn = 0;
odd = 1;
}

The function above does nothing except use up some time. change it to:

int odd(unsigned int number)

and then return 1 to signify odd. A name such as odd/even is simply
annoying. Which is it? odd? Even?

int main(int argv, char *argc[])
{
unsigned long n;
unsigned int i,j;
int counter=0;
if(argv == 0 && argv >=3)
{
printf("eror\n");
exit(EXIT_FAILURE);
}

i=atoi(argc[1]);
j=atoi(argc[2]);
for(n=i; n<j;n++)
{
odd_evn(n);
if(odd == 1 && evn == 0)

Don't do this belt and suspenders thing. Write

if(odd( ...) )

n = (3 * n) + 1;
if(odd == 0 && evn == 1)
n = n / 2;
counter++;
printf("%lu and %d\n",n, counter);
}
return 0;
}

Once the n gets the even number it just divides it by two
and, at the end n reaches with even number and terminates.
Can any one give me some clue or hint for correct implementation.
of the above?

I don't know if that is all you need to make it work. Doing things wrong
is a huge part of the learning process so being helpful is not, in case
like this, very helpful.

That post is utter nonsense. I didn't see the global variables. Ignore
everything I said except the part about a bad name.

 

[osmium]

The below given link which I want to implement in C.

http://online-judge.uva.es/p/v1/100.html

The code which I wrote does not even reaches the near to the
given problem.(I am just learning)

#include<stdio.h>
#include<stdlib.h>

unsigned evn,odd;

void odd_evn(unsigned int number)
{
if((number % 2) == 0)
{
evn = 1;
odd = 0;
}
evn = 0;
odd = 1;
}

int main(int argv, char *argc[])
{
unsigned long n;
unsigned int i,j;
int counter=0;
if(argv == 0 && argv >=3)

How can any number be equal to 0 and greater than 3?
<snip>

 

[Michael Mair]

Dear group,

The below given link which I want to implement in C.

http://online-judge.uva.es/p/v1/100.html

The code which I wrote does not even reaches the near to the
given problem.(I am just learning)

#include<stdio.h>
#include<stdlib.h>

unsigned evn,odd;

void odd_evn(unsigned int number)
{
if((number % 2) == 0)
{
evn = 1;
odd = 0;
}
evn = 0;
odd = 1;

This code always executes the last two statements.
Either put this part into an else branch or directly compute
evn and odd via
odd = ((number % 2) != 0);
evn = 1 - odd;
or similar.

}

int main(int argv, char *argc[])

You changed the usually used main parameter identifiers.
It's
int main (int argc, char **argv)
This is perfectly legal but may irritate or confuse people
reading your code.

{
unsigned long n;
unsigned int i,j;

unsigned int has a minimal maximum value of 65535 -- this
is not enough for the task at hand. Use unsigned long values.

int counter=0;
if(argv == 0 && argv >=3)

This is never true.
Make it
if (argv != 3)

{
printf("eror\n");
exit(EXIT_FAILURE);
}

i=atoi(argc[1]);
j=atoi(argc[2]);

atoi() is not exactly the safest input function; in addition,
it does not guaranteedly cover the range discussed. Read up on
the use of strtoul().

for(n=i; n<j;n++)
{

Within this loop, you are supposed to determine the cycle length
for every number from i to j, including i and j.

odd_evn(n);
if(odd == 1 && evn == 0)
n = (3 * n) + 1;
if(odd == 0 && evn == 1)
n = n / 2;

What a mess.
You obviously do not need evn at all as evn always is 1-odd;
this is the second, unnecessary, check you are performing for
every if.
In addition, the two if conditions are mutually exclusive.

if (odd)
n = (3 * n) + 1;
else
n = n/2;

counter++;
printf("%lu and %d\n",n, counter);

You misunderstood the task.

}
return 0;
}

Once the n gets the even number it just divides it by two
and, at the end n reaches with even number and terminates.
Can any one give me some clue or hint for correct implementation.
of the above?

unsigned long max = 0;
unsigned long index;
unsigned long cycle_length;

for (index = i; index <= j; index++) {
cycle_length = determine_cycle_length(index);
if (cycle_length > max) {
max = cycle_length;
}
}
printf("%lu %lu %lu\n", i, j, max);

matches the requirements from the link. Now just implement
determine_cycle_length along the given algorithm.


Cheers
Michael

 

[Herbert Rosenau]

Dear group,

The below given link which I want to implement in C.

http://online-judge.uva.es/p/v1/100.html

The code which I wrote does not even reaches the near to the
given problem.(I am just learning)

#include<stdio.h>
#include<stdlib.h>

unsigned evn,odd;

void odd_evn(unsigned int number)
{
if((number % 2) == 0)
{
evn = 1;
odd = 0;
}

Why does you destroy the set you've made when the if is true? When you
remove the whole if block there would be noch change on the result in
any case.

Hint: for what does else exist?

evn = 0;
odd = 1;
}

int main(int argv, char *argc[])
{
unsigned long n;
unsigned int i,j;
int counter=0;
if(argv == 0 && argv >=3)
{
printf("eror\n");
exit(EXIT_FAILURE);
}

i=atoi(argc[1]);
j=atoi(argc[2]);
for(n=i; n<j;n++)
{
odd_evn(n);
if(odd == 1 && evn == 0)
n = (3 * n) + 1;
if(odd == 0 && evn == 1)
n = n / 2;
counter++;
printf("%lu and %d\n",n, counter);
}
return 0;
}

Once the n gets the even number it just divides it by two
and, at the end n reaches with even number and terminates.
Can any one give me some clue or hint for correct implementation.
of the above?

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2 Deutsch ist da!

 

[Walter Roberson]

this seems to work..
#include <stdio.h>

while (1) {
printf("%d ", number);

You never output a \n . Your output is not certain to appear at
all, and if it does appear it might get erased by the next command
prompt.

 

[Peter Nilsson]

Dear group,

The below given link which I want to implement in C.

http://online-judge.uva.es/p/v1/100.html

The code which I wrote does not even reaches the near to the
given problem.(I am just learning)

Can any one give me some clue or hint for correct implementation.
of the above?

Hmmm....

"The input will consist of a series of pairs of integers i and j, one
pair
of integers per line. All integers will be less than 1,000,000 and
greater than 0. ...

"You can assume that no opperation overflows a 32-bit integer. "

You know what they say about _ass_u_me_ don't you... ;-)


% type 3n1.c
#include <stdio.h>
#include <stdlib.h>

#if 0
#define PRINT printf
#else
#define PRINT while (0) printf
#endif

int main(int argc, char **argv)
{
unsigned long i, j, input, n;
unsigned long c, mc = 0;

if (argc != 3) { return 0; }
i = strtoul(argv[1], 0, 10);
j = strtoul(argv[2], 0, 10);
if (i == 0) { return EXIT_FAILURE; }

for (input = i; input <= j; input++)
{
n = input;
PRINT("%lu -\n", n);
c = 1;

while (n != 1)
{
if ((n % 2) == 0) /* even? */
n /= 2;
else if (n <= (-1UL - 1) / 3) /* 'safe' odd? */
n = n * 3 + 1;
else /* overflow! */
{
printf("\noverflow");
printf(": input = %lu", input);
printf(", cycle = %lu", c);
printf(", n = %lu\n", n);
exit(EXIT_FAILURE);
}

PRINT(" %lu\n", n);
c++;
}

PRINT(" cycle(s):%lu\n", c);
if (c > mc) mc = c;
}

printf("%lu %lu %lu\n", i, j, mc);
return 0;
}

% acc 3n1.c -o 3n1.exe

% 3n1.exe 1 10
1 10 20

% 3n1.exe 100 200
100 200 125

% 3n1.exe 201 210
201 210 89

% 3n1.exe 900 1000
900 1000 174

% 3n1.exe 1 999999

overflow: input = 159487, cycle = 60, n = 1699000271

%

 

[Richard Heathfield]

Peter Nilsson said:

Hmmm....

"The input will consist of a series of pairs of integers i and j, one
pair
of integers per line. All integers will be less than 1,000,000 and
greater than 0. ...

"You can assume that no opperation overflows a 32-bit integer. "

You know what they say about _ass_u_me_ don't you... ;-)

% 3n1.exe 1 999999

overflow: input = 159487, cycle = 60, n = 1699000271

In this case, it would appear that you (yes, you, Peter!) assumed that the
ACM will provide arbitrary input. Have you not considered the possibility
that they might have thought of that already, and filtered out such inputs
from their online judge's test data stream?

 

[iuz]

You never output a \n . Your output is not certain to appear at
all, and if it does appear it might get erased by the next command
prompt.

really? i didn't know..
can you tell me in which cases omitting the new line can give this kind of
problem?

 

[Michael Mair]

really? i didn't know..
can you tell me in which cases omitting the new line can give this kind of
problem?

The _last_ output of your programme should be a newline character.
In the following, I assume that you work with a console:
Most of the time, you only will see something like
lastOuputNextPrompt >
instead of
lastOutput
NextPrompt >
but it is also possible that you only see
NextPrompt >
If "lastOutput" is the only information given by your programme and
output after three days of non-stop computation, the latter case is
rather annoying...

If you do not work with a run-of-the-mill console or not a console
at all, then your IO may be line based and input or output happens
only for '\n'-terminated character sequences.
So, you are on the safe side if you append an '\n'. No disadvantages.

Note: You can force output using fflush().


Cheers
Michael

 

[sathyashrayan]

Thanks for all the help that this group provides.

 

[iuz]

Michael Mair wrote:

[..]

If you do not work with a run-of-the-mill console or not a console
at all, then your IO may be line based and input or output happens
only for '\n'-terminated character sequences.
So, you are on the safe side if you append an '\n'. No disadvantages.

Note: You can force output using fflush().

[..]

thanks..

 

[Jordan Abel]

really? i didn't know..
can you tell me in which cases omitting the new line can give this kind of
problem?

On my system, if there is no newline at the end of the last line of
output, the cursor will remain at the end of the line. My shell clears
the line and returns the cursor to the left edge before printing its
prompt.

 

[Peter Nilsson]

Peter Nilsson said:


In this case, it would appear that you (yes, you, Peter!)
assumed that the ACM will provide arbitrary input.

No, I tested that my reading of ACM's assertion is correct
for the specified input range. I found it not to be the case.

In any case, the notion that a C program can make wholesale
assumptions about the input it receives is dangerous.

Have you not considered the possibility that they might have
thought of that already, and filtered out such inputs
from their online judge's test data stream?

If ACM were to specify that no input line is longer than say
60 characters, would that mean that it's okay to use gets()?

Just because someone tells you that the input they supply
will not cause problems is no reason to take that input or
their assertion for granted.