有道难题第二题最新算法(不仅仅是速度)

2009/06 16 04:06

最近好像算法问题又不热门了,米关系,自己喜欢就好。我的有道第二题不是双倍超立方,也不知道是什么算法,大概的题目意思,大家可以参考:“我的有道第二题(不是双倍超立方)

 

其实一开始我觉得很简单,我写的第一个解法也是正确的,不过讨厌在题目说,输入的n可以为2,000,000,000。 20亿。。。。。如果N为最大的时候,不用看了,我的解法直接out,第一时间很长,第二,直接out of Memory

 

那该怎么做呢???我寻思着它的规律,其实一直有种感觉,可一直把握不住,而且平时也没什么时间静下来,不过老留着这个问题,我一直睡不着觉,所以还是找了时间找了一下规律。我把n设为16,因为16已经足够让我们看出规律了,如果再小,这个规律也很难让我们立足。按照我第一次的解法,打印 n=16 的拼接字符串 A:

01
0110
01101010
0110101010100010
01101010101000101010001011100010

这是 n=16 时,每次循环所打印出的字符,由此我们看出,我们的循环次数为:Log2(N+1),这个不是重点,我们要找的是规律,可以看出,2的n次幂位,也就是A(2 ^ n) 一定是1,这是为什么呢?稍后说。

再来说说完全平方数:根据定义,一个数n 如果 等于 i * i 那我们就认定n为完全平方数。i<=n

按照题目,如果index 是完全平方数,则 B[index] = 1 - A[index]  ,从题目来看,其实也就是取反 0 -> 1   1->0

接着上面的来说,为什么A(2 ^ n) 一定是1呢?我们知道,每次循环的时候,A  = A + B

B是根据A的每位判断是否是完全平方数而决定的,且A的长度也是有规律的 2 ^ n 位,所以,2 ^ n 位 其实就是对A[0] 的一个判断

根据完全平方数定义, 因为 0 = 0 * 0  所以它是一个完全平方数

B[0] = 1 - A[0] = 1 - 0 = 1

这就是为什么2 ^ n 一定是1的原因了。

接下来,我们分析其他位数的规则。

其实一开始我也很迷茫,因为想到了重点,但始终捉不到它,越是如此,我越是痴迷,毕竟没学过算法,也不知道数据结构,只能慢慢的自己找寻答案,现在已经懊悔当初的年少轻狂了。

我们再看下 (2 ^ n )+ 1 位,你会发现,始终是0,按照上面的证明,我们知道,(2^n) + 1始终是对A[1]的一个判断。

1 = 1 * 1

所以 1 是完全平方数,也就是对 A[1] 的一次取反操作,而1 = 2 ^ 0  所以 A[1] = 1 所以 A[(2^n) + 1] = 0

好了,到这里大家是否已经看出点规则了呢?我稍微写一下,因为我也不是很懂,只能写个大概

A[n] = IsSqrt(A[n - 2 ^ (log2(n)]) ? 1- A[n - 2 ^ (log2(n)] : A[n - 2 ^ (log2(n)]

 

IsSqrt方法,是判断这个数是否是完全平方数,代码如下:

public bool IsSqrt(double n)
{
return Math.Sqrt(n).Equals(Math.Truncate(Math.Sqrt(n)));
}

可以看出,它是判断OldA(循环前的A)相对应位数的一个判断,那我们是不是也要进行log2(n+1)次循环吗?当然不需要,可以看出,如果是前几位的话,我们只需要循环到前几位的log2n就可以了,或许说得很朦胧,简单说下,

当n=16的时候,我们需要判断的是上一次A的第0位(16 - 2 ^ (floor(log2 16))) = 0

而0其实在每次循环中,都会是取A[0]的一个判断,所以我们只要判断 包含此位数的最小XXX (不知道怎么说)

我们只需要得到 log2(index) 次的循环就可以了。废话了这么多,我表达比较差,还是看我写的代码吧,我写了2种,意义是一样的,只不过一种用了递归,一种没有用而已。

        public int GetValues(int n)
{
if (getValue(n))
return 1;
else
return 0;
}
public bool getValue(double n)
{
double baseN = Math.Floor(Math.Log(n, 2));
double index = n - Math.Pow(2, baseN);
if (index == 0) return true;
bool isSquer = IsSqrt(index);
return isSquer ^ getValue(index);
}
 

上面是递归的做法,下面是没有递归的做法:

        public int GetValues(int n)
{
double baseN = Math.Floor(Math.Log(n, 2));
bool isSqrt = true;
double index = n - Math.Pow(2, baseN);
while (index > 0)
{
isSqrt = isSqrt ^ IsSqrt(index);
index = index - Math.Pow(2, Math.Floor(Math.Log(index, 2)));
}
return isSqrt ? 1 : 0;
}
 

两者其实是一个意思,大家可以自己理解一下我的意思吧,哈哈。

 

我知道应该还有更好的做法,比如位移,但我的能力有限,只能做到这里了,最后看下在n = 2,000,000,000 的性能吧。

image

 

额。。。。。不递归的情况下,竟然快了1个数量级。。。。。

 

我这个算法,真的没什么科学依据,也希望高手能指点一下,给出一个公式之类或者证明之类的,也可以给出新的好的算法。

--转载请注明: http://www.jamesying.com/2009/06/16/%e6%9c%89%e9%81%93%e9%9a%be%e9%a2%98%e7%ac%ac%e4%ba%8c%e9%a2%98%e6%9c%80%e6%96%b0%e7%ae%97%e6%b3%95%ef%bc%88%e4%b8%8d%e4%bb%85%e4%bb%85%e6%98%af%e9%80%9f%e5%ba%a6%ef%bc%89/

发表回复

欢迎回来 (打开)

(必填)