关于确定多项式的难题

yang_bigarm

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

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

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

yang_bigarm

题目的“注意”那个地方不是写得很清楚了吗？系数为正整数的多项式。

如果没有注意的这个条件，用拉格朗日插值多项式来做。

[ 本帖最后由 yang_bigarm 于 2009-8-13 08:46 编辑 ]

lulijie

突然想到   第一次取1，知道了f(1)的值，还是不知道最大系数的绝对值。
这样的话，假设你能通过n次成功获得这个多项式。那么可以证明你无法通过n次成功获得这个多项式。
假设这n次你的取值分别是a1,a2,a3......an
那么我的多项式如果是 (x-a1)(x-a2)(x-a3)......(x-an)(......)
那么你的n次取值给出的结果都等于0，所以无法获得系数绝对值的最大值。
所以你可能无论多少次也无法成功获得这个多项式的准确表达式。
------------------------------------------------------
所以我觉得楼主的题目要成立的话，至少需要增加一个条件：
     事先给定所有系数的绝对值的最大值。      那么只要1次就行。
或者
     所有的系数都是非负整数。                       那么需要2次才能完成任务。

lulijie

哈哈，先取1，然后取f(1)或比f(1)大的任何数，两次必能成功。

ggglgq

　　
  
    实际上对于整系数多项式，令 a = π（任意一个“超越数”），便可以搞定 f(x) 。
  
注： 只需一次！ 而且 不必限定  f(x) 的 最高次幂 ！ 这时只需要“高精度计算机”，
  
便可以由  f(π) 的值 唯一 确定 整系数多项式 f(x) 。
  
　　
　　
　　
　　

yang_bigarm

cielo和lulijie两人的想法合在一起就是正确答案啦。

Cielo

呵呵既然这样那么第一次令 a=1 就可以得出系数的最大值了

yang_bigarm

lulijie的答案距离正确答案还查一点距离，显然不会是一次提问就能确定的吧。

不要老改我的题目，我说zeta想好了一个多项式，那么我们可以认为他已经事先写在纸上了。

lulijie

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

superacid

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