poj 1207 The 3n + 1 problem

  1. 云栖社区>
  2. 博客>
  3. 正文

poj 1207 The 3n + 1 problem

this_is_bill 2013-10-22 16:06:00 浏览690
展开阅读全文

当我看到题目的时候我就感觉到这是一道彻彻底底的水题,因为很像A+B的作风。。。

但是看完题目我心里想了想:应该没有那么水吧,可能还是要优化的,暴力可能会TLE。。。

但是我暴力过了以后我这样想:。。。。。。。


下面摘抄了一点文字说明:

大致题意:

根据给定的算法,可以计算一个整数的循环数

现在给定一个区间,计算这个区间的所有数的循环数,把最大的循环数输出

PS:输出的是整数A的循环数,而不是输出整数A

解题思路:

注意的只有一点:

输入的两个区间端点不一定是从小到大输入的,因此要先对这两个数排一下序。



【纯暴力】AC的代码:


#include<stdio.h>

int Process(int i)
{
	int count=1;
	while(i!=1)
	{
		if(i%2)
			i=3*i+1;
		else
			i/=2;
		count++;
	}
	return count;
}

//这题居然可以暴力过。。。我不解释
int main()
{
	int a,b;
	while(scanf("%d%d",&a,&b)!=EOF)
	{
		int x=a<b?a:b;
		int y=a>b?a:b;
		int Max=0;

		for(int i=x;i<=y;i++)
		{
			int temp=Process(i);
			if(Max<temp)
				Max=temp;
		}

		printf("%d %d %d\n",a,b,Max);
	}

	return 0;
}



写写自己”不暴力“的思路:

要维护两个集合

1. 每个数当然最好有一个自己的数组专门存循环节的长度,因为很可能区间有重叠。。。

2. 另外一个集合 【链表】就是把 循环序列 都存起来,因为循环节很可能就是重复的,比如知道 4 的长度是 3 ,那 8/2 以后就是 4 ,就不用算了,长度就是3+1=4;这样就要每次检查一次,如果有就结束循环,否则如果没有就 插入那个序列,这就涉及  搜索 ,当然最好用  二分。。。


这样就不算水了。。。


最后我并不是用这个解法。。。我是维护了一个Trace数组,相当于维护路径。。。之后再处理路径上的值的循环节。。。在电脑上对了,但是一直Runtime Error。。。改了数组上下界无数次也不行。。。后来直接改成 int 数组的极大值,AC了


附代码:

#include <stdio.h>

//自动初始化为0
int Num[99999999];
int Trace[99999999];

void RecordTrace(int count)
{
	int i;
	for(i=count;i>=1;i--)
	{
		if(Num[Trace[i]]!=0)
			continue;

		else
			Num[Trace[i]]=i;
	}
}



int Process(int pos)
{
	int count=1;
	Trace[1]=pos;
	while(pos!=1)
	{
		
		if(pos%2)
		{
			pos=3*pos+1;
			if(Num[pos]!=0)
			{
				count+=Num[pos];
				RecordTrace(count);
				return count;
			}

			else
			{
				count++;
				Trace[count]=pos;
			}
		}

		else
		{
			pos/=2;
			if(Num[pos]!=0)
			{
				count+=Num[pos];
				RecordTrace(count);
				return count;
			}

			else
			{
				count++;
				Trace[count]=pos;
			}
		}
	}
	
	return count;
}



int main()
{
	int a,b;
	while(scanf("%d%d",&a,&b)!=EOF)
	{
		int x=a<b?a:b;
		int y=a>b?a:b;
		int max=-1;
		
		int i,tmp;
		for(i=x;i<=y;i++)
		{
			if(Num[i]!=0)
			{
				if(Num[i]>max)
					max=Num[i];
			}
				
			else
			{
				tmp=Process(i);
				if(tmp>max)
					max=tmp;
			}
		}

		printf("%d %d %d\n",a,b,max);
	}
	
	return 0;
}




另:附上一个不水的解法

POJ 1207 HDOJ/HDU 1032 3n+1数链问题 绝对不水的解法


网友评论

登录后评论
0/500
评论
this_is_bill
+ 关注