algorithm - 使用最少的调用数打印多项式

我一直在问这些难以回答的面试问题。这个真让我困惑。
我们给了一个函数poly，它接受并返回一个int。它实际上是一个非负整数系数的多项式，但是你不知道系数是什么。
您必须编写一个函数，该函数使用尽可能少的对poly的调用来确定系数。
我的想法是使用递归，知道我可以通过poly(0)得到最后一个系数。所以我想用poly替换(poly - poly(0))/x，但我不知道如何在代码中实现这一点，因为我只能调用poly。有人知道怎么做吗？

最佳答案

这里有一个巧妙的技巧。
int N = poly(1)
现在我们知道多项式中的每个系数最多都是N。
int B = poly(N+1)
现在在baseB中展开N+1，得到系数。
尝试解释：代数上，多项式是

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

如果您有一个数字b并在basen中展开它，那么您将得到

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

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

关于algorithm - 使用最少的调用数打印多项式，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6636878/