UVA 100: The 3n+1 problem

Here’s my C++ code:

// This program computes the maximum cycle length over all numbers between i and j.

#include 
#include 

using namespace std;

//Prototype
int cycle_length(int);

int main() {
	int a, b, temp; //The 2 numbers and a temp slot for swapping
	int max = 0; //Maximum cycle length
	int length; //Cycle length of the current number
	stringstream ss; //String stream acts as a buffer to write the output to
	bool swapped = false; //A, B swap flag

	// For every pair of numbers compute the maximum cycle length over all numbers between i and j
	while(cin >> a >> b) {
		if(a > b) { // If a < b, swap them
			temp = a;
			a = b;
			b = temp;
			swapped = true;
		}

		for(int i = a; i <= b; i++) { // For each number in the range calculate its cycle length
			length = cycle_length(i);

			if(length > max) //New max length encountered
				max = length;
		}

		if(swapped) {
			ss << b << " " << a << " " << max << endl;
			swapped = false;
		} else
			ss << a << " " << b << " " << max << endl;

		max = 0; //Reset the max
	}

	cout << ss.str();

	return 0;
}

int cycle_length(int num) { //Calculates the cycle length of num
	int len = 1;

	while(num != 1) {
		if(num%2 == 0) //If even, double
			num /= 2;
		else //If odd multiply by 3 and add 1
			num = num *3 + 1;

		len++;
	}

	return len;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s