1

完全な正方形は2進数で取得され、一部のビットは「？」に置き換えられます。たとえば、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の数値を入力してC++に移行しました（Pythonバージョンよりもはるかに高速でした）。

ただし、数値が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に切り下げて置き換えます。これらの2つの値を見つけ、それらを反復処理し、正方形にして、パターンと照合します。

これは、より少ない数を反復処理しているため、およびループ内の平方根を計算していないため、より高速です。二乗ははるかに簡単です。

一致を確認するために文字列を比較する必要はありません。

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でのみ機能し、最後のテストはPython2.xでオーバーフローrangeします

于 2013-02-14T10:42:25.750 に答える
2

私の理解では、整数が与えられた場合、次の値に一致nする平方数を見つけようとしています。sq

2 n - 1 <sq <2 n + 1-1

この条件は、「私の番号は1の形式である必要がありますか????」の数学的な翻訳です。n「？」があるところ。

まず、n偶数の場合、数値2 nは完全な正方形であり、条件に一致します（2進数では、数値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
または22p - 2p + 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のすべての数値を反復する必要はありません。実際、必要なのは1つの小数平方演算だけです。

整数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 に答える