вычисления р^п + д^п от р + д и рд

Question

Я решала this проблемы на SPOJ

Мы должны вычислить ((P^N) + (Q^N)), мы данные P + Q и P * Q.
Входной сигнал: Первая строка будет содержать целое число T (< = 15), обозначающее количество тестовых случаев три целые числа р + д, р * д и п будут даны для каждого теста в отдельной строке для каждого теста случай выход соответствующий выход (р^п) + (д^п) в отдельной строке

Через некоторое время я пришел с этим рецидивом

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)); 
    } 

Ответы, которые я получаю с данными testcases является

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), например, очень быстро переместило бы эту ошибку. Только после того, как он пройдет мои собственные тестовые примеры, я затем отправлю его другим тестовым данным, которые могут или не могут иметь какой-либо смысл для меня.