概念考察題：「多項式和係數」（關東行者）

「行者按：本文（連帶完整答案）首發於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賦什麼值才能得出最後的答案呢？思考留給讀者。

（完）