用最少次数的调用打印一个多项式

Question

我一直得到这些难以回答的面试问题，这个问题真的让我困惑。

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

你需要编写一个函数，尽可能少地调用poly来确定这些系数。

我的想法是使用递归，知道我可以通过poly(0)得到最后一个系数。所以我想用(poly - poly(0))/x替换poly，但我不知道如何在代码中实现这一点，因为我只能调用poly。 有人有办法吗？

- Daniel

---

这个对我来说完全没有意义。当你调用Poly(x)或者Poly(coefficient_index)时，单个整数参数x的名称和含义是什么？它返回一个系数？它返回什么？你的问题定义不清楚。 - Warren P

你知道有多少个术语吗？ - Oliver Charlesworth

@Warren：我认为OP的意思是对于形如'a+b.x+c.x^2+d.x^3+...'的表达式，当'x=0'时进行求值会得到'a'。 - Oliver Charlesworth

不，你不知道程度。我认为那会有所帮助。 - Daniel

@warren：是啊，我知道。我觉得我挂了。我完全不知道该怎么做，那就是我能想到的全部了。 - Daniel

Oli = 看起来 x=0 返回常数项，而 x=1 返回常数项和系数之和。 - Warren P

Answer 1

这里有个巧妙的方法。

int N = poly(1)

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

int B = poly(N+1)

现在用N+1作基数展开B，然后你就能得到系数了。

---

尝试解释：代数上，这个多项式为

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。

- PengOne

---

我完全不理解这个。 - Daniel

我来解释一下。为了简化论述，假设有一个多项式 poly = 4x^3 + 3x^2 + x + 2。如果你计算 poly(1)，这将给你多项式系数的和，因为你只需要计算 41^3 + 31^2 + 11 + 2。由于所有系数都是非负的，你知道 poly(1) + 1 > 任何一个系数。既然你对此有信心，那么你可以继续计算 poly(M)，其中 M = poly(1) + 1。这将给你 4M^3 + 3M^2 + 1M^1 + 2*M^0。这看起来像是基数 M 的定义（就像二进制是基数 2，十六进制是基数 16 等）。继续... - Draksis

好的。那我该怎么想到这样做呢？ - Daniel

很好。你正在利用所有数量都是非负整数的事实。我本来以为我们需要和次数一样多的调用。我相信这对于实系数是成立的。 - Szabolcs

@PengOne，我认为对于实系数来说，在严格意义上无法检测出次数。 - Szabolcs