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