задачка, математическое

[avva]

Предположим, я загадал многочлен F(x) с целыми неотрицательными коэффициентами. Вы можете сказать мне любое рациональное число a, а я вам в ответ скажу F(a). Сколько таких попыток нужно вам, чтобы гарантированно отгадать многочлен?

Update: в комментах есть правильные ответы.

Comments

[(Anonymous)]

Пожалуй, от нескольких до бесконечности.

[valery-pavlov.livejournal.com]

А членов сколько?

[avva.livejournal.com]

Этого я не говорю.

[komprendre.livejournal.com]

две. сначала узнаем сумму коеффицентов k=F(1), а потом просим посчитать F(1/k).

[dmarck.livejournal.com]

Что-то подсказывает, что n+1, при этом две первые очевидны: ноль даёт свободный член, единица даёт сумму коэффициентов.

"На этом мысль останавливается" © ;-P

[valery-pavlov.livejournal.com]

То есть имеется в виду решение в общем виде? В противном случае попыток может быть сколько угодно.

[altal.livejournal.com]

За два можно.
Первый вопрос про F(1).
Затем подбираем n, чтобы 10^n>F(1) и спрашиваем 1/10^n.

В ответе получим длинную десятичную дробь, каждые n знаков которой будут записывать по очереди коэффициенты многочлена.

[i_eron]

Замечательно!

[avva.livejournal.com]

Предположим, сумма коэффициентов равна 1.

Скучно.

[toluca.livejournal.com]

Если
- с целыми неотрицательными коэффициентами
- сумма коэффициентов равна 1

то ненулевой коэффициент один, и равен 1.

[kukutz.livejournal.com]

7 и 1.469804...

[barabash.livejournal.com]

actually, F(F(1) + 1)

Re: Скучно.

[avva.livejournal.com]

Да, но все равно неясно, какой многочлен: 1, x, x^2...

[avva.livejournal.com]

Ага, это работает.

Re: Скучно.

[kukutz.livejournal.com]

И чему равна степень x при этом коэффициенте?

Скучно^2

[toluca.livejournal.com]

Ну вторым-то вопросом F(2) выбор из 1, x, x^2 производится...

[avva.livejournal.com]

Ага, так можно.

[toluca.livejournal.com]

Т.е. тоже 2...

[akalenuk.livejournal.com]

n+2?

[dimrub.livejournal.com]

I seem to remember the required number of trials is equal to the degree of the polynom.

[dimrub.livejournal.com]

Oops... Sorry, missed the part about integer coefficients.

[imfromjasenevo.livejournal.com]

подозреваю, что одна если туда например a=пи засунуть.

[toluca.livejournal.com]

Пи каплю НЕ рациональное.

[imfromjasenevo.livejournal.com]

прочитал не внимательно условие

[barabash.livejournal.com]

Более оптимально было бы каким-то образом оценить максимальный коэффициент многочлена. Предположим, загадывающий должен записать многочлен на бумажке в десятичном виде. Мы знаем, что он не может писать больше десяти цифр в секунду. Тогда, зная верхнюю оценку количества цифр во всех коэффициентах, скажем N, попросить F(N). :)