1

この回答に基づいて、 Python 3.xで単純なアルゴリズムを実装して、整数nが別の整数の累乗であるかどうかを判断していbaseます。ただし、アルゴリズムは正しい結果を返しません。リンクされた回答のコードは次のとおりです。

while (n % 3 == 0) {
    n /= 3;
}
return n == 1;

（コメントn == 0は、論理的にもチェックが必要であることを示しています）。これは私のコードです：

def is_power(n: int, base: int) -> bool:
    if n == 0:
        return false
    while (n % base == 0):
        n /= base
    return n == 1

特定の範囲の基数と指数をテストする簡単なテストコードを作成しましたが、返される結果が正しくありません。テストコード：

for base in range(3, 10):
    print("Base: {0}".format(base))
    for exp in range(30, 40):
        b = is_power(pow(base, exp), base)
        if not(b):
            print("{: <3}: {: <5}".format(exp, str(b)))

これをはるかに広い範囲でテストしましたが、出力のために、この例では制限しました。これは以下を出力します：

Base: 3
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 4
Base: 5
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 6
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 7
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 8
Base: 9
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False

これは明らかに間違っています。私は小さな例をデバッグしようとしました。ここで、ループ内のこれらの値を生成n = pow(3, 35)します。base = 3n

50031545098999707
1.6677181699666568e+16

50031545098999707/3 == 1.667718169966656 9 e + 16であるため、ループは終了します（最後の桁が異なることに注意してください）。これは問題ですか？Pythonの計算は失敗していますか？そうでない場合、このアルゴリズムの問​​題は何ですか？

代わりに使用すると、アルゴリズムもさらに失敗しますが、1つの例を確認すると、常に同じ値が返されるとは限らmath.powないため、必ずしも驚かされるわけではpowありません。math.pow

import math
pow(3, 35) == math.pow(3, 35) # 50031545098999707 != 5.0031545098999704e+16
4

2 に答える 2

7

Python 3を使用しているので、

def is_power(n: int, base: int) -> bool:
    if n == 0:
        return false
    while (n % base == 0):
        n //= base
    #     ^^ note two slashes
    return n == 1

Python 3.xでは、/演算は常に「実際の除算」を実行し、浮動小数点数を返しますが、リンクしたアルゴリズムでは、 （「床除算」）/で行われる整数除算を実行することを想定しています。//代わりに演算子。

そして、あなたが期待したように、浮動小数点演算の精度が不足しているため、テストは実際に失敗します。/無限精度の実数を返す場合でも、アルゴリズムは正しいです。例として3.034を取り上げます。

3.0 ** 34 == 16677181699666569
          == 0b111011001111111100111011110011000100000011001010001001

デフォルトの浮動小数点形式は53ビットの精度しかサポートしていませんが、上記の数値を表すには5 4ビットが必要なので、最後のビット（1）を四捨五入する必要があります。

             0b111011001111111100111011110011000100000011001010001000
                                                                    ^
          == 16677181699666568

3へのモジュラスは2を返し、ループを中断してfalseを返します。

（なぜ切り上げではなく切り捨てるのかは確認していませんが、切り上げてもモジュラスはゼロではないため、falseが返されます。）

于 2012-07-21T20:40:32.710 に答える
2

あなたのアルゴリズムについて考えてください：あなたは何をしたい/=ですか？

浮動小数点除算？または整数除算？あなたの質問は明らかに前者を使用していますが、それを手で試して、それが機能するかどうかを確認してください-あなたは分割し続けbase、非整数を取得します。

Python 3では、整数の除算は//です。

于 2012-07-21T20:51:46.510 に答える