0

入力として大きな数 (800 桁以上) を取り、複雑な数学のない単純な式を文字列として返す関数を作成しようとしています。

単純な数学とは、必要に応じて+、-、*、/、^、および()を使用した数字のみを意味します。

'4^25+2^32' = giveMeMath(1125904201809920); // example

どの言語でも構いません。ロジックに関するヘルプを探しているだけで、リファクタリングできます。

ボーナス。出力は短いほどよい。処理時間は重要です。また、数学的な正確さも必要です。

更新: 明確にするために、すべての入力値は正の整数 (小数なし) になります。

4

4 に答える 4

2

問題全体は、長整数のバイナリ表現に関するランレングス エンコーディングの問題に言い換えることができると思います。

たとえば、次の番号を使用します。

17976931348623159077293051907890247336179769789423065727343008115773
26758055009631327084773224075360211201138798713933576587897688144166
22492847430639474110969959963482268385702277221395399966640087262359
69162804527670696057843280792693630866652907025992282065272811175389
6392184596904358265409895975218053120L

これはかなり恐ろしく見えます。ただし、バイナリでは：

>>> bin(_)
'0b11111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111100000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
0000000'

これは約 500 個の 1 の後に 500 個のゼロが続きます。これは、次のような表現を示唆しています。

2**1024 - 2**512

これが、最初に多数を取得した方法です。

整数のバイナリ表現に大幅に長いランがない場合、これはまったくうまく機能しません。101010101010101010....最悪のケースです。

于 2012-04-23T05:15:09.483 に答える
0

ご覧になることをお勧めします

  1. 演算を実行するためのGMPライブラリ (The GNU Multiple Precision Arithmetic Library)

  2. 整数因数分解を見てください。リンクはウィキペディアにリダイレクトされ、おそらく概要がよくわかるはずです。ただし、もう少し科学的にするために：

于 2012-04-23T04:35:58.700 に答える
0

BigDecimalJava では、java.math パッケージのクラスを確認する必要があります。

于 2012-04-23T04:11:40.420 に答える
0

Pythonでの私の試みは次のとおりです。

def give_me_math(n): 

    if n % 2 == 1:
        n = n - 1  # we need to make every odd number even, and add back one later
        odd = 1
    else:
        odd = 0
    exps = []

    while n > 0:
        c = 0
        num = 0
        while num <= n/2:
            c += 1
            num = 2**c

        exps.append(c)    
        n = n - num
    return (exps, odd)

結果：

>>> give_me_math(100)
([6, 5, 2], 0)  #2**6 + 2**5 + 2**2 + 0 = 100

>>> give_me_math(99)
([6, 5, 1], 1)  #2**6 + 2**5 + 2**1 + 1 = 99

>>> give_me_math(103) 
([6, 5, 2, 1], 1) #2**6 + 2**5 + 2**2 + 2**1 + 1 = 103

結果は正確だと思いますが、他の基準についてはわかりません。

編集：

結果: 約 1 秒で計算されます。

>>> give_me_math(10**100 + 3435)
([332, 329, 326, 323, 320, 319, 317, 315, 314, 312, 309, 306, 304, 303, 300, 298, 295, 294, 289, 288, 286, 285, 284, 283, 282, 279, 278, 277, 275, 273, 272, 267, 265, 264, 261, 258, 257, 256, 255, 250, 247, 246, 242, 239, 238, 235, 234, 233, 227, 225, 224, 223, 222, 221, 220, 217, 216, 215, 211, 209, 207, 206, 203, 202, 201, 198, 191, 187, 186, 185, 181, 176, 172, 171, 169, 166, 165, 164, 163, 162, 159, 157, 155, 153, 151, 149, 148, 145, 142, 137, 136, 131, 127, 125, 123, 117, 115, 114, 113, 111, 107, 106, 105, 104, 100, 11, 10, 8, 6, 5, 3, 1], 1)

800 桁も高速に動作します。

>>> give_me_math(10**800 + 3452)

しかし、出力が長すぎてここに投稿できません。これはもちろん OP の懸念事項です。

ここでの時間計算量は 0(ln(n)) であるため、かなり効率的です。

于 2012-04-23T04:47:22.447 に答える