?

Log in

No account? Create an account
Ни о какой безапелляционности в моих высказываниях не может быть и речи! [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка с решением (математическое) [дек. 22, 2011|12:35 am]
Anatoly Vorobey
Задачка такая: продолжить последовательность чисел 1,2,4,8,16...

Решение у нее немного нетривиальное, хотя в принципе ничего сложного нет. Я его дам под катом.


Понятно, что напрашивается предположение, что это значения какой-то не очень сложной функции, и если мы поймем, какой, то легко будет продолжить последовательность. Если мы обозначим эту функцию f, то можно предположить, что нам дали значения f(1), f(2), f(3), f(4), f(5), и если мы по ним сможем понять, что такое f(x), то следующее число будет просто f(6).

Самые логичные кандидаты на f(x), благодаря своей простоте - несомненно, многочлены. Поскольку у нас есть пять значений, можно надеяться, что есть единственный многочлен степени 4, который отвечает нашим условиям. И действительно, с помощью простых методов линейной алгебры (опускаю эту часть), легко видеть, что это многочлен

f(x) = x4/24 - x3/4 + 23x2/24 - 3x/4 + 1

Легко проверить, что его значения для x=1,2,3,4,5 как раз равны 1,2,4,8,16. А если подставить x=6, получим f(x)=31. Очевидно, это и есть правильный ответ.


Итак, правильный ответ - 31. Конечно, в каком-то смысле правильного ответа нет, потому что есть бесконечно много разных функций, продолжающих эту последовательность по-разному. Но вполне вероятно, что все они сложнее, чем найденное нами простое и элементарное решение.

источник: Carl E. Linderholm, Mathematics Made Difficult.
СсылкаОтветить

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: amigofriend
2011-12-21 10:42 pm
Десять лет как жизни нет. Всё Колмогоровы, Линдерхольмы, Фихтенгольцы, всякие там Сканави.
(Ответить) (Thread)
[User Picture]From: cema
2011-12-21 11:46 pm
+1
(Ответить) (Parent) (Thread) (Развернуть)
(Удалённый комментарий)
[User Picture]From: amigofriend
2011-12-21 10:43 pm
Вы прочитали название книги?
(Ответить) (Parent) (Thread)
[User Picture]From: tandem_bike
2011-12-21 10:43 pm
однако шутник Карл!
(Ответить) (Thread)
[User Picture]From: amigofriend
2011-12-21 10:55 pm
как у нас говорили - шалунишка.
(Ответить) (Parent) (Thread)
[User Picture]From: dimrub
2011-12-21 10:45 pm
Типичный overfit, кстати :).
(Ответить) (Thread)
[User Picture]From: avva
2011-12-21 10:51 pm
:)
(Ответить) (Parent) (Thread)
From: (Anonymous)
2011-12-21 10:46 pm
На мой взглад, утверждение "Самые логичные кандидаты на f(x), благодаря своей простоте - несомненно, многочлены" весьма спорно.
(Ответить) (Thread)
[User Picture]From: cema
2011-12-21 11:50 pm
Спорно, но логично!
(Ответить) (Parent) (Thread)
From: captain_tylor
2011-12-21 10:46 pm
Правильный ответ - 32
Если считать простейший ответ по количеству символов в формуле.
(Ответить) (Thread)
From: oblomov_jerusal
2011-12-22 04:46 am
Это если у вас в языке есть символ экспоненты, а если нету?
(Ответить) (Parent) (Thread)
[User Picture]From: homotub
2011-12-21 10:55 pm
это прекрасно)))
(Ответить) (Thread)
[User Picture]From: trurle
2011-12-21 11:02 pm
Удивительно с какой точностью полиномиальная аппроксимация воспроизводит экспоненту.
(Ответить) (Thread)
[User Picture]From: kblcbka
2011-12-21 11:23 pm
:)))
(Ответить) (Parent) (Thread)
[User Picture]From: grur
2011-12-21 11:07 pm
Чуть менее нетривиальная Хофштадтеровская последовательность: 0, 1, 2, ... ?

(правильный ответ: 720 факториал)
(Ответить) (Thread)
From: (Anonymous)
2011-12-22 11:58 am
Лол что? А функция какая?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: olkab
2011-12-21 11:14 pm
Ах как хорошо!
(Ответить) (Thread)
[User Picture]From: avzel
2011-12-21 11:15 pm
Ну да. А разве бывают другие решения? :)
(Ответить) (Thread)
[User Picture]From: xxxxx
2011-12-22 04:28 pm
Вообще-то да. Тут этот многочлен вылезает как рояль из кустов. Пропедевтически правильнее было бы решение с разностями.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: bugabuga
2011-12-22 12:00 am
Напоминает систему предложения маршрута от Амтрака :)
Где при попытке съездить из Остина в Лос Анжелес предлагается не Остин-Сан Антонио-Лос Анжелес, а упорно рекоммендуется маршрут через штат Иллиноис или через Монтану :)
(Ответить) (Thread)
[User Picture]From: kcmamu
2011-12-22 12:18 am
В таких задачах более естественным представляется вычислять не отдельный элемент последовательности, а все подряд по очереди; при этом нам оказывается доступен набор ранее вычисленных предыдущих значений. В этом смысле вычислительная схема f(t)=2f(t-1) проще многочлена с кучей коэффициентов: для вычисления очередного значения нужно выполнить всего одно арифметическое действие.
(Ответить) (Thread)
[User Picture]From: vaniusha
2011-12-22 08:44 am
+1. Задача сформулирована некорректоно. "ПРодолжить последовательность" <> "отыскать функцию от аргумента, гдле аргументом служит порядковый номер значения функции в приведенной последовательности".
Простейший ответ на вопрос "продолжить последовательрность" - это 32. который получается умножением предыдущего члена последовательности на 2.
поскольку это работает для всех приведенных членов последовательности то это и является именно ПРОСТЕЙШИМ решением. притом - корректным :)
(Ответить) (Parent) (Thread)
[User Picture]From: vdinets
2011-12-22 12:37 am
очаровательно :-)
(Ответить) (Thread)
Страница 1 из 2
<<[1] [2] >>