#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);
}
[C++] 3n+1 Problem
Author
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.
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.
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:
Then, you can write a function which computes the convergence time:
From there, you can write a function to get the maximum number of cycles.
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.
Which means the loop itself becomes:
Then, you can choose to test individual functions to see if they work correctly.
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.
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!
Also, you, Zahlman, Fruny = book, online class, [insert something awesome here]. Please!
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).
You don't reset the "swapped" variable. For example, your program produces wrong output for this input:
3 1
1 3
3 1
1 3
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
