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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Как создавать информативные исключения? http://www.cyberforum.ru/cpp-beginners/thread1304523.html
как создавать информативные исключения??? нигде не могу найти внятного объяснения :( единственный способ какой я знаю throw std::exception("Exception!"), но он не информативен абсолютно, почему то...
C++ Змейка в консоли: неправильное поведение функции Всем привет! Пишу консольную змейку. Есть класс Snake и метод isSnake(), который работает некорректно (всегда возвращает true). Не могу разобраться, в чем ошибка, и как ее исправить? #include... http://www.cyberforum.ru/cpp-beginners/thread1304521.html
C++ Отсортировать методом прямого включения
Составить программу. Двумерный динамический массив размером NxM. Отсортировать методом прямого включения элементы стоящие от побочной диагонали.
Вывод первого слова из строки с помощью функции C++
#include <iostream> #include <cstdio> using namespace std; void slovo1(char *simv,char* result) { int i = 0; while( simv!=' ' || simv!=',' || simv!='.' && simv!=0)
C++ Определить, есть ли в строке или столбце повторяющиеся элементы http://www.cyberforum.ru/cpp-beginners/thread1304517.html
необходимо написать код, который определяет есть ли в отдельной строке или в отдельном столбце повторяющиеся элементы?
C++ Вывести таблицу значений функции Посмотрите пожалуйста програму, все работает, только в ответе во втором и третих столбиках должны быть числа со знаком+, может вы знаете в чем дело. #include <iostream.h> #include <math.h>... подробнее

Показать сообщение отдельно
Igor Fender
1 / 1 / 0
Регистрация: 09.07.2014
Сообщений: 167

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

18.11.2014, 22:41. Просмотров 386. Ответов 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
Изображения
 
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru