有道难题第二题最新算法（不仅仅是速度）

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

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

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

这是 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

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

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 的性能吧。

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

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