1

一个完美的正方形采用二进制格式，一些位被替换为“？” 例如 1??，数字将是 4.（或 1????000???0000）

我需要找到那个完美的正方形。（只有这样的可能数字）

字符串中的 '?' 数为 n

为了找到这个数字，我正在做的是遍历 2**n 个数字（111,110,101,100）并检查它是否是一个完美的正方形。我正在使用以下函数来检查它是否是一个完美的正方形。

bool issqr(int n){
   int d=(int)(sqrt(n));
   if(d*d==n) return true;
   else return false;
}

即使在 python 中我做到了，它也需要很多时间，所以我只使用位操作来填充 2**n 数字（这比 python 版本快得多）转移到 C++

但如果数字超过 64 位，则会失败

如何避免这个问题？如果一个数字有 120 位，我怎么能做同样的事情。

(10100110???1?1?01?1?011000?1100?00101000?1?11001101100110001010111?0?1??0110?110?01?1100?1?0110?1?10111?01?0111000?10? ?101?01)

4

4 回答 4

3

与其用 C++ 重写，不如先考虑改进算法。最低可能的答案是原始值的平方根，所有“？” 替换为四舍五入的 0，可能的最高答案是模式的平方根，将“？”替换为向下舍入的 1。找到这两个值，遍历它们，平方并检查模式。

这更快，因为您迭代的数字要少得多，而且因为您没有在循环中计算任何平方根：平方要容易得多。

您无需比较字符串即可检查匹配项：

mask = int(pattern.replace('0', '1').replace('?', '0'), 2)
test = int(pattern.replace('?', '0'), 2)

def is_match(n):
    return (n&mask)==test

所以把它们放在一起：

def int_sqrt(x):
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    n = int(x)
    if n == 0:
        return 0
    a, b = divmod(n.bit_length(), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y

def find_match(pattern):
    lowest = int(pattern.replace('?', '0'), 2)
    highest = int(pattern.replace('?', '1'), 2)
    mask = int(pattern.replace('0', '1').replace('?', '0'), 2)
    lowsqrt = int_sqrt(lowest)
    if lowsqrt*lowsqrt != lowest:
            lowsqrt += 1
    highsqrt = int_sqrt(highest)
    for n in range(lowsqrt, highsqrt+1):
        if (n*n & mask)==lowest:
            return n*n

print(find_match('1??1??1'))
print(find_match('1??0??1'))
print(find_match('1??????????????????????????????????????????????????????????????????????1??0??1'))

输出：

121
81
151115727461209345152081

注意 这仅适用于 Python 3.x，最后一个测试将range在 Python 2.x 中溢出

于 2013-02-14T10:42:25.750 回答
2

据我了解，给定一个整数n，您试图找到一个sq匹配的平方数：

2 n - 1 < 平方 < 2 n+1 - 1

这个条件是“我的数字必须有形式 1????”的数学翻译。哪里有n“？”。

首先，您可以注意到，如果n是偶数，则数字 2 n是一个完全平方并且符合您的条件（在二进制中，它是数字 1000...000 - n 个零 -）。

如果n是不均匀的（比如 n = 2.p + 1），那么 2 n+1是一个完美的正方形（(2 p+1 ) 2）。计算以下数字将为您提供一个完美的正方形：

(2 p+1 - 1) 2

为了满足第一个不等式，p 必须满足：

2 n - 1 < (2 p+1 - 1) 2

然后

0 < 2 n+1 - 2 p+2 + 1 - 2 n + 1，

最后，

2 n + 2 - 2 p+2 > 0
或
2 2p - 2 p+1 + 1 > 0

如果我们考虑将 p 与 f(p) 匹配的函数，则：

f(p) = 2 2p - 2 p+1 + 1

该函数是为每个正实数定义的，并且是严格递增的。此外，f(0) = 0。最后，当p > 0! 对于p = 0- 或n = 1-，问题没有有效的解决方案。

于 2013-02-14T10:40:32.880 回答
0

您不需要遍历所有 2**n 数字来找到完美的平方，实际上您只需要一个小数平方操作：

假设您有整数 n，并且您想找到小于或等于 n 的最大完全平方，我们将其称为 m。然后：

d = (int)sqrt(n);
m = d*d;

解释：

假设有一个完美的正方形 m' 比 m 大，这意味着有一个整数 d' 使得：d' > d 并且 d'*d' = m'。

但是 d' >=d+1 和 (d+1)*(d+1) > n 所以 m' > n 与我们的要求 m' <= n 相矛盾。

现在回答你的问题：

为了找到完美的正方形，只需将所有“？”更改为“1”。并找到完美的正方形，如果它符合你的字符串，你得到了你正在寻找的数字，如果没有改变足够的“？” 从 msb 到“0”，使结果数字小于或等于您刚刚找到的完美正方形，并继续前进，直到找到完美正方形或用完选项。

于 2013-02-14T10:36:27.540 回答
-1

您的操作可能返回对于整数来说太大的东西...... http://www.cplusplus.com/doc/tutorial/variables/

于 2013-02-14T10:36:05.747 回答