Jump to content
  • Advertisement
Sign in to follow this  
whiz_kid

[C++] 3n+1 Problem

This topic is 3735 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been working on the 3n+1 problem from the 'Programming Challenges' book and I've got the program working, but the website doesn't seem to want to accept my program as correct. If anyone could help me out on what I'm doing wrong, it would be appreciated. If you don't know the 3n+1 problem, look here.
#include <iostream>
using namespace std;

int main()
{    
    unsigned long int n = 0;
    unsigned long int i = 0;
    int min = 0; 
    int max = 0;
    int temp = 0;
    int swapped = 0;
    
    int counter = 0;
    int maxCycles = 0;

    while(cin >> min >> max)
    {
        if(min > max)
        {
            temp = max;
            max = min;
            min = temp;
            
            swapped = 1;
        }
        for(i=min;i <= max;i++)
        {
            n = i;
            while(n > 1)
            {
                if((n%2) == 0)
                {
                    n = n/2;
                }
                else if((n%2) == 1)
                {
                    n = n*3+1;
                }
                counter++;
            }
            counter++;
            if(counter > maxCycles)
            {
              maxCycles = counter;
            }

            counter = 0;
        }
        if(swapped == 0)
          cout << min << " " << max << " " << maxCycles << endl;
        else
          cout << max << " " << min << " " << maxCycles << endl;
        maxCycles = 0; 
    }
    
    return(0);
}





Edit: I know I'm not doing anything fancy such as recursion, or optimizing it at all. I just wanted a basic structure of how it works, and then move on from there.

Share this post


Link to post
Share on other sites
Advertisement
Slice. Things. Up.

The point is that you should be using functions to make your code easier to read. Also, you should always define variables as locally as possible, so that you don't have to worry about the initial value of the variable. Ideally, you should have individually testable blocks instead of a single large function.

For instance, you can move the 3n+1 code to its own function:

unsigned step(unsigned n)
{
return n%2 ? 3*n+1 : n/2;
}


Then, you can write a function which computes the convergence time:

unsigned convergence(unsigned n)
{
unsigned count = 1;
while (n > 1) { n = step(n); ++count; }
return count;
}


From there, you can write a function to get the maximum number of cycles.

unsigned cycles(unsigned begin, unsigned end)
{
unsigned best = 0;
while (begin <= end) best = std::max( best, convergence(begin++) );
return best;
}


Last but not least, a function which attempts to read two integers (smaller and greater) and returns true if it works. Don't use swaps, merely describe what the begin and end values should be.

bool read(unsigned &begin, unsigned &end)
{
unsigned a, b;
std::cin >> a >> b;

begin = std::min(a,b);
end = std::max(a,b);

return std::cin;
}


Which means the loop itself becomes:

unsigned begin, end;
while ( read(begin,end) )
std::cout << begin << ' ' << end << ' ' << cycles(begin,end) << '\n';


Then, you can choose to test individual functions to see if they work correctly.

Share this post


Link to post
Share on other sites
Uhhhhh, how do you get the while loop to terminate? Besides entering something else than an int.

Also, you, Zahlman, Fruny = book, online class, [insert something awesome here]. Please!

Share this post


Link to post
Share on other sites
Quote:
Original post by Alpha_ProgDes
Uhhhhh, how do you get the while loop to terminate? Besides entering something else than an int.


Send an EOF (^D under most terminals).

Share this post


Link to post
Share on other sites
You don't reset the "swapped" variable. For example, your program produces wrong output for this input:
3 1
1 3

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!