Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > Технологии > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 21.04.2015, 16:24   #1
Obey177
Форумчанин
 
Регистрация: 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 символа, помогите разобраться
Obey177 вне форума Ответить с цитированием
Старый 21.04.2015, 16:30   #2
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,840
По умолчанию

А это не факториалом считается?
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 21.04.2015, 16:35   #3
Obey177
Форумчанин
 
Регистрация: 29.08.2010
Сообщений: 159
По умолчанию

Цитата:
Сообщение от Stilet Посмотреть сообщение
А это не факториалом считается?
ну вообще кажется динамическим программированием будет легче
Obey177 вне форума Ответить с цитированием
Старый 21.04.2015, 17:18   #4
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 4,984
По умолчанию

Цитата:
певрая на которой всего 2 символа,
нет там символов (в соответствии с рисунком!!!)
Цитата:
со второй-по восьмую по три символа
итого восемь кнопок глубины 3
Цитата:
и девятая 4 символа,
А также седьмая (также по рисунку).
итого 2 глубины 4
программа — запись алгоритма на языке понятном транслятору
evg_m вне форума Ответить с цитированием
Старый 21.04.2015, 17:23   #5
Poma][a
Новичок
Джуниор
 
Регистрация: 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..
Poma][a вне форума Ответить с цитированием
Старый 21.04.2015, 17:41   #6
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 18,305
По умолчанию

Вообще наверно цифры тоже учитываются? Или нет?
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Старый 21.04.2015, 17:57   #7
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Не..
Думаю, можно сказать, что пустота (под единичкой) тоже что-то делает.. Тогда все сойдется
Poma][a вне форума Ответить с цитированием
Старый 21.04.2015, 18:43   #8
Obey177
Форумчанин
 
Регистрация: 29.08.2010
Сообщений: 159
По умолчанию

Цитата:
Сообщение от Poma][a Посмотреть сообщение
Не..
Думаю, можно сказать, что пустота (под единичкой) тоже что-то делает.. Тогда все сойдется
Думаю пустота под единичкой равна пробелу а это тоже символ) вот уже разбираю 3 задачу с каждым разом динамика более понятна, надо вот эту до конца разобрать
Obey177 вне форума Ответить с цитированием
Старый 21.04.2015, 19:03   #9
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Если брать 1-ку, то все сходится
Poma][a вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Динамическое программирование 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 12:40
Динамическое программирование joey_ramone Паскаль, Turbo Pascal, PascalABC.NET 0 23.04.2010 13:51
Динамическое программирование. MAKEDON Помощь студентам 6 26.08.2009 14:10