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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Rakaddar
0 / 0 / 0
Регистрация: 23.03.2009
Сообщений: 14
#1

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

27.04.2009, 10:28. Просмотров 436. Ответов 3
Метки нет (Все метки)

Помогите пожалуйста решеть динамическим программированием задачу Лесенки. Заранее спасибо. Я просто не могу понять логику динамики в этой задаче

Добавлено через 23 часа 35 минут 39 секунд
решил сам
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
using namespace std;
 
int lesenka(int N,int min){
    int sum=0;
    for (int i=min;i<=N;i++){
        if(i==N){sum++;continue;}
        sum+=lesenka(N-i,i+1);  
    }
 
    return sum;
}
 
main () {
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);   
    int N;
    cin>>N;
    cout<<lesenka(N,1);
    cin>>N;
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2009, 10:28     Динамическо программирование
Посмотрите здесь:

C++ Программирование со строками
Системное программирование C++
C++ Динамическое программирование
C++ Параллельное программирование
C++ Оконное программирование
Программирование графов C++
C++ Программирование алгоритмов
Программирование с файлами C++
Разработать метод-член класса для определения минимального и максимального элементов одномерного динамическо C++
C++ Динамическое программирование
Многопоточное программирование C++
C++ Динамическое программирование

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Monte-Cristo
2786 / 1372 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
27.04.2009, 10:32     Динамическо программирование #2
а тут точно есть динамика?
Rakaddar
0 / 0 / 0
Регистрация: 23.03.2009
Сообщений: 14
11.03.2010, 12:42  [ТС]     Динамическо программирование #3
точно, можно перерешить этот рекурсивный перебор на динамику
Грымзик
2466 / 1443 / 31
Регистрация: 14.09.2009
Сообщений: 2,742
11.03.2010, 17:29     Динамическо программирование #4
Строишь таблицу: индекс столбца - количество кубиков (от 1 до N),
индекс строки - количество уровней. И элемент m[i][j] будет показывать
сколько лесенок высотой не более j можно построить из i кубиков.
Первая строка заполняется элементарно. Для заполнения i-го элемента
j+1 строки делаем так: суммируем все m[I][j], где I от i/2-1 (если i четное),
или от i/2 (нацело, если i нечетное) и до 1. И надо найти элемент m[N][N].
Yandex
Объявления
11.03.2010, 17:29     Динамическо программирование
Ответ Создать тему
Опции темы

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