Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перегрузка операторов http://www.cyberforum.ru/cpp-beginners/thread1116147.html
Реализуйте класс CTime , моделирующий время суток ( количество часов , минут и секунд). Каркас класса : // Моделирует время суток , задаваемой количеством часов ( 0-23 ) , // Минут ( 0-59 ) и...
C++ Составить программу, выводящую на экран квадрат Пифагора - таблицу умножения. Составить программу, выводящую на экран квадрат Пифагора - таблицу умножения. Рекомендуемый вид экрана программы приведен ниже. 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 2 4 6 8 10 12 14 16 18... http://www.cyberforum.ru/cpp-beginners/thread1116146.html
C++ Чтение строки из файла
как считать строку(-и) из файла без стринга? по заданию у меня выводит кол-во слов с одинаковыми первой и последними буквами(символами) вместо 3 у меня выводит 33333,с сохранением пока не пробовал...
C++ Массив со сдивгом
Ребята, помогите пожалуйста! Дан вещественный массив А и натуральное число k. Если количество положительных элементов в массиве А больше k, то сдвинуть циклически все элементы массива на одну...
C++ Если елементы массива соседние одинаковы то один из них заменяется на 0 а другой увеличиваетмя на один http://www.cyberforum.ru/cpp-beginners/thread1116050.html
#include "stdafx.h" #include<string> #include <cmath> #include <iostream> #include<locale> using namespace std; const int max_size=255; int a,b,rl1={0},i,j,rl2={0},c,k,rl_chislo,kol=0; string...
C++ Дан двухмерный массив целых чисел. Определить сумму элементов больших 30 Дан двухмерный массив целых чисел. Определить сумму элементов больших 30 подробнее

Показать сообщение отдельно
jzetko
0 / 0 / 0
Регистрация: 11.03.2014
Сообщений: 3

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

11.03.2014, 11:52. Просмотров 331. Ответов 0
Метки (Все метки)

Здравствуйте. Имеется следующая задача, реализовать которую нужно 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.