3N+1/김상섭

4358392 2006-02-24 00:56:30 Accepted 2.207 4360 28565 C++ 100 - The 3n + 1 problem

~cpp
#include <iostream>
#include <vector>
using namespace std;

const int Min = 1;
const int Max = 1000000;
int table[Max];

struct Data
{
	int num;
	int pre_count;
};

void process()
{
	vector<Data> data;
	Data temp;
	int i, j, k, count;
	unsigned long num;
	for(i = Min; i < Max; i++)
	{
		if(table[i] == 0)
		{
			num = i;
			count = 1;
			while(num != 1)
			{
				if(num % 2 == 0)
				{
					temp.num = num /=2;
					temp.pre_count = count++;
					if(num > Min && num < Max && table[num] == 0)
						data.push_back(temp);
				}
				else if(num % 2 != 0)
				{					
					temp.num = num = num*3 + 1;
					temp.pre_count = count++;
					if(num < 0)
						cout << " 하하 " <<endl;
					if(num > Min && num < Max && table[num] == 0)
						data.push_back(temp);
				}
			}
			table[i] = count;
			for(j = i; j < Max; j *=2)
				table[j] = count++;
			for(k = 0; k < data.size(); k++)
			{
				count = table[i] - data[k].pre_count;
				for(j = data[k].num; j < Max; j *=2)
					table[j] = count++;
			}
			data.clear();
		}
	}
}

int main()
{
	int i, j, k, max_num;
	process();
//	for(i =1; i < 20; i++)
//		cout << i << " " << table[i] << endl;
//	cout << table[999999];
	while(cin >> i >> j)
	{
		cout << i << " " << j << " ";
		if(i > j)
		{
			k = j;
			j = i;
			i = k;
		}
		max_num = 0;
		for(k = i; k <= j; k++)
		{
			if(table[k] > max_num)
				max_num = table[k];
		}
		cout << max_num << endl;
	}
	return 0;
}