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

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

Восстановить пароль Регистрация
 
Igor Fender
1 / 1 / 0
Регистрация: 09.07.2014
Сообщений: 167
18.11.2014, 22:41     Спортивное программирование: Количество СМСок #1
Нашел интересную задачу по динамическому программированию. Вот ее условие:
Раньше, когда у телефонов были кнопки, их клавиатуры выглядели примерно так: (прикрепил фото).
Требуется подсчитать, сколько различных текстовых сообщений множно написать используя не более 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++ количество букв в слове, количество предложений, самое длинное слово в предложении
C++ Определить количество выигрышей, количество проигрышей и количество ничьих данной команды
В массиве записаны результаты N игр футбольной команды. Определить количество выигрышей, количество проигрышей и количество ничьих данной команды. C++
C++ Найти через индекс количество отрицательных и количество положительных элементов массива
C++ Подсчитать количество всех строк, а потом - количество слов в каждой строке
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
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
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
18.11.2014, 22:57     Спортивное программирование: Количество СМСок #5
Igor Fender, может переполняется?
Igor Fender
1 / 1 / 0
Регистрация: 09.07.2014
Сообщений: 167
18.11.2014, 23:00  [ТС]     Спортивное программирование: Количество СМСок #6
Скорее всего, число невероятных размеров))

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

Текущее время: 23:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru