Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
0 / 0 / 0
Регистрация: 10.10.2015
Сообщений: 2
1

Основы динамического программирования

10.10.2015, 17:37. Просмотров 805. Ответов 3
Метки нет (Все метки)

Добрый день! Я начал изучать динамическое программирование, но что-то не особо получается. В общем почитав пару статей все стало ещё хуже. И мне тут же дали домашку.
Задача: Программа должна вывести, сколькими способами можно считать данное число(101010101) кодовыми последовательностями(a=01,b=10,c=101,d=1010). На вход подается число, а на выходе кол-во способов его считывания. ответ будет 7.
Но как динамическое программирование можно тут применить? Может кто подскажет. В идеале кусочек кода бы для наглядности.
Заранее спасибо!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.10.2015, 17:37
Ответы с готовыми решениями:

Основы программирования язык С
Здравствуйте, у меня такая проблема, необходимо писать программы в turbo c запускаю через...

Основы алгоритмизации и программирования тест сделайте пожалуйста
Вопрос 1 (10454) Укажите, какое из нижеследующих утверждений ложное. 1: Комментарии при...

Задача о рюкзаке методом динамического программирования
Здравствуйте, помогите, пожалуйста, реализовать до конца программу. Входные данные должны быть...

Игра Ним методом динамического программирования
добрый день помогите решить задачу методом динамического программирования. Игра Ним с одной кучей...

3
267 / 170 / 40
Регистрация: 25.08.2014
Сообщений: 1,087
Записей в блоге: 1
10.10.2015, 17:45 2
Разбей число, посчитай сколькими способами можно считать каждое в отдельности, сложи. Разбивай до длины минимального слова (кодовой последовательности). И так для каждой позиции. Это вроде рекурсия должна получиться.
0
4453 / 2072 / 263
Регистрация: 01.03.2013
Сообщений: 5,508
Записей в блоге: 22
11.10.2015, 03:48 3
Скрепя сердце позволил себе один (непринципиальный) фор Но мутабельные экспоненциально-рекурсивные лямбды удалось накостылить далеко не сразу.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
 
int main() {
    const char a[]="01", b[]="10", c[]="101", d[]="1010", s[]="101010101";
    auto suff = [](const char *a, const char *b, const char *p, const auto& la) -> const char* {
        return *a ? *a==*b ? la(a+1,b+1,p,la) : p : b;};
    
    auto f_rec = [&](const char *beg, const auto& la) -> int {
        auto go = [suff,beg,la](const char *a) -> int {
            const char *end = suff(a,beg,beg,suff); return beg==end ? 0 : la(end, la);};
        return *beg ? go(a)+go(b)+go(c)+go(d) : 1;};
    
    std::cout<<"recursion without memoization: "<<f_rec(s, f_rec)<<'\n';
   
    const int dp_size=1000; int dp[dp_size]; for(int i=0; i<dp_size; ++i) dp[i]=-1;   
    auto f_rec_dp = [&](const char *beg, const auto& la) -> int {
        auto go = [suff,beg,la](const char *a) -> int {
            const char *end = suff(a,beg,beg,suff); return beg==end ? 0 : la(end, la);};
        
        int i = beg-s; 
        auto memo = [&]() mutable -> int {
            if (dp[i]<0) dp[i] = go(a)+go(b)+go(c)+go(d); return dp[i];};
 
        return *beg ? memo() : 1;};
    
    std::cout<<"recursion with memoization = dp: "<<f_rec_dp(s, f_rec_dp)<<'\n';
}
0
0 / 0 / 0
Регистрация: 10.10.2015
Сообщений: 2
14.10.2015, 16:42  [ТС] 4
Через рекурсию я решил. Но как я понял если использовать динам.прог. то тогда как-то используется предыдущий ответ.

Добавлено через 7 минут
_Ivana, тяжеловато для восприятия. Может в лс объяснишь?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.10.2015, 16:42

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Задача коммивояжера методом динамического программирования
Помогите пожалуйста переделать коммивояжера методом динамического программирования. Пусть n - это...

Как считать а степени н применяя принцип динамического программирования?
Как считать а^n применяя принцип динамического программирования?

Как называется движение программирования или теория программы считывающая др. язык программирования
Не знал, как по другому задать вопрос, и также назвать тему, но буду краток: Допустим я хочу...

Основы 3D-программирования?
Всем доброго времени суток ! В последнее время задался вопросом, а для чего нужны знания основ...


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

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

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