Collatz conjectur

Collatz conjectur

The Collatz conjecture is an unsolved conjecture in mathematics named after Lothar Collatz, who first proposed it in 1937. The conjecture is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanisław Ulam), Kakutani’s problem (after Shizuo Kakutani), Thwaites conjecture (after Sir Bryan Thwaites), Hasse’s algorithm (after Helmut Hasse) or the Syracuse problem;[1] the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers,[2] or as wondrous numbers.[3] – from http://en.wikipedia.org/wiki/Collatz_conjecture

The problem is here: http://online-judge.uva.es/p/v1/100.html

My solution not using STL is as below:

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

const char *const INPUT_FILE = "sample.in";		// file name

// A structure of pairs of integer i and j
typedef struct _ITEM{
	int i;
	int j;
	struct _ITEM *Next;
}ITEM;

void init(void);
void read(istream &);
void solveIt(const ITEM *, int *);
bool isValid(const ITEM *, const int *);

ITEM *Head;
ITEM *Tail;

void main()
{
	ifstream in;
	in.open(INPUT_FILE);
	if(in.bad()){
		cerr << "[Error] Could not open " << INPUT_FILE << '\n';
		exit(8);
	}

	init();

	read(in);
         in.close();

	int nCycle = 0;
	int i=0; ITEM *list;
	for(list = Head->Next; list != Tail; list = list->Next, i++)
	{
		if(isValid(list, &i))
		{
			solveIt(list, &nCycle);
			cout << list->i << " " << list->j << " " << nCycle << endl;
		}
	}

	return ;
}

// Initialize a linked list
void init(void)
{
	Head = (ITEM*)malloc(sizeof(ITEM));
	Tail = (ITEM*)malloc(sizeof(ITEM));
	Head->Next = Tail;
	Tail->Next = Tail;
}

// Read two integers from stream
void read(istream &in)
{
	while(!in.eof()){
		ITEM *ptr;
		ptr = (ITEM*)malloc(sizeof(ITEM));

		in >> ptr->i;
		in >> ptr->j;

		if(Head->Next == Tail)
		{
			ptr->Next = Tail;
			Head->Next = ptr;
		}
		else
		{
			ITEM *tmp;
			tmp = Head;
			while(tmp->Next != Tail)
			{
				tmp = tmp->Next;
			}

			ptr->Next = Tail;
			tmp->Next = ptr;
		}
	}
}

// Get the answer to determine the maximum cycle length by each item
void solveIt(const ITEM *v, int *maxCycle)
{
	int max=0;
	for(int n = v->i; n <= v->j; n++)
	{
		int cur = n;
		int count = 1;

		while(cur > 1)
		{
			// cout << "cur: " << cur << " " << "count: " << count << endl;

			if(cur & 1)
			{
				cur = 3*cur + 1;
				count++;
			}
			else if(!(cur & 1))
			{
				cur = cur >> 1;
				count++;
			}
		}

		if(max <= count){
			max = count;
		}

		// cout << "n: " << n << " " << "max: " << max << endl;
	}

	*maxCycle = max;
}

// check whether all integers are less than 1,000,000 and greater than 0
bool isValid(const ITEM *v,  const int *idx)
{
	bool b = (0 < v->i && v->i < 1000000) && (0 < v->j && v->j < 1000000) ;
	if(!b)
		cerr << "[Error]Invalid data: (" << v->i << " " << v->j <<") at line " << (*idx)+1 << endl;
	return b;
}

Advertisement