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

@mirror2u · Регистрация: 12.04.2012

Студворк — интернет-сервис помощи студентам

Мячик прыгает по лестнице, состоящей из 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.

@yekka · 12.09.2012, 09:12

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 · 12.09.2012, 17:48

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 · 12.09.2012, 19:54 **[ТС]**

Спасибо большое, что помогли и объяснили)

Добавлено через 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 · 12.09.2012, 22:05

Сообщение от Andrew_Lvov

Если ещё и запоминать k[i], то можно ещё и оптимизировать процесс.

Мне кажется, это очевидно. Более того, это единственный адекватный вариант, поскольку топик назван "Динамическое программирование".

mirror2u, юзай массивы, запоминай количество путей на каждой спупеньке, а затем используй эти данные.

@yekka · 12.09.2012, 23:01

можно и без рекурсии

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 · 13.09.2012, 15:22

Понять не могу вот эти вещи:
"typedef unsigned long long RType;
RType * table = (RType *) malloc((n+1) * sizeof(RType));
что такое table?
что такое min?
free(table)?"

@yekka · 13.09.2012, 16:11

RType -- псевдоним для unsigned long long
table -- указатель на динамически выделяюмую функцией malloc память, которая потом освобождается функцией free
min -- макрос

Code
1
#define min(x, y) (x<y?x:y)

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@Andrew_Lvov 261 / 191 / 10 Регистрация: 19.08.2010 Сообщений: 760 Записей в блоге: 1
	12.09.2012, 17:48
	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], то можно ещё и оптимизировать процесс. 1

@OlegRuno 2 / 2 / 0 Регистрация: 28.05.2012 Сообщений: 38
	13.09.2012, 15:22
	Понять не могу вот эти вещи: "typedef unsigned long long RType; RType * table = (RType ) malloc((n+1) sizeof(RType)); что такое table? что такое min? free(table)?" 0