| 21 Олеринский Ян Дмитриевич, 24 июля 2019 г. 14:21:48 |
| Егор Степанов, формулу можно вывести для всего, у чего есть рекуррентное соотношение.
|
|
|
| 22 Винк В В, 16 мая 2018 г. 13:38:08 |
| Простая формула и объясняется очень просто. Представим, что Вова стоит на первой ступени и перед ним ещё N-1 ступеней. Вова может либо шагать на соседнюю ступень либо прыгать через одну как вверх так и вниз. Задача у Вовы побывать на каждой ступени ровно 1 раз. Наша задача найти количество всех его вариантов. Если Вова делает шаг вперёд, то ему остаётся преодолеть на 1 ступень меньше, то есть F(n-1) вариантов. Если делает прыжок вперёд, то у него теперь 2 пути: 1) сделать шаг назад и прыжок вперёд, таким образом он преодолеет 3 ступени и ему останется F(n-3) вариантов; 2) прыгать до конца и вернуться назад прыжками, то есть 1 вариант. Получаем простую формулу
|
|
|
| 23 Алан Тьюринг, 12 мая 2018 г. 13:00:17 |
| Хорошая задачка, однако задача "Магазин", по-моему, гораздо тяжелее.
|
|
|
| 24 Егор Степанов СПбГУ, 17 декабря 2016 г. 14:20:59 |
Для чисел Фибоначчи есть формула Бине, вычисляющая n-ый элемент за O(1).
Формула выводится через характеристическое уравнение рекуррентного соотношения.
Можно ли такую формулу вывести и для этой последовательности ?
|
|
|
| 25 Ганжа Владислав [X-FIGHTers tEAm], 09 августа 2011 г. 15:40:27 |
"Ну я не знаю, по-моему она только выглядит легко, а додуматься до формулы не так уж и легко."
согласен!большая часть тех хто додумался до формулы записали несколько первых членов и смотрели што нужно добавить к a[i-1] штоб вышло a[i] а не выводили её
|
|
|
| 26 Нурумов Андрей, 15 августа 2010 г. 12:41:37 |
очень легкая динамика!!!!!!!!
Ну я не знаю, по-моему она только выглядит легко, а додуматься до формулы не так уж и легко.
|
|
|
| 27 Рузибоев Содик Абдугаффарович, 19 декабря 2009 г. 9:27:59 |
30%-40% хватило бы....
Ну не знаю, до формулы то сами додумались? У меня лично, более сложная динамика получилась.
|
|
|
| 28 Мехрдоди Одил (ТРГИ), 21 августа 2009 г. 2:30:49 |
2 1
3 2
4 4
5 6
6 9
7 14
8 21
9 31
;)!
|
|
|
| 29 Павлова Алёна, 21 июня 2009 г. 21:30:42 |
это особая, уличная магия...
=)
|
|
|
| 30 Корчажников Фёдор Васильевич, 21 июня 2009 г. 19:51:18 |
| мда...формулка конечно магическая какая-то. интересно бы было послушать доказательство)
|
|
|
| 31 Набиев Умед ТРГИ, 14 мая 2009 г. 20:10:18 |
а почему вы этой задаче дали 55% ?? любой кто хотябы раз слыхал о динамике может с 1 попытки решить эту задачу
Да неужели? По-вашему на этом сайте только 95 человек слышало о динамике?
|
|
|
| 32 Ладик Артём, 06 октября 2008 г. 23:10:18 |
Динамика проще некуда. Дастаточно написать рекурсивный алгоритм и посмотреть первых 20 членов и видна обсолютно простецкая формула...
Я лично решил динамикой посложнее. Так и не понял, как без закономерностей объяснить эту простую формулу :)
|
|
|
