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

Динамическое программирование. Рыцарь. - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ подскажите аналог конструкции pascal в c http://www.cyberforum.ru/cpp-beginners/thread221841.html
Начал изучать язык Си без плюсов. подскажите, пожалуйста, аналог такой конструкции pascal if a in then в языке Си
C++ очень надо к 6 часам очень гадо к 6 часам Класс n-мерных векторов Базовый класс (координаты начала и конца вектора Совет: реализовать дополнительный класс NPoint, содержащий в виде массива координаты n-мерных точек, а также количество координат - N) Конструкторы: по умолчанию, с параметрами и копирования. Деструктор. Функции: перегрузки операции сложения; Перегрузка операции вычитания; перегрузки операции... http://www.cyberforum.ru/cpp-beginners/thread221836.html
C++ Вычислить: y=1!+2!+3!+…+n! (n>0).
Вычислить: y=1!+2!+3!+…+n! (n>0). Всем плюсану!
Даны действительные числа А,В,С . Найти те из них которые не принадлежат заданному отрезку [0; 2]. C++
Даны действительные числа А,В,С . Найти те из них которые не принадлежат заданному отрезку . кто напишет правильно программу тому "+"
C++ Сохранение информации в файле и считывание из него http://www.cyberforum.ru/cpp-beginners/thread221828.html
В файле сохраняется информация о деятельности некоторых подразделений: наименование подразделения, количество сотрудников, прибыль, полученная за текущий квартал. Определить лучшее подразделение с учетом числа сотрудников.
C++ C++ Блок схема Всем доброго времени суток. Есть проблема, которую я сам решить не могу из-за того, что ничерта не понимаю. Суть ее в следующем, есть код программы, написанной в С++, к этой программе нужна блок схема. Парни, кто может, помогите плиз, ну прям очень надо. Из за этой схемы курсак сдать не могу. Заранее всем откликнувшимся огромное спасибо. #include <iostream> #include <string> #include <vector>... подробнее

Показать сообщение отдельно
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
16.01.2011, 15:57  [ТС]     Динамическое программирование. Рыцарь.
Эт точно очень неэффективные алгоритмы + громоздкие они походу получаются (по крайней мере у меня точно). А могли бы подсказать еще немного: вот 3 вариант - " модификация первой, основанная на механизме «запоминания»." - будет программа с мемоизацией - это запоминание промежуточных результатов работы рекурентного алгоритма. Только вот интересный факт, в своем рекурентном коде не представляю, где нужно вставить эту мемоизацию. + где я не искал, везде только мемоизация встречается с Java языком?!!!
#include <iostream>
#include <math.h>

using std::cout;
using std::cin;
using std::endl;

struct coords
{
int x,y;
coords(int p_x=0, int p_y=0): x(p_x), y(p_y) {}
};

class Stack
{
private:
coords array[1024]; // Чтоб не мучаться с дин. массивом
int index;
public:
Stack(): index(0) {}
void push(const coords& obj)
{
if (index<=1024) array[index++]=obj;
}
coords pop() {if (index-1>=0) --index;}
Stack& operator=(const Stack& obj)
{
index=obj.index;
for (int i=0; i<index; ++i) array[i]=obj.array[i];
}
void Print()
{
for (int i=0; i<index; ++i) std::cout<<"x="<<array[i].x<<", y="<<array[i].y<<std::endl;
}
};


const int n=4;
const int m=5;

int matrix[n][m];
void Getmatr (int, int); //матрица из случайных чисел
void Myprint (int, int); //выводит матрицу
void find(bool**, int&, int, int, int, Stack&, Stack&);

int main()
{
int sum=0;
bool **field; //двумерное "поле"
field =new bool*[n];
for (int i=0; i<n; i++)
{
field[i]=new bool[m];
for (int j=0; j<n; j++) field[i][j]=false; // Первоначально никакую клетку не посетили
}
Getmatr(n,m);
Stack c;
for (int i=0; i<m; i++) // Проходим по элементам первой строки
{
int temp_sum=0;
Stack a,b;
find(field,temp_sum,0,i,0,a,b);
if (temp_sum>sum)
{
sum=temp_sum;
c=a;
}
}
Myprint(n,m);
cout<<"Max: "<<sum<<endl;
c.Print();
int a;
cin>>a;
for (int i=0; i<n; i++)
delete []field[i];
delete []field;
return 0;
}

void Getmatr (int n, int m)
{
int RANGE_MIN=0;
int RANGE_MAX=10;
srand((unsigned)time(NULL));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
matrix[i][j]=
static_cast<int>(((double)rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
}
}

void Myprint (int n, int m)
{
for(int i=0;i<n;i++)
{
cout<<endl;
for(int j=0;j<m;j++)
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}

void find(bool **field, int& sum, int i, int j, int s, Stack& primary, Stack& current)
{
if (i<0 || i>=n || j<0 || j>=m)
return;
if (i==n-1)
{
if (s+matrix[i][j]>sum)
{
sum=s+matrix[i][j];
primary=current;
primary.push(coords(j,i));
}
return;
}
if (!field[i][j])
{
field[i][j]=true;
current.push(coords(j,i));
int temp=s+matrix[i][j];
find(field,sum,i+1,j,temp,primary,current);
find(field,sum,i+1,j-1,temp,primary,current);
find(field,sum,i+1,j+1,temp,primary,current);
current.pop();
field[i][j]=false;
}
}
 
Текущее время: 22:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru