修復遞歸求冪法？

我目前正在研究使用遞歸進行指數計算的方法。這是我到目前爲止：修復遞歸求冪法？

public static long exponentiation(long x, int n) { 

    if (n == 0) { 
     return 1; 
    } else if (n == 1) { 
     return x; 
     // i know this doesn't work since im returning long 
    } else if (n < 0) { 
     return (1/exponentiation(x, -n)); 
    } else { 
     //do if exponent is even 
     if (n % 2 == 0) { 
      return (exponentiation(x * x, n/2)); 
     } else { 
      // do if exponent is odd 
      return x * exponentiation(x, n - 1); 
     } 
    } 
}

我有兩個問題。首先問題是我不能做負指數，這不是一個主要問題，因爲我不需要做負指數。第二個問題是，某些計算給我錯誤的答案。例如2^63給了我正確的值，但它給了我一個負數。 2^64然後就給我0.有沒有辦法解決這個問題？我知道我可以將long改爲double，而且我的方法可以很好地工作。但是，我的教授要求我們使用long。感謝您的幫助！

來源

2016-04-13 name

[Long.MAX_VALUE]（http://docs.oracle.com/javase/8/docs/api/java/lang/Long.html#MAX_VALUE）。 – rgettman

@rgettman我明白這一點。我想知道是否有一種方法可以解決這個問題。我知道這可能聽起來像一個愚蠢的問題，但由於我是編程新手，我以爲我應該問問並看看。 – name

@ug_哦，好的。但爲什麼當我把長變成雙倍時，它會對更大的價值起作用？ – name

long可以表示的最大值是2^63 -1。所以，如果你計算2^63，那麼它就會更大，那麼一個長期可以持有和包裝的東西就會變大。 Long表示使用twos-complement。

只要將長變爲兩倍並不完全正常。它改變了方法的語義。浮點數的精度非常有限。對於64位浮點數，您仍然只能表示與64位整數相同數量的數字。他們只是分佈不同。一個long可以代表-2^63和2^63-1中的每個整數。雙數也可以表示數字的小數部分，但數量很高時，它甚至不能代表每個數字。

例如，下一雙可以代表後100000000000000000000000000000000000000000000000000是100000000000000030000000000000000000000000000000000 - 所以你missiong高達30000000000000000000000000000000000你不能用雙重代表。

您正試圖解決您不應該打擾修復的問題。使用很長時間，您的方法可能會返回一個固定的最大返回值。你的方法應該清楚地說明如果它溢出會發生什麼，你可能想要處理這種溢出（例如使用Math#multiplyExactly），但如果long是你應該返回的返回值，那麼這就是你應該使用的。

來源

2016-04-13 18:07:49 Polygnome

您可以將結果保存在一個long數組中，我們稱之爲result[]。首先，將邏輯應用於result[0]。但是，當該值變爲負數時，

1）增量result[1]超過。 2）現在，你的邏輯變得更加混亂，我正在打電話給我的手機，所以這部分留給讀者作爲練習。 3）當result[1]溢出時，在result[2]...上啓動

當您打印結果時，再次合併結果，邏輯混亂。

我認爲這是BigInteger的工作原理（或多或少）？我從來沒有看過那個代碼，你可能會想。

但是，基本上，Polygnone是正確的。沒有相當多的解決方法，就有一個上限。

來源

2016-04-13 18:23:55 user949300

修復遞歸求冪法？

回答

相關問題