13

我不断收到这些棘手的面试问题。这个真的让我很困惑。

你得到一个函数poly，它接受并返回一个int. 它实际上是一个具有非负整数系数的多项式，但你不知道系数是什么。

您必须编写一个函数，使用尽可能少的调用来确定系数poly。

我的想法是使用递归知道我可以得到最后一个系数poly(0)。所以我想用 替换poly，(poly - poly(0))/x但我不知道如何在代码中执行此操作，因为我只能调用poly. 任何人都知道如何做到这一点？

4

1 回答 1

28

这是一个巧妙的技巧。

int N = poly(1)

现在我们知道多项式中的每个系数最多为N。

int B = poly(N+1)

现在扩展B基数N+1，你就有了系数。

尝试的解释：代数上，多项式是

poly = p_0 + p_1 * x + p_2 * x^2 + ... + p_k * x^k

如果您有一个数字b并将其扩展为 base n，那么您会得到

b = b_0 + b_1 * n + b_2 * n^2 + ...

其中每个b_i都是唯一确定的并且b_i < n.

于 2011-07-09T19:18:13.133 回答