0

私はSPOJでこの問題を解決していました

( (P^N) + (Q^N) ) を計算すると、P+Q と P*Q が与えられます。
入力 : 最初の行には、テスト ケースの数を示す整数 T (<=15) が含まれます。3 つの整数 p+q、p*q、および n は、テスト ケースごとに別の行でテスト ケースごとに指定されます。対応する出力(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

私が導き出した式は間違っていますか？

4

1 に答える 1

1

No, your derived equation is spot-on. Just a wee error in your implementation that I can see:

If n=0, p^0 + q^0 = 1 + 1 = 2. Your computeExponential for n=0 returns 1.

[edit]For future reference, I find it quite helpful, for complicated algorithms especially, to write my own test cases, especially for the base cases, simple cases, and outliers, that I have manually calculated the results for and then run these first to check my function is doing what I think it should. Testing your method with n=0, p=2, q=3 (i.e. p+q=5, pq=6) for example would have thrown this error up pretty quickly. Only once it passes my own test cases would I then submit it to other test data which may, or may not, have any meaning to me.

于 2012-06-03T10:32:05.220 に答える