UVa 3n+1问题

UVa 3n+1 问题

<!---->1.       <!---->问题描述

编号 :100.

简单描述 : 就是对一个整数 ( 大于等于 1), 不断按照这样的规律进行运算 , 即如果当前数是偶数 , 则下一个数为当前数除以 2, 如果当前数为奇数 , 则下一个数为当前数乘 3 加 1, 整个过程直到计算到 1 为止 . 那么形成的数列的长度称为 cycle-length.

问题的输入是 : 给定一个区间 [a,b]

问题的输出为 : 输出给定区间 ( 含端点 ) 所以数的 cycle-length 的最大的 cycle-length.

详细描述可参见 这里 .

<!---->2.       <!---->问题分析

<!---->            <!---->2.1    直观分析

最直观的方法当然是采用蛮力法 ( 即 brute-force), 将给定区间的每个数求出其 cycle-length, 然后在所以的 cycle-length 中找出最大的即可 .

<!---->            <!---->2.2    优化

优化是建立在分析的基础之上 .

我们先对一个简单例子进行实验 .

例如给定区间为 B[1,10], 即 1,2,3,4,5,6,7,8,9,10

通过简单分析我们可以知道 , 通常较大的数具有较大的 cycle-length, 所以我们可以首先取 A=9( 为什么不取 10, 是因为 9 在一次处理后可变为 28, 大于 10) 按照给定的规律来进行如下 :

9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

可以看出 , 上面红色标记的部分 , 处于给定的区间内 , 而且它们的 cycle-length 显然是小于当前的数 9 的 cycle-length, 所以这些数可以从给定的区间内剔除掉 , 记住当前的 cycle-length, 于是

经过一次的操作后 , 给定的区间变为 3,6

继续按照这个方法进行 , 直至这个区间为空 , 停止 , 其中最大的 cycle-length 即为所求 .

<!---->            <!---->2.3    得出算法

算法的描述同 2.2 处优化部分的分析 , 具体的算法描述可见 3.

<!---->3.       <!---->算法描述

算法伪代码 ( 类 C) 描述如下 :

function getMCL

B[left, right];  // 为给定的区间

mcl = 0;               //mcl 指 max-cycle-length

while !B.empty()

{

A = getCandidate(B);// 这个函数是用来找出 B 区间内当前最适合处理的元素 ,

// 一般是最大的奇数 , 即预计可能具有较大 cycle-length 的元素

                     ccl = 1;          //ccl 是指 current-cycle-length

                     while (A!=1)

              {

                     ccl++;

                     A = (A%2)?(3*A+1):(A/2);

                     if find(B,A)           // 这个函数是用来判断 B 区间内是否存在中间结果 A

                            pop(B,A);       // 有则剔除

              }

              mcl = (mcl<ccl)?ccl:mcl;

       }

       return mcl;

 

<!---->4.       <!---->具体实现

#include "iostream"
using namespace std;

int getCandidate(int B[], int base, int n)
{
	int i;
	for (i = n-1; i>=0; i--)
	{
		if (((base+i) % 2)&&(B[i]==0))
			return i;
	}
	for (i = n-1; i>=0; i--)
	{
		if (!B[i])
			return i;
	}
	return -1;
}
int nadd2(int left, int right)
{
	int Blength = right - left + 1;
	int length = Blength;
	int *B = new int[length];
	for (int i=0; i<length; i++)
		B[i] = 0;
	int mcl = 0;
	while (length > 0)
	{
		int ccl = 1;
		int pos = getCandidate(B, left, Blength);
		if (pos==-1)
			break;
		B[pos] = 1;
		length--;
		int A = pos+left;
		while (A!=1)
		{
			ccl ++;
			A = (A%2)?(3*A+1):(A/2);
			int Apos;
			if ((A-left>Blength)||(B[A-left])||(A<left))
				Apos = -1;
			else
				Apos = A-left;
				
			//B[Apos] = 1;
			if (Apos!=-1)
			{
				B[Apos] = 1;
				length --;
			}
		}
		mcl = (mcl<ccl)?ccl:mcl;
	}
	delete[] B;
	return mcl;
}
int main()
{
	int left, right;
	while(cin>>left>>right)
		cout<<left<<" "<<right<<" "<<nadd2(left,right)<<endl;
	return 0;
}

 

 

<!----><!----><!---->

<!----><!----><!---->

<!---->5.       <!---->复杂性分析

主要的耗时部分是二层循环部分 , 而外层循环的次数主要取决于内层循环在区间内的命中率 . 没有进行过统计学的分析 , 但只要 candidate 选取合适 , 每次内层循环会有大于 50% 的命中率 .

假设区间内数 A 的内层循环次数 ( 即由 A 按照规则变为 1 的 cycle-length) 为 X, 平均命中率为 p, 那么时间复杂度为 :

T(n) = X*T(n*(1-p))     // 其中 X 为平均的 cycle-length

<!---->6.       <!---->备注

在实现过程中 , 最初使用的是 C++ 中的 vector, 但运行时的实际耗时比使用数组的蛮力法还要长 , 经过分析 , 这是因为编译器在维护 vector 这个数据结构时所耗时长是比较大的 , 特别是当使用 vector 的 earse 方法来删除某个特定元素时 . 所以最后还是使用最基本的数组来实现 , 用标记来指示删除状态 .

所以在实际的算法实现中 , 数据结构的选取也是非常重要的 , 所谓的程序 = 算法 + 数据结构是也 .

可以改进的地方包括有 :getCandidate 函数的算法 , 即如何预估一个具有较长 cycle-length 的元素 ; 还有当内层循环出现在区间内已标记为删除状态的元素中时 , 这时内层循环可终止 .

评论

1 楼 leeldy 2009-02-03  

我用C写过这个东西，以前的做法就是如果这个数据范围在10w以内，直接开个数组count用来保存每个数的cycle-length，这样速度会快很多
如果只是运算一次的话，速度的提升不会很明显，但是如果有相当多的数据要计算的话，这种用空间换时间的速度是非常快的
具体做法如下：

初始化max=0;
开始输入：
得到一个区间，扫描这个区间内的每一个数，是否都已经计算过cycle-length，如果计算过，则直接取这个数于max比较
如果没有计算过就计算以后再取这个值（计算过程也可以利用以前计算过的数据来避免重复计算，开个临时数组当做堆栈）
一直到扫描完整个区间
此时就可以得出来max

因为以前计算过的所有数据都保存在数组count中，所以多次运算的话，已经计算过的数就不会再计算

说得有点笼统，但是这个问题是相当有技巧的
总是想方设法避免重复计算就可以了
但是如果数据很大的话，就需要仔细考虑一下细节问题了