使用最少的呼叫数打印多项式

Question

我一直在接受这些艰难的面试问题.这个真让我感到困惑.

您将获得一个poly获取并返回的函数int.它实际上是一个非负整数系数的多项式,但你不知道系数是什么.

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

我的想法是使用递归知道我可以得到最后一个系数poly(0).所以我想,以取代poly用(poly - poly(0))/x,但我不知道如何做到这一点的代码,因为我只能打电话poly.任何人都知道如何做到这一点？

Answer 1

这是一个巧妙的技巧.

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并在基础上扩展它n,那么你得到

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

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