概念考察題：「多項式和系數」

「行者按：本文（連帶完整答案）首發於zedstudio.org：『多項式和系數』」

多項式和系數

關東行者

有好事者傳了一道題，得空看了一下，考察概念，不錯，推薦給感興趣的朋友：

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

友情提示：

關於x的一元（single indeterminate）多項式（Polynomial）p（x），總是可以寫成：

a[n]*x^n + a[n-1]*x^(n-1) + … + a[1]*x^1 + a[0]*x^0   （1）

或寫成：

sum[i=0->n](a[i]*x^i）（2）

這裡的[]表示下標，^標示指數，*就是乘法運算，sum是求和運算；作為係數（coefficient）的a[i]是常數（constant），根據原題，它們都是正整數（1，2，3，...）。

一個數是可以用不同的進位系統（位值計數）來表達的，我們日常使用的數多數是十進制數（也有十二進制，六十進制和其它進制的），其基數是10（即可以用0到9這十個數來表達所有的數值，逢十進一）；在計算機中使用的多是二進制（八進制，十六進制），其基數是2（只能用0和1，逢二進一）。

數在位值計數系統中的表達a[n]a[n-1]...a[1]a[0]時（位置從0到n），如果基數是正整數b，則表達成：

a[n]*b^n + a[n-1]*b^(n-1) + … + a[1]*b^1 + a[0]*b^0 （3）

把（3）中的b替換成x，就是前面提到的（1），只是注意這裡的係數a[i] (i=0..n)都小於基數x。

一個具體的例子是十進制的234這個數（n＝2，位置從0到2分別對應：個位，十位和百位），寫成多項式則是：

234 = 2*10^2 + 3*10^1 + 4*10^0

十進制的234按位值計數寫成二進制會是什麼樣子呢？

11101010 ＝ 1*2^7 + 1*2^6 + 1*2^5 + 0*2^4 + 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0

十進制的234按位值計數寫成八進制會是什麼樣子呢？

352 ＝ 3*8^2 + 5*8^1 + 2*8^0

回到原來的問題，當x賦值1時，（1）給出p(1)：

p(1) ＝ a[n] + a[n-1] + … + a[1] + a[0]

正整數a[i]的和p(1) 還正整數，而且一定大於a[i] (i=0..n)中的任何一個（如果係數是包括零的自然數，p(1)則不一定大於任何一個係數，在下面的取值時就要用p(1)＋1。大家可以想想為什麼。）。

下面要給x賦什麼值才能得出最後的答案呢？思考留給讀者。

（完）