計算P 1中n + q^n的P + Q和PQ

Question

我解決上SPOJ

this問題

我們來計算（（P^N）+（Q^N）），我們給定 P + Q和P * Q。
輸入： 第一行包含表示的測試用例 三個整數P + Q，P * Q和n將給出對於每個測試實例中一個單獨的行 對於每個測試的數量的整數T（< = 15）情況下輸出對應的 輸出功率（p^N）+（q^N）在一個單獨的線

在一段時間之後我想出了這個復發

p^n + q^n = (p^n-1 + q^n-1)(p+q) - pq(p^n-2 + q^n-2) 
and in my code i have 
a = p + q and b = p.q 

這是我的溶液

個

public Long computeExponential(int n) 
    { 
    //base cases 
    if(n == 0) 
    { 
     return 1L; 
    } 
    else if(n == 1) 
    { 
     return new Long(a); 
    } 
    else 
    { 
     return (a * computeExponential(n-1) - b * computeExponential(n-2)); 
    } 

，我與給定的測試用例得到的答案是

2125764 
4383653 
-3 
175099 
28160 

是我有錯導出公式？

Answer 1

不，你的派生方程是點亮的。在您的實施中，我只能看到一個錯誤：

如果n=0,p^0 + q^0 = 1 + 1 = 2。您的computeExponential爲n=0返回1。

爲了將來的參考，對於複雜的算法，尤其是對於編寫我自己的測試用例，特別是對於基本情況，簡單情況和異常值，我手動計算結果以及然後運行這些首先檢查我的功能正在做我認爲應該做的。例如，用n = 0，p = 2，q = 3（例如p + q = 5，pq = 6）測試你的方法會很快引起這個錯誤。只有當它通過我自己的測試用例時，我纔會將其提交給其他測試數據，這些測試數據可能會或可能不會對我有任何意義。