100 - The 3n + 1 problem

[webgoudarzi]

jus to let you know this is the 3n + 1 problem

problem 100

[webgoudarzi]

im very sorry... im new here.. i should of made this post

please forgive me

[webgoudarzi]

Code: Select all

#include <iostream>
using namespace std;

class MaxCycle
{
public:
	int getMax(long i, long j);

private:
	long j;
	long i;

};

int MaxCycle::getMax(long i, long j)
{
	long long temp = 0;
	long long max = 0;
	long long count = 1;
	if ( i > j )
	{
		temp = i;
		i = j;
		j = temp;
	}
	for (int min = i; min <= j; min++)
	{
		count = 1;
		long long answer = min;

		do
		{
			if ( answer == 1 )
			{
				continue;
			}

			if ( answer%2 != 0 )
			{
				answer = (3 * answer) + 1;
			}
			else
			{
				answer = ( answer / 2 );
			}

			count++;

		} 

		while ( answer != 1);



		if ( count > max )
		{
			max = count;
		}
	}

	return max;
}




int main ()
{
	int firstNumber;
	int secondNumber;

	cin >> firstNumber >> secondNumber;
	
	MaxCycle M1;
	int result = M1.getMax(firstNumber,secondNumber);

	cout << firstNumber;
	cout << " ";
	cout << secondNumber;
	cout << " ";
	cout << result;
	cout << "\n";
	char response;
	cin >> response;
	return 0;
}

Good God my code seemed good to me. I saw some posts up there about inputing wrong. Not one by one or something. It confused me. I was hoping to get a personal answer

[webgoudarzi]

omg im sorry i thought i was replying to a forum

I accidentally made a new one so sorry. Please dont be mad

[webgoudarzi]

Code: Select all

#include <iostream>
using namespace std;

class MaxCycle
{
public:
	int getMax(long i, long j);

private:
	long j;
	long i;

};

int MaxCycle::getMax(long i, long j)
{
	long long temp = 0;
	long long max = 0;
	long long count = 1;
	if ( i > j )
	{
		temp = i;
		i = j;
		j = temp;
	}
	for (int min = i; min <= j; min++)
	{
		count = 1;
		long long answer = min;

		do
		{
			if ( answer == 1 )
			{
				continue;
			}

			if ( answer%2 != 0 )
			{
				answer = (3 * answer) + 1;
			}
			else
			{
				answer = ( answer / 2 );
			}

			count++;

		} 

		while ( answer != 1);



		if ( count > max )
		{
			max = count;
		}
	}

	return max;
}




int main ()
{
	int firstNumber;
	int secondNumber;

	cin >> firstNumber >> secondNumber;
	
	MaxCycle M1;
	int result = M1.getMax(firstNumber,secondNumber);

	cout << firstNumber;
	cout << " ";
	cout << secondNumber;
	cout << " ";
	cout << result;
	cout << "\n";
	char response;
	cin >> response;
	return 0;
}

I think something is wrong with the way i input. Could someone suggest something

[emotional blind]

Dont print unnecessery thinks at all it will give you wrong answer..

[chunyi81]

Have you read the thread at the top of this forum. Your question is answered there.

To make thing clear: There is more than one test case in the input. You program has to read input until end of file and not just one ionput and output.

[reemuskumar]

#include <iostream>

using namespace std;

int max_cyclic(int,int);
int cyclic(int);

int main() {
int i,j;

while(!cin.eof()) {
cin>>i>>j;
if (i<j)
cout<<i<<" "<<j<<" "<<max_cyclic(i,j)<<endl;
else
cout<<i<<" "<<j<<" "<<max_cyclic(j,i)<<endl;
}
return 0;
}
int max_cyclic(int num1, int num2) {
int cyc,max=cyclic(num1);

for(int i=num1+1;i<=num2;i++) {
cyc=cyclic(i);
if(cyc>max) max=cyc;
}
return max;
}

int cyclic(int n) {
int count=1;

while (n!=1) {
if (n%2==1) {
n=3*n+1;
} else {
n=n/2;
}
count++;
}
return count;
}

[reemuskumar]

I've posted many programs for 100. But I'm getting "Wrong Answer".

I have handled i>j and in display also it is on the order of the input.

Pls tell me what am I missing ?

Code: Select all

#include <iostream>

using namespace std;

int max_cyclic(int,int);
int cyclic(int);

int main() {
  int i[10],j[10],count=0,x=0;

  while(cin>>i[count]>>j[count]) {
     count++;
  }
  while(x<count) {
    if (i[x]<j[x])
      cout<<i[x]<<" "<<j[x]<<" "<<max_cyclic(i[x],j[x])<<endl;
    else
      cout<<i[x]<<" "<<j[x]<<" "<<max_cyclic(j[x],i[x])<<endl;
    x++;
  }
  return 0;
}
int max_cyclic(int num1, int num2) {
  int cyc,max=cyclic(num1);

  for(int i=num1+1;i<=num2;i++) {
    cyc=cyclic(i);
    if(cyc>max) max=cyc;
  }
  return max;
}

int cyclic(int n) {
  int count=1;

  while (n!=1) {
     if (n%2==1) {
        n=3*n+1;
     } else {
        n=n/2;
     }
     count++;
  }
  return count;
}

[emotional blind]

Dont think that there may maximum of 10 inputs
there may thousands of input.

And another thing,
you have to consider the cycle lengths of all numbers between i and j[INCLUSIVE]

[chunyi81]

Instead of using an array to store all the input, why don't you read input like this:

Code: Select all

while (cin >> i >> j)
{
// compute and output
}

[mac]

Hello. Here is part of my code that i'm having trouble with. For some reason when I print the biggest_length it is 0. I tried printing the cycle_length in the main function just to see if that was working, and it was also 0.

So I think there's a problem when i'm returning the value of the count in the algorithm function. When I just print it inside the function it works, but returning gives a 0. I thought the way I did it was valid, but apparently it's not. Could someone help me please.

This is obviously just a test case for ONE pair of non-zero integers.

Code: Select all

for (a=first;a<=last;a++)
{
	cycle_length = algorithm(a,counter); 
              
        if(cycle_length>biggest_length)
			        biggest_length = cycle_length; 

        counter=1; //reset the counter for the next integer
}

printf("%d %d %d",first,last,biggest_length); 

return 0;
}

/*Input: an integer, counter to count number of cycles
  Output: If the number isn't 1, the function is recursively called (using the
          given algorithm), until the number is 1. The number of cycles is returned.
*/

int algorithm(int number, int count)
{

if (number==1)
           return count;   //when i print from here it works fine
else if (number%2 !=0)
	   algorithm(3*number+1,count+1);
else
	   algorithm(number/2,count+1);
}

[LithiumDex]

Using recursion for this problem isn't a good idea, it will probably run out of stack space or something on the judges dataset.

you're algorithm function could be done like this:

Code: Select all

int algorithm ( int n )
{
    int ret = 1;
    while (n != 1)
    {
        if (n&1)
            n = n+n+n+1;
        else
            n = n>>1;
        ret ++;                
    }
    
    return ret;
}

P.S. But if you don't like that, you could fix your function by chaning your existing algorithm function too:

Code: Select all

int algorithm(int number, int count)
{

if (number==1)
           return count;
else if (number%2 !=0)
      return algorithm(3*number+1,count+1); // needs to be sent back
else
      return algorithm(number/2,count+1); // needs to be sent back
}

But yeah, and the reason recursion is useless here, is because this is a linear problem. (There's no branching)

[mac]

Thanks for replying LithiumDex. I updated my code and it works great now. One last question, how am I supposed to read an indefinte number of pairs from the judges dataset? I read the how to's and it says to use the standard IO and no files, but it doesn't specify what to use as a terminating integer (like -1 or something). It's my first submission so i'm not really sure how the judge wants it.

[LithiumDex]

just like this:

Code: Select all

while (cin >> i >> j)
{
.
.
.
}

and of course redirect the console input to a file (when testing)

so.. 100.exe <100.txt

or whatever