|
|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail | |||||||
| Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
||||
 |
|
|
Опции темы | Поиск в этой теме |
21.04.2015, 15:24
|
#1 |
|
Форумчанин
Регистрация: 29.08.2010
Сообщений: 159
|
Динамическое программирование
Вот нашел такую ЗАДАЧУ не понимаю как здесь выведена формула:
Количество СМСок Раньше, когда у телефонов были кнопки, их клавиатуры выглядели примерно так:  Требуется подсчитать, сколько различных текстовых сообщений множно написать используя не более k нажатий на такой клавиатуре. Автор задачи привел решение: 1) Состояние: dp[m] — количество различных собщений, которые можно набрать за m нажатий. 2) Начальное состояние: dp[0] = 1. 3) Формула пересчёта: dp[m] = (dp[m - 1] + dp[m - 2] + dp[m - 3]) * 8 + dp[m - 4] * 2 4) Порядок: все три варианта можно использовать. 5) Ответ — это сумма всех состояний. Не понял откуда взялась такая не понятная формула пересчета, у нас есть 9 кнопок, певрая на которой всего 2 символа, со второй-по восьмую по три символа и девятая 4 символа, помогите разобраться |
|
|
|
21.04.2015, 15:30
|
#2 |
|
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
А это не факториалом считается?
I'm learning to live...
|
|
|
|
|
21.04.2015, 15:35
|
#3 | |
|
Форумчанин
Регистрация: 29.08.2010
Сообщений: 159
|
Цитата:
|
|
|
|
|
|
21.04.2015, 16:18
|
#4 | |||
|
Старожил
Регистрация: 20.04.2008
Сообщений: 5,526
|
Цитата:
Цитата:
Цитата:
итого 2 глубины 4
программа — запись алгоритма на языке понятном транслятору
|
|||
|
|
|
|
21.04.2015, 16:23
|
#5 |
|
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Чейта не уверен в правильности этой формулы..
Смотрите.. давайте оставим dp[m-1] Разберемся с остальными Чтобы получить вторую букву на любой кнопке, нужно было остановить два шага назад и начать жать на кнопку. Всего кол-во кнопок со 2-ой буквой - 8. Получаем 8*dp[m-2] (понятно?) Так же с 3-ей. С 4-ой аналогично Таких букв 2. Значит нужно остановиться 4 шага назад и начать жать на кнопку. Получится dp[m-4]*2.. С dp[m-1] момент не очень понятен.. Формула перестает действовать уже для dp[2] dp[1] = dp[0]*8 = 8 (пока правильно : ABDGJMPTW) dp[2] = (dp[1]+dp[0])*8 = 9*8 = 72.. А должно быть, вроде, 64.. |
|
|
|
|
21.04.2015, 16:41
|
#6 |
|
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Вообще наверно цифры тоже учитываются? Или нет?
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика 
|
|
|
|
|
21.04.2015, 16:57
|
#7 |
|
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Не..
Думаю, можно сказать, что пустота (под единичкой) тоже что-то делает.. Тогда все сойдется |
|
|
|
|
21.04.2015, 17:43
|
#8 | |
|
Форумчанин
Регистрация: 29.08.2010
Сообщений: 159
|
Цитата:
|
|
|
|
|
|
21.04.2015, 18:03
|
#9 |
|
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Если брать 1-ку, то все сходится
|
|
|
|
|
| Опции темы | Поиск в этой теме |
Похожие темы
|
||||
| Тема | Автор | Раздел | Ответов | Последнее сообщение |
| Динамическое программирование | DRGNforce | Паскаль, Turbo Pascal, PascalABC.NET | 4 | 01.03.2013 15:35 |
| Динамическое программирование | GoldSieg | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 12.04.2012 16:35 |
| Динамическое программирование | Daniya.ru | Общие вопросы .NET | 2 | 19.12.2010 11:40 |
| Динамическое программирование | joey_ramone | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 23.04.2010 13:51 |
| Динамическое программирование. | MAKEDON | Помощь студентам | 6 | 26.08.2009 14:10 |
