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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Распознование угла программой http://www.cyberforum.ru/cpp-beginners/thread231057.html
Подскажите, пожалуйста. Если во входных данных задается какой-то угол, то при дальнейших расчетах программой он должен быть переведен в радианы. Как это задается в программном коде? То есть, к примеру задан угол 37 градусов, то потом в каком виде он будет участвовать в расчете программы?
C++ функция Perim Помогите с лабораторной, пожалуйста. Написать программу, в которой использовалась бы функция Perim, которая возвращает периметр квадрата, заданного координатами вершин http://www.cyberforum.ru/cpp-beginners/thread231038.html
C++ имеется последовательность чисел содержащая n элементов, определить сколько раз в ней меняется знак
имеется последовательность чисел содержащая n элементов, определить сколько раз в ней меняется знак Добавлено через 17 минут на сишке Добавлено через 25 секунд помогите, а
C++ Сборник вопросов от меня.
Решил создать чисто свою тему, чтобы не плодить кучу тем из-за мелочей. Буду всегда писать вопросы здесь, надеюсь на вашу помощь. Спасибо. Вопрос, если внутри класса объявлю структуру, то объекты этой структуры я могу создавать только внутри этого класса? и еще вот вопрос, есть класс A(базовый) и класс B(производный). В обоих классах определен метод virtual show_time(); если я объявлю...
C++ Распечатать строку, которая содержит заданное слово заданное колличество раз http://www.cyberforum.ru/cpp-beginners/thread231020.html
Доброго времени суток. Суть проблемы такова: в написанной программе, вместо строки распечатывается первое слово. До этого эта программа была написана несколько по другому и строка печаталась полностью. Помогите разобраться с данной проблемой... Собственно задание: Даны две строки, содержащие не более 100 символов. Строки состоят из слов, разделенных пробелами. Распечатать строку, которая...
C++ применение c++ в 1 семестре начали проходить с++ за сем дошли до указателей (во 2 их начнем) прошли: типы, константы, операции, функции (передача по ссылке, по значению), потоки ввода/вывода, циклы, массивы, строки (char) я сам уже прошел указатели, и основы ООП. мы весь сем решали мат. задачи разные, уже от них тошнит. что реально полезное можно написать зная вот это все вышеперечисленное? спасибо подробнее

Показать сообщение отдельно
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
19.01.2011, 10:50     Как переписать код, чтобы получить мемоизацию.
Рекурсивное решение следующей задачи: (Путь по клеткам с поиском максимальной суммы.)
За долгую и верную службу Рыцарю позволено набрать сокровищ в сокровищнице своего сеньора. Сокровищница имеет форму прямоугольника, состоящего из отдельных "клеток" — прямоугольных комнат. В каждой комнате хранятся сокровища известной стоимости. Рыцарь может вынести сколько угодно сокровищ, но пройдя через сокровищницу только один раз. Он может начать с любой комнаты вдоль внешней северной стены сокровищницы (выбор комнаты — за рыцарем). На каждом шаге он может переходить в одну из трех "южно-соседних" комнат: южную, юго-восточную или юго-западную. Из комнат, граничащих с восточной или западной внешней стеной, возможны только два направления выхода. Закончить путь Рыцарь должен в любой из комнат на южной внешней стороне сокровищницы.
У Рыцаря есть план сокровищницы — прямоугольная таблица, в которой обозначены стоимости сокровищ каждой комнаты. Направлению с севера на юг соответствует направление сверху вниз на карте.
По заданной карте нужно найти один из допустимых путей, обеспечивающих наибольшую возможную сумму сокровищ.
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) под мемоизацию. Помогите пожалуйста! А могли бы вы объяснить как в данной функции набирается сумма для вывода. Понимаю что тут всё дело в применении ссылки - правда понимаю это расплывчато!(
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 07:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru