我一直得到这些难以回答的面试问题,这个问题真的让我困惑。
给你一个函数poly
,它接受并返回一个int
。它实际上是一个具有非负整数系数的多项式,但你不知道这些系数是什么。
你需要编写一个函数,尽可能少地调用poly
来确定这些系数。
我的想法是使用递归,知道我可以通过poly(0)
得到最后一个系数。所以我想用(poly - poly(0))/x
替换poly
,但我不知道如何在代码中实现这一点,因为我只能调用poly
。 有人有办法吗?
我一直得到这些难以回答的面试问题,这个问题真的让我困惑。
给你一个函数poly
,它接受并返回一个int
。它实际上是一个具有非负整数系数的多项式,但你不知道这些系数是什么。
你需要编写一个函数,尽可能少地调用poly
来确定这些系数。
我的想法是使用递归,知道我可以通过poly(0)
得到最后一个系数。所以我想用(poly - poly(0))/x
替换poly
,但我不知道如何在代码中实现这一点,因为我只能调用poly
。 有人有办法吗?
这里有个巧妙的方法。
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
。