Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 
[Вернуться к задаче]   1
  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 членов и видна обсолютно простецкая формула...
     Я лично решил динамикой посложнее. Так и не понял, как без закономерностей объяснить эту простую формулу :)
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru