ZedStudio

本博客為zedstudio.org所有,作品,除非標明,皆屬原創。有各類隨筆,有獨家小說,間或詩詞歌賦;側重海外見聞,溝通中西文化,並穿插中土回憶。
正文

概念考察題:「多項式和系數」(關東行者)

(2024-01-19 21:52:26) 下一个

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

(完)

 

[ 打印 ]
阅读 ()评论 (0)
评论
目前还没有任何评论
登录后才可评论.