0

我在 SPOJ 上解决了这个问题

我们要计算 ( (P^N) + (Q^N) )，我们得到 P+Q 和 P*Q。
输入：第一行将包含一个整数 T (<=15) 表示测试用例的数量 三个整数 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

不，您导出的方程式是正确的。我可以看到您的实现中的一个小错误：

如果n=0，p^0 + q^0 = 1 + 1 = 2。你computeExponential的n=0回报1。

[编辑]为了将来参考，我发现它非常有帮助，特别是对于复杂的算法，编写我自己的测试用例，特别是对于基本用例、简单用例和异常值，我已经手动计算了结果然后首先运行这些检查我的功能正在做我认为应该做的事情。例如，使用 n=0、p=2、q=3（即 p+q=5、pq=6）测试您的方法会很快引发此错误。只有当它通过我自己的测试用例后，我才会将它提交给其他测试数据，这些数据可能对我有任何意义，也可能没有任何意义。

于 2012-06-03T10:32:05.220 回答