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

Как переписать код, чтобы получить мемоизацию. - C++

Восстановить пароль Регистрация
 
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
19.01.2011, 10:50     Как переписать код, чтобы получить мемоизацию. #1
Рекурсивное решение следующей задачи: (Путь по клеткам с поиском максимальной суммы.)
За долгую и верную службу Рыцарю позволено набрать сокровищ в сокровищнице своего сеньора. Сокровищница имеет форму прямоугольника, состоящего из отдельных "клеток" — прямоугольных комнат. В каждой комнате хранятся сокровища известной стоимости. Рыцарь может вынести сколько угодно сокровищ, но пройдя через сокровищницу только один раз. Он может начать с любой комнаты вдоль внешней северной стены сокровищницы (выбор комнаты — за рыцарем). На каждом шаге он может переходить в одну из трех "южно-соседних" комнат: южную, юго-восточную или юго-западную. Из комнат, граничащих с восточной или западной внешней стеной, возможны только два направления выхода. Закончить путь Рыцарь должен в любой из комнат на южной внешней стороне сокровищницы.
У Рыцаря есть план сокровищницы — прямоугольная таблица, в которой обозначены стоимости сокровищ каждой комнаты. Направлению с севера на юг соответствует направление сверху вниз на карте.
По заданной карте нужно найти один из допустимых путей, обеспечивающих наибольшую возможную сумму сокровищ.
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
#include <iostream>
#include <math.h>
#include <vector>
 
using namespace std;
 
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);
 
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);    
    for (int i=0; i<m; i++)           // Проходим по элементам первой строки
    {
        int temp_sum=0;
        find(field,temp_sum,0,i,0);
        if (temp_sum>sum) sum=temp_sum;
    }
    Myprint(n,m);
    cout<<"Max: "<<sum<<endl;
    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)
{
    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];
        return;
    }
    if (!field[i][j])
    {
        field[i][j]=true;
        int temp=s+matrix[i][j];       
        find(field,sum,i+1,j,temp);
        find(field,sum,i+1,j-1,temp);
        find(field,sum,i+1,j+1,temp);
        field[i][j]=false;
    }
}
Необходимо переписать функцию void find(bool **field, int& sum, int i, int j, int s) под мемоизацию. Помогите пожалуйста! А могли бы вы объяснить как в данной функции набирается сумма для вывода. Понимаю что тут всё дело в применении ссылки - правда понимаю это расплывчато!(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2011, 10:50     Как переписать код, чтобы получить мемоизацию.
Посмотрите здесь:

C++ Как получить ассемблерский код
C++ Как получить код завершения процесса
Как получить html код C++
код, который прекрасно выполняет Code::Blocks не выполняеться в Студии, как сделатьь так чтобы Студия воспринимала этот код?? C++
C++ Переписать код, чтобы выводило студентов имеющих оценку 2
Как переделать код, чтобы изменить интерфейс до неузнаваемости? C++
C++ Как получить код символа unicode в std::wstring?
Как получить готовый .exe файл, чтобы запускать его без IDE C++

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

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

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