Public Group

# [C++] 3n+1 Problem

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

## 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 on other sites
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 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 on other sites
Quote:
 Original post by Alpha_ProgDesUhhhhh, how do you get the while loop to terminate? Besides entering something else than an int.

Send an EOF (^D under most terminals).

##### 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

1. 1
Rutin
49
2. 2
3. 3
4. 4
5. 5

• 10
• 28
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633410
• Total Posts
3011727
• ### Who's Online (See full list)

There are no registered users currently online

×