首页 » 算法 » 【转】一个令人拍案叫绝的算法

【转】一个令人拍案叫绝的算法

 

在Matrix67的blog 上看的一道题:

有一个黑匣子,黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项,但已知所有的系数都是正整数。每一次,你可以给黑匣子输入一个整数,黑匣子将返回把这个整数代入多项式后的值。那么,最少需要多少次, 我们可以得到这个多项式每项的系数呢?

答案是两次。

第一次,输入 1 ,于是便得到整个多项式的所有系数之和。记作 S 。

第二次,输入 S + 1 ,于是黑匣子返回的是

a_n * (S + 1)^n + a_{n-1} * (S + 1)^{n-1} + ... + a_1 * (S + 1) + a_0 的值。

我们要得到 {a_n,...,a_0},只需要把这个值换成 S+1 进制, 然后依次读出每一位上的数。

P.S. 第一次得到S是为了保证对于任意系数a_i, a_i<=S

---------------------------------------------------------------------------------------

其实最大系数不超过N的多项式,本来就是N进制的本质

作者:Liang Miya
链接:https://www.zhihu.com/question/27547892/answer/131272696
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

原文链接:【转】一个令人拍案叫绝的算法,转载请注明来源!

0