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

Динамическое программирование - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
mirror2u
0 / 0 / 0
Регистрация: 12.04.2012
Сообщений: 20
11.09.2012, 19:47     Динамическое программирование #1
Мячик прыгает по лестнице, состоящей из N ступенек, строго сверху вниз. За один прыжок он может отпрыгнуть на не более M ступенек. Необходимо посчитать, сколькими способами он может спуститься без вывода самих вариантов прыжков.
Даны два числа - количество ступенек в лестнице и максимальное количество ступенек, на которое может отпрыгнуть мячик. Все получаемые значения положительные и не превосходят 2147483647.

Помогите пожалуйста с решением.

Делал так :
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <stdio.h>
#include <fstream>
 
using namespace std;
 
int main()
{
    int M;
    int n;
    int g=0;
    cout<<"input n :";cin>>n;
    cout<<"input M :";cin>>M;
    if(M==1) {g=1;}
    else
    for(int i=1;i<=M;i++)
    {
        g+=n-i;
    }
    cout<<g<<endl;
    return 0;
}
как я понимаю нужно использовать вот такую функцию подсчёта: k[n]=k[n-1]+k[n-2]+k[n-3]+k[n-m],
где n - количество ступенек, а m - максимальное количество ступенек, на которое может отпрыгнуть мячик. Но при значениях n=7, а m=3 моя программа выдаст 15 вариантов, а на самом деле их 44.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.09.2012, 19:47     Динамическое программирование
Посмотрите здесь:

C++ Динамическое программирование
C++ динамическое программирование
Динамическое программирование C++
C++ ДП Динамическое программирование
C++ Динамическое программирование
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
12.09.2012, 09:12     Динамическое программирование #2
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
#include <iostream>
#include <cstdlib>
using namespace std;
 
int k(int n, int m) {
    if (n <= 1) return 1;
    int sum = 0;
    for (int i = 1; i <= m && i <= n; ++i) {
        sum += k(n - i, m);
    }
    return sum;
}
 
#define ASSERT(e) if (e) {} else { cout << "WTF??" << endl; exit(1); }
 
int main() {
    int n, m;
    cout << "n = ";
    cin  >> n;
    ASSERT(n > 0);
    cout << "M = ";
    cin  >> m;
    ASSERT(m > 0);
    cout << k(n, m) << endl;
}
Andrew_Lvov
Эксперт C++
 Аватар для Andrew_Lvov
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 758
Записей в блоге: 1
12.09.2012, 17:48     Динамическое программирование #3
k[i] = сколькими способами можно опрыгать i ступенек.
k[1] = 1 - очевидно, если не разрешать "нулевых" шагов.

k[n] = SUM(k[i] + k[n-i]), i = 1...m-1, i != m-i
Из формулы видно, что k[n] считается из значений предыдущих k[l], где l<n, то есть напрашивается рекурсия как один из вариантов. Если ещё и запоминать k[i], то можно ещё и оптимизировать процесс.
mirror2u
0 / 0 / 0
Регистрация: 12.04.2012
Сообщений: 20
12.09.2012, 19:54  [ТС]     Динамическое программирование #4
Спасибо большое, что помогли и объяснили)

Добавлено через 1 час 20 минут
Цитата Сообщение от yekka Посмотреть сообщение
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
#include <iostream>
#include <cstdlib>
using namespace std;
 
int k(int n, int m) {
    if (n <= 1) return 1;
    int sum = 0;
    for (int i = 1; i <= m && i <= n; ++i) {
        sum += k(n - i, m);
    }
    return sum;
}
 
#define ASSERT(e) if (e) {} else { cout << "WTF??" << endl; exit(1); }
 
int main() {
    int n, m;
    cout << "n = ";
    cin  >> n;
    ASSERT(n > 0);
    cout << "M = ";
    cin  >> m;
    ASSERT(m > 0);
    cout << k(n, m) << endl;
}
А не могли бы вы привести пример, без использования рекурсии? Просто при больших значениях,из-за рекурсии, увеличивается время выполнения программы.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
12.09.2012, 22:05     Динамическое программирование #5
Цитата Сообщение от Andrew_Lvov Посмотреть сообщение
Если ещё и запоминать k[i], то можно ещё и оптимизировать процесс.
Мне кажется, это очевидно. Более того, это единственный адекватный вариант, поскольку топик назван "Динамическое программирование".

mirror2u, юзай массивы, запоминай количество путей на каждой спупеньке, а затем используй эти данные.
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
12.09.2012, 23:01     Динамическое программирование #6
можно и без рекурсии
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
28
29
30
31
32
33
34
35
#include <stdlib.h>
#include <stdio.h>
 
#define min(x, y) (x<y?x:y)
typedef unsigned long long RType;
 
RType k(int n, int m) {
    RType * table = (RType *) malloc((n+1) * sizeof(RType));
    table[1] = 1;
    int j;
    for (j = 2; j <= min(m, n); ++j) {
        table[j] = table[j-1] << 1;
    }
    for (; j <= n; ++j) {
        table[j] = 0;
        for(int k = 1; k <= min(m, j-1); ++k) {
            table[j] += table[j-k];
        }
    }
    RType result = table[n];
    free(table);
    return result;
}
 
int main() {
    int n = 0, m = 0;
    printf("Enter n m: ");
    scanf("%d %d", &n, &m);
    if (n <= 0 || m <= 0) {
        printf("BadInput\n");
        exit(1);
    }
    printf("%llu\n", k(n, m));
    exit(0);
}
OlegRuno
2 / 2 / 0
Регистрация: 28.05.2012
Сообщений: 38
13.09.2012, 15:22     Динамическое программирование #7
Понять не могу вот эти вещи:
"typedef unsigned long long RType;
RType * table = (RType *) malloc((n+1) * sizeof(RType));
что такое table?
что такое min?
free(table)?"
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.09.2012, 16:11     Динамическое программирование
Еще ссылки по теме:

C++ Динамическое программирование
C++ Динамическое программирование!
Динамическое программирование C++

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

Или воспользуйтесь поиском по форуму:
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
13.09.2012, 16:11     Динамическое программирование #8
RType -- псевдоним для unsigned long long
table -- указатель на динамически выделяюмую функцией malloc память, которая потом освобождается функцией free
min -- макрос
Код
#define min(x, y) (x<y?x:y)
Yandex
Объявления
13.09.2012, 16:11     Динамическое программирование
Ответ Создать тему
Опции темы

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