使用最少的调用数打印多项式 [英] Print a polynomial using minimum number of calls

问题描述

我不断遇到这些艰苦的面试问题。

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.

这篇关于使用最少的调用数打印多项式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！