魔方吧·中文魔方俱乐部

标题: 关于确定多项式的难题 [打印本页]

作者: yang_bigarm 时间: 2009-8-10 21:27:52 标题: 关于确定多项式的难题

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

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

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

作者: superacid 时间: 2009-8-10 21:35:00

多项式的次数不知道吗？

作者: Osullivan 时间: 2009-8-10 21:50:16

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

作者: yang_bigarm 时间: 2009-8-10 21:51:41

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

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

作者: 今夜微凉 时间: 2009-8-10 22:07:18

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

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

作者: lulijie 时间: 2009-8-11 09:52:46

只需要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 时间: 2009-8-11 10:06:18

通项是不是类似这样？如果是不话能否用下面的方法进行:
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项，求出最后一个最高次项的系数，再类推.
请楼主赐教

作者: 今夜微凉 时间: 2009-8-11 10:10:04

那取10不就好了嘛~~？

作者: superacid 时间: 2009-8-11 14:56:12

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

作者: lulijie 时间: 2009-8-11 21:08:42

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

作者: yang_bigarm 时间: 2009-8-12 00:09:09

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

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

作者: Cielo 时间: 2009-8-12 11:35:19

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

作者: yang_bigarm 时间: 2009-8-12 11:48:29

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

作者: ggglgq 时间: 2009-8-12 12:03:48

　　

实际上对于整系数多项式，令 a = π（任意一个“超越数”），便可以搞定 f(x) 。

注： 只需一次！ 而且不必限定  f(x) 的最高次幂 ！这时只需要“高精度计算机”，

便可以由  f(π) 的值唯一确定整系数多项式 f(x) 。

　　
　　
　　
　　

作者: lulijie 时间: 2009-8-12 12:51:21

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

作者: lulijie 时间: 2009-8-12 14:27:21

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

作者: yang_bigarm 时间: 2009-8-13 08:43:08

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

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

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

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)