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