The 3n + 1 problem (Acm's problem set,help)

C

c_beginner

As a mean to improve my C skill for a more of program oriented
I started the acm's problem set.

In the following code the stdin gets the two inputs but the program
does not proceeds further. Please help.

The problem link follows:


http://acm.uva.es/p/v1/100.html

The program:

#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
unsigned int is_odd(unsigned int num)
{
if((num % 2) == 0)
return 0; /* the num is even*/
else
return 1; /* else odd*/
}

int main(void)
{
unsigned int i,j; /*The two numbers*/
unsigned int i_counter=0,j_counter=0; /*calcuting the counters*/
unsigned int cycle_length; /* total cycle lenght*/

fscanf(stdin,"%d%d",&i,&j);
if ( i == (UINT_MAX + 1) || j == (UINT_MAX + 1))
{
exit(1); /*exit on error*/
}
while( i++ && j++ )
{
if(is_odd(i) && is_odd(j))
{
i = (3 * i )+1;
j = (3 * j )+1;
}
else
{
i = i / 2 ;
j = j / 2;
}
i_counter++;
j_counter++;
}
cycle_length = i_counter + j_counter;
printf("%d\n",cycle_length);
return 0;
}

Please guide me to the proper logics.

--
Nothing is stable, even the universe.
By
Hindu God

Mail to :sathyashrayan at gmail dot com
 
V

Vladimir S. Oka

c_beginner said:
As a mean to improve my C skill for a more of program oriented
I started the acm's problem set.

In the following code the stdin gets the two inputs but the program
does not proceeds further. Please help.

The problem link follows:


http://acm.uva.es/p/v1/100.html

The program:

#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
unsigned int is_odd(unsigned int num)
{
if((num % 2) == 0)
return 0; /* the num is even*/
else
return 1; /* else odd*/
}

int main(void)
{
unsigned int i,j; /*The two numbers*/
unsigned int i_counter=0,j_counter=0; /*calcuting the counters*/
unsigned int cycle_length; /* total cycle lenght*/

fscanf(stdin,"%d%d",&i,&j);
if ( i == (UINT_MAX + 1) || j == (UINT_MAX + 1))

The problem states 1,000,000 as the maximum number allowed, and assumes
32-bit integers. For those UINT_MAX is considerably larger than
1,000,000. You need to fix this.
{
exit(1); /*exit on error*/

return EXIT_FAILURE;

may be more appropriate here (although using `exit()` is not an error);

When did you expect the loop below to finish? The way you state it,
it'll only finish when both `i` and `j` wrap around zero at the same
time. Unless i == j this will never happen.

Also, the problem states that you should check every number *between*
`i` and `j` for the cycle length, and you're clearly not doing this.
while( i++ && j++ )
{
if(is_odd(i) && is_odd(j))
{
i = (3 * i )+1;
j = (3 * j )+1;
}
else
{
i = i / 2 ;
j = j / 2;
}
i_counter++;
j_counter++;
}
cycle_length = i_counter + j_counter;
printf("%d\n",cycle_length);
return 0;
}

Please guide me to the proper logics.

The whole thing above is not per problem stated. You need to step
between `i` and `j`, say using some `k` and check cycle lengths of all
`k`s, keeping track of the largest one. In pseudo code:

max_cycle = 0
max_k = 0

for k = i to j

tmp = get_cycle_length(k)

if tmp > max_cycle then
max_cycle = tmp
max_k = k
end if

end for

So, there's the logic you asked for. Now, go and try to write it in C.
Any problems, come back and ask. (I deliberately didn't specify the
logic of get_cycle_length, you have that already in the problem).
 
U

Ulrich Eckhardt

c_beginner said:
unsigned int i,j; /*The two numbers*/
unsigned int i_counter=0,j_counter=0; /*calcuting the counters*/
unsigned int cycle_length; /* total cycle lenght*/

fscanf(stdin,"%d%d",&i,&j);

According to my manpage, '%d' is for signed integers. Also, before using
those values you should check that reading them succeeded, i.e. check the
returnvalue of fscanf. Lastly, fscanf( stdin, ..) is the same as
scanf(...).
if ( i == (UINT_MAX + 1) || j == (UINT_MAX + 1))
{
exit(1); /*exit on error*/
}

"If either of i or j is by one larger than the maximum value they can hold"
is the if condition in plain english. Doesn't make sense, right? Also,
provide a meaningful errormessage and use EXIT_FAILURE as exitvalue.
while( i++ && j++ )
{ [...]
i_counter++;
j_counter++;
}
cycle_length = i_counter + j_counter;

You are aware that these two independent counters will always have the same
values, right? Also, since you are possibly dealing with integers and
their overflows, I would check for that, too.
return 0;

Similarly, use EXIT_SUCCESS here.

Please guide me to the proper logics.

What are the logics? We're usually willing to help solve C problems, but
what are the required logics? What is the problem? What is happening, what
did you expect?

Uli
 
K

Kenneth Brody

c_beginner wrote:
[...]
In the following code the stdin gets the two inputs but the program
does not proceeds further. Please help. [...]
unsigned int i,j; /*The two numbers*/ [...]
fscanf(stdin,"%d%d",&i,&j);
[...]
while( i++ && j++ )
{ [...]
[...]
Please guide me to the proper logics.

What will it take to break out of that while loop?

Will that condition ever be met?

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>
 
K

Keith Thompson

Ulrich Eckhardt said:
c_beginner wrote: [...]
return 0;

Similarly, use EXIT_SUCCESS here.

Returning 0 from main is fine. The portable values to return from
main (or to pass to exit()) are 0, EXIT_SUCCESS, and EXIT_FAILURE.
exit(1) is *not* portable; it denotes failure on some systems, success
on others.

On the other hand, if you're using EXIT_FAILURE elsewhere in the
program, it's probably better style to use EXIT_SUCCESS rather than 0,
just for the sake of symmetry.

(Both 0 and EXIT_SUCCESS denote successful termination, but they're
not necessarily equal.)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top