问题描述
我不断遇到这些艰苦的面试问题。
I keep getting these hard interview questions. This one really baffles me.
您会得到一个函数 poly ，该函数接受并返回 int 。它实际上是具有非负整数系数的多项式，但是您不知道系数是什么。
You're given a function poly that takes and returns an int. It's actually a polynomial with nonnegative integer coefficients, but you don't know what the coefficients are.
您必须编写一个函数，该函数使用对的最少调用来确定系数 poly 尽可能。
You have to write a function that determines the coefficients using as few calls to poly as possible.
我的想法是使用递归，因为我知道我可以得到<$ c的最后一个系数$ c> poly（0）。所以我想用（poly-poly（0））/ x 替换 poly ，但是我不知道如何在代码中执行此操作，因为我只能调用 poly 。
My idea is to use recursion knowing that I can get the last coefficient by poly(0). So I want to replace poly with (poly - poly(0))/x, but I don't know how to do this in code, since I can only call poly. ANyone have an idea how to do this?
推荐答案
这是一个绝妙的把戏。
int N = poly（1）
现在我们知道多项式中的每个系数都在大部分 N 。
Now we know that every coefficient in the polynomial is at most N.
int B = poly（N + 1）
现在在基数 N + 1 B c>并且您有系数。
Now expand B in base N+1 and you have the coefficients.
尝试解释：代数上，多项式为
Attempted explanation: Algebraically, the polynomial is
poly = p_0 + p_1 * x + p_2 * x^2 + ... + p_k * x^k
如果您有数字 b 并将其扩展为基数 n ，则得到
If you have a number b and expand it in base n, then you get
b = b_0 + b_1 * n + b_2 * n^2 + ...
其中每个 b_i 是唯一确定的， b_i< n 。
where each b_i is uniquely determined and b_i < n.
这篇关于使用最少的调用数打印多项式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！