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

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

Восстановить пароль Регистрация
 
jzetko
0 / 0 / 0
Регистрация: 11.03.2014
Сообщений: 3
11.03.2014, 11:52     Динамическое программирование #1
Здравствуйте. Имеется следующая задача, реализовать которую нужно 3-мя методами:
• неэффективным, при помощи рекуррентного спуска.
• с использованием динамического программирования.
• модификацией первого, основываясь на механизме «запоминания».
Сама задача:
Прямоугольная таблица имеет М строк и N столбцов. В каждой ее клетке записано натуральное число не больше 200. Нужно пройти из левого верхнего угла таблицы в правый нижний, на каждом шаге перемещаясь на 1 клетку вправо или вниз. Очевидно, таких путей много, и для каждого можно найти сумму чисел в пройденных клетках. Ясно, что среди этих сумм есть максимальная.
"Хорошими" считаются не только пути с максимально возможной суммой, но и пути, сумма которых отличается от максимальной не более чем на К. Количество "хороших" путей гарантированно не больше 10.
Найти максимально возможную сумму и количество "хороших" путей.
Вход. Первая строка входного текста содержит три целых числа М (2<М<200), N (2<N<200) и K (0<K<200). Каждая из следующих М строк задает N чисел в соответствующих клетках.
Выход. Первая строка текста должна содержать максимально возможную сумму, вторая — количество маршрутов, сумма чисел которых отличается от максимальной не более чем на K.
Вопрос состоит в следующем, почему не выводится на экран бинарное дерево? И вообще правильно ли оно реализовано. Просто бинарные деревья мы как таковые еще не проходили. Даже толком не представляю как с ними работать. И куда вообще девать это K? Может есть знающие люди)) буду благодарен за помощь. Код прилагается
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <conio.h>
 
using namespace std;
 
struct Node{// звено дерева
    int x; //то, что записываем в дерево
    Node *u,*u1;// указатели на новые звенья
    int k;// число "хороших путей"
}; 
 
void show(Node *&Tree){//функция обхода
    if(Tree != NULL){//пока не встретится пустое звено
        show(Tree->u);//рекурсивная функция для вывода левого поддерева
        cout<<Tree->x;//отображаем корень дерева
        show(Tree->u1);//рекурсивная функция для вывода правого поддерева
    }
}
 
void add_node(int x,Node *&MyTree){//функция добавления звена в дерево
    if(NULL==MyTree){//если нет дерева, сажаем семечко
        MyTree=new Node;//выделяем память под звено дерева
        MyTree->x=x;//записываем данные в звено
        MyTree->u=MyTree->u1=NULL;
    }
                if(x<MyTree->x){//если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо
                    if (MyTree->u != NULL) add_node(x,MyTree->u);//при помощи рекурсии заталкиваем элемент на свободное место
                    else{
                        MyTree->u=new Node;//выделяем память левому подзвену
                        MyTree->u->u=MyTree->u->u1 = NULL;//у левого подзвена будут свои левые и правые подзвенья
                        MyTree->u->x=x;//записываем в левое подзвено записываемый элемент
                    }
                } 
                if(x>MyTree->x){//если нововведенный элемент х больше чем элемент х из семечка, уходим вправо
                    if(MyTree->u1 != NULL) add_node(x,MyTree->u1);//при помощи рекурсии заталкиваем элемент на свободное место
                    else{//если элемент получил свой участок, то
                        MyTree->u1=new Node;//Выделяем память правому подзвену
                        MyTree->u1->u=MyTree->u1->u1 = NULL;//у правого подзвена будут свои левые и правые подзвенья
                        MyTree->u1->x=x;//записываем в правое подзвено записываемый элемент
                        
                    }
                }    
}
 
int main(int argc, char** argv)
{
    setlocale(LC_ALL,"Russian");
    int N;
    int M;
    cout<<"Введите кол-во строк(M): ";
    cin>>M;
    cout<<"Введите кол-во столбцов(N): ";
    cin>>N;
    if((N<2||N>200)||(M<2||M>200)){
        cout<<"Ошибка ввода!"<<endl;
        system("PAUSE");
        return 0;
    }
 
 
    short** desk;
    desk = new short*[N];
    for(int i=0;i<N;i++){
        desk[i]=new short[M];
    }
    cout<<"Выберите способ заполнения таблицы:\n1. С клавиатуры\n2. Рандомно\n";
    int forswitch;
    cin>>forswitch;
    switch(forswitch){
        case 1:{
            for(int i=0;i<M;i++){
                for(int j=0;j<N;j++){
                    cin>>desk[i][j];
                }
            }
            break;
        }
        case 2:{
             for(int i=0;i<M;i++){
                for(int j=0;j<N;j++){
                    desk[i][j]=rand()%199 + 1;
                }
            }
            break;
        }
 
    }
 
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            cout<<desk[i][j]<<" ";
        }
        cout<<endl;
    }
    int** deskforhelp;
    deskforhelp = new int*[N];
    for(int i=0;i<N;i++){
        deskforhelp[i]=new int[M];
    }
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            if(i==0&&j==0){
                deskforhelp[i][j]=desk[i][j];
            }
            if(i==0&&j!=0){
                deskforhelp[i][j]=deskforhelp[i][j-1]+desk[i][j];
            }
            if(j==0&&i!=0){
                deskforhelp[i][j]=deskforhelp[i-1][j]+desk[i][j];
            }
            if(i!=0&&j!=0){
                if(deskforhelp[i][j-1]>deskforhelp[i-1][j]){
                    deskforhelp[i][j]=deskforhelp[i][j-1]+desk[i][j];
                }
                else{
                    deskforhelp[i][j]=deskforhelp[i-1][j]+desk[i][j];
                }
            }
        }
    }
    cout<<endl<<endl;
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            cout<<deskforhelp[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"\nМаксимум = "<<deskforhelp[M-1][N-1]<<endl;;
    Node *Tree=NULL;  //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой
    for (int i=0;N>0;i++) {
        add_node(N,Tree);}
    for (int i=i;M>0;i++) {
        add_node(M,Tree);}
    show(Tree); //Вывод на экран дерева. или просто обход дерева
    cin.get();
    cout<<(N,Tree)<<(M,Tree)<<endl;
    delete []desk;
    delete []deskforhelp;
    desk=NULL;
    deskforhelp=NULL;
    system("PAUSE");
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2014, 11:52     Динамическое программирование
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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