Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

18.11.2014, 22:41. Просмотров 420. Ответов 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/

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

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

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

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

Выбор кафедры в дальнейшей жизни: прикладное программирование VS системное программирование - C++
Сразу извиняюсь что очень не по теме но всё же лучшего форума для этого вопроса я не нашел. Итак я вступаю во взрослую жизнь и давно...

В массиве записаны оценки, найти количество пятерок, количество четверок, количество троек и количество двоек - C++
В массиве записаны оценки по иностранному языку каждого из 22 учеников класса. Определить количество пятерок, количество четверок,...

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

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

C++ (Qt)
1
if(dp[m] != -1) return dp[m];
1
OnePiece
33 / 33 / 22
Регистрация: 22.02.2014
Сообщений: 107
18.11.2014, 22:49 #3
Решение этой задачи лежит в основах дискретной математики. Вам стоит поискать ответ в теории ДМ.
0
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 уже падает
0
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
18.11.2014, 22:57 #5
Igor Fender, может переполняется?
0
Igor Fender
1 / 1 / 0
Регистрация: 09.07.2014
Сообщений: 167
18.11.2014, 23:00  [ТС] #6
Скорее всего, число невероятных размеров))

Добавлено через 2 минуты
Просто в нете столько всего на ДМ, я тону в тонне информации. И большинство тем сложны для начала
0
18.11.2014, 23:00
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.11.2014, 23:00
Привет! Вот еще темы с ответами:

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

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

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

Динаммическое программирование: найдите количество способов представления заданного числа N в соответствии с условием. - Pascal ABC
Любое натуральное число можно представить в виде суммы натуральных слагаемых, каждое из которых является степенью числа 2. Суммы,...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

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