1 / 1 / 0
Регистрация: 09.07.2014
Сообщений: 167
1

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

18.11.2014, 22:41. Показов 1816. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.11.2014, 22:41
Ответы с готовыми решениями:

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

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

Спортивное программирование
Нужно прочитать большой набор строк в массив. Использовал - string nums =...

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

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

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

Добавлено через 2 минуты
Просто в нете столько всего на ДМ, я тону в тонне информации. И большинство тем сложны для начала
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.11.2014, 23:00
Помогаю со студенческими работами здесь

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

Как написать скрипт посылки смсок?
Расскажите поподробней, как написать скрипт посылки смсок? Что для этого нужно? (Только пусть...

Спортивное програмирование
Здравствуйте, Кто участвовал в олимпидах по програмированию, можете поделится своим опытом и тем...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru