关于确定多项式的难题

yang_bigarm

两个希腊人alpha和zeta在玩一个游戏，其中zeta心中事先想好了一个多项式f(x)，
alpha每次说出一个数字a，zeta就把这个数字代入多项式里，报出f(a)的值。

请问alpha最少提问几次，就可以完全确定这个多项式。

注意：古希腊的时候人们通常研究的是系数为正整数的多项式。

superacid

多项式的次数不知道吗？

Osullivan

这次数不知道，貌似无法确定吧～～～

yang_bigarm

原帖由 superacid 于 2009-8-10 21:35 发表
多项式的次数不知道吗？

是的，不知道次数，想一想如何确定？

今夜微凉

我只知道，给0，则得出常数项~原来还有条件~系数是正整数~那可能好办一些~

[ 本帖最后由 今夜微凉 于 2009-8-10 22:09 编辑 ]

lulijie

只需要1次就可确定这个整系数多项式。
假设所有系数中最大的数为n位数，那么可以用10^n或更大的数来检验即可。
比如  12x^4+98x^2+56x+3
可取100，值为1200985603
将这个值每两位分隔得 12，00，98，56，03
      多项式就是 12x^4+98x^2+56x+3
如果最大的系数不清楚多大，可以取尽可能大的数就行，比如取10^n，n取尽量大就行。

东莞的8

通项是不是类似这样？如果是不话能否用下面的方法进行:
f(x)=a+bx+cx^2+dx^3+~~~~~~
x取0的话可以得出常数项
再x分别取1,2,3~~~为1时则f(x)=a+b+c~~~  设等于K，这样的话最多K次就可以知道项数。然后再取x为2时则f(x)=a+2b+4c~~~ 最多K次，可以约去前面的K-1项，求出最后一个最高次项的系数，再类推.
请楼主赐教

今夜微凉

那取10不就好了嘛~~？

superacid

你在不知道此数的情况下只有最佳策略，没有最少次数。

lulijie

如果非得认为整系数最大值可以无限大，最高次幂可以选的无限大，那么讨论本题就没有意义了。
我估计楼主的本意就是让你取一个无限大的数，就可最少一次就解决问题。
--------------------------------------------------------------------------
如果要让题目出的精确些，可以改成这样：
两个希腊人alpha和zeta在玩一个游戏，其中zeta心中事先想好了一个整系数多项式f(x)，系数的最大值为m，
alpha每次说出一个数字a，zeta就把这个数字代入多项式里，报出f(a)的值。
请问alpha最少提问几次，就可以完全确定这个多项式。
-------------------------------------
答案是最少提问一次：任意选一个比m大的数，根据f(m)的值就可确定这个整系数多项式。