Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Igor Fender
1 / 1 / 0
Регистрация: 09.07.2014
Сообщений: 167
#1

Спортивное программирование: Количество СМСок - C++

18.11.2014, 22:41. Просмотров 377. Ответов 5
Метки нет (Все метки)

Нашел интересную задачу по динамическому программированию. Вот ее условие:
Раньше, когда у телефонов были кнопки, их клавиатуры выглядели примерно так: (прикрепил фото).
Требуется подсчитать, сколько различных текстовых сообщений множно написать используя не более k нажатий на такой клавиатуре.


Программа вроде работает корректно:

C++
1
2
3
4
5
6
7
8
9
10
11
int F(int m)
{
    if(m == 0)return 1;
    else if (m < 0) return 0;
    else return (F(m - 1) + F(m - 2) + F(m - 3)) * 8 + F(m - 4) * 2;
}
 
int main()
{
    std::cout<<F(2);
}
Написал я ее по данному алгоритму:
dp[m] = (dp[m - 1] + dp[m - 2] + dp[m - 3]) * 8 + dp[m - 4] * 2

Объясняется это так:
Формулы пересчёта: есть по восемь букв, для написания которых нужно одно, два и три нажатия, а так же две буквы требующие 4 нажатия.

Прочитал, что можно заставить несколько вариантов формул:
1) Прямой порядок
2) Обратный порядок
3) Ленивая динамика

Вот источник: http://habrahabr.ru/post/191498/

Плохо понял, чем отличаются все эти способы и теория по созданию этих формул. То есть как мне научится перебирать все варианты по заданной задаче и создавать формулы. Не могу найти доходчивую теорию.
Просто сама идея изучения алгоритмов мне очень понравилась, люблю короткие алгоритмы. Но как научится их делать?
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2014, 22:41     Спортивное программирование: Количество СМСок
Посмотрите здесь:

Входные данные и спортивное программирование - C++
Привет всем! Дело в том, что когда учавствуешь в соревнованиях на codeforces, informatics или просто решаешь задачи, всегда присутствуют...

Спортивное программирование: подскажите удобный сайт - C++
Всем Доброго времени суток!:) Уважаемые программисты с опытом,нужна помощь новичку. Увлёкся спортивным программированием,столкнулся с...

Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) - C++
Написать программу, которая использует метод динамического программирования. Даны N целых чисел X1,X2, . . . ,XN (1 &lt;= N &lt;= 10000, 1 &lt;=...

Пользователь вводит строку. Определить количество букв (рус eng), количество цифр и количество остальных - C++
в чем проблема не пойму работает на английских буквах на цифрах и остальные символы вроде считает а вот русские не хочет их забивает как...

Определить количество выигрышей, количество проигрышей и количество ничьих данной команды - C++
Недавно начал изучать язык С++ и уже застопорился. Помогите пожалуйста решить. 2.В массиве записаны результаты N игр футбольной...

Спортивное программирование - развивает мышление программиста или бесполезное занятие?
Тема не новая, но хотелось бы узнать мнение. Дело в том что учу Паскаль, но хочу не просто взять и вызубрить язык, но и мышление иметь. Вот...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
18.11.2014, 22:47     Спортивное программирование: Количество СМСок #2
ты написал перебор а не динамику. чтобы перебор превратился в динамику, надо сохранять результаты(перед тем как что-то считать надо проверить, а не считал ли я это до этого). В функции надо в самом верху нписать что-то типа

C++ (Qt)
1
if(dp[m] != -1) return dp[m];
OnePiece
33 / 33 / 22
Регистрация: 22.02.2014
Сообщений: 107
18.11.2014, 22:49     Спортивное программирование: Количество СМСок #3
Решение этой задачи лежит в основах дискретной математики. Вам стоит поискать ответ в теории ДМ.
Igor Fender
1 / 1 / 0
Регистрация: 09.07.2014
Сообщений: 167
18.11.2014, 22:55  [ТС]     Спортивное программирование: Количество СМСок #4
А с чего конкретно начать??

Добавлено через 4 минуты
SlavaSSU,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dp[30];
int F(int m)
{
    if(m == 0)return 1;
    else if (m < 0) return 0;
    else  {
            if(dp[m] != -1) return dp[m];
             dp[m] = (F(m - 1) + F(m - 2) + F(m - 3)) * 8 + F(m - 4) * 2;
             return dp[m];
          }
}
 
int main()
{
    for(int i=0; i<30; i++) dp[i] = -1;
    std::cout<<F(2);
}
Ну вот так вроде, но на 20 уже падает
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
18.11.2014, 22:57     Спортивное программирование: Количество СМСок #5
Igor Fender, может переполняется?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.11.2014, 23:00     Спортивное программирование: Количество СМСок
Еще ссылки по теме:

устройство для отправки смсок - Микроконтроллеры
Что имеется: сим-карты разных операторов . количество не менее 10 Что нужно: устройство, в которое можно было вставить, если не все...

Как написать скрипт посылки смсок? - PHP
Расскажите поподробней, как написать скрипт посылки смсок? Что для этого нужно? (Только пусть рассказывают тот, кто это делал:)

Спортивное питание: за и против. - Спорт
У многих начинающих спортсменов сложилось предвзятое мнение к спортивному питанию. Плюсы и минусы компонентов спортивного питания. ...

Holywar : бумажные книги vs электронные.Спортивное чтение на скорость?
бумажная, так как электронную копируют с неё

Программа "Спортивное табло" - Системный софт
Суть проги - ноутбук с запущенной программой подключается к телевизору. Программа должна отображать на экране телевизора две фамилии, часы...

Динамическое программирование: найти количество N-значных трипростых чисел - Free Pascal
Будем называть натуральное число трипростым, если в нем любые подряд идущие 3 цифры образуют трехзначное простое число. Требуется найти...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Igor Fender
1 / 1 / 0
Регистрация: 09.07.2014
Сообщений: 167
18.11.2014, 23:00  [ТС]     Спортивное программирование: Количество СМСок #6
Скорее всего, число невероятных размеров))

Добавлено через 2 минуты
Просто в нете столько всего на ДМ, я тону в тонне информации. И большинство тем сложны для начала
Yandex
Объявления
18.11.2014, 23:00     Спортивное программирование: Количество СМСок
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru