VPF::Поиск пути с максимальной суммой в матрице

Atma

Дата 28.5.2006, 13:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 28.5.2006
Где: Минск, Беларусь

Репутация: нет
Всего: нет

Задача:

Дана матрица a(m, n). Найдите в ней путь с максимальной суммой от какого-нибудь элемента первой строки матрицы до какого-нибудь элемента последней строки. Ходить можно вниз по вертикали или диагоналям.

Проблема еще и в том, что эту задачу нужно решить с помощью рекурсии. Как ее правильно записать? Помогите плз!

MAKCim

Дата 28.5.2006, 16:04 (ссылка)

(нет голосов)

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 6
Всего: 207

Код


void find(vector<vector<bool> >& field, int& sum, int i, int j, int s)
{
    if (i<0 || i>=field.size() || j<0 || j>=field[0].size()) 
        return;
    if (i==field.size()-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];       // matrix - твоя матрица, либо через ф-ию ее передавать, либо глобальной делать
        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;
    }
}

--------------------

Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©

Atma

Дата 29.5.2006, 00:33 (ссылка)

(нет голосов)

Загрузка ...

Большое спасибо!
Я так поняла, мне осталось только вывести этот двумерный вектор?
Проблема в том, что мы с контейнерными классами не работали, даже если я его выведу, мой практик будет недоволен.
Можно ли заменить его на обычный двумерный массив?
Я попробовала, но у меня не получилось, вот код полностью:

Код


#include <iostream>
#include <math.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>


using namespace std;
    
const int n=4;
const int m=5;
int matrix[n][m];
int i,j,s, sum;
bool **field;  //двумерное "поле"
void Getmatr (int, int);  //матрица из случайных чисел
void Myprint (int, int);  //выводит матрицу
void find(bool **field, int& sum, int i, int j, int s);

int main()
{
    field =new bool*[n];
    for (int i=0; i<n; i++)
        field[i]=new bool[m];
    Getmatr(n,m);    
    find(field, sum, i, j, s);
    for (int i=0; i<n; i++)
    {
        cout<<"\n";
        for (int j=0; j<m; j++)
            cout<<"  "<<field[i][j];
    }
    Myprint(n,m);
    _getch();      
    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]=(((double)rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
       }
}

void Myprint (int n, int m)
{
    for(int i=0;i<n;i++)
    {  
        printf("\n");
        for(int j=0;j<m;j++)
            printf("%5d",matrix[i][j]);
     }
    printf("\n");
}
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;
    }
}

MAKCim

Дата 29.5.2006, 09:24 (ссылка)

(нет голосов)

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 6
Всего: 207

Цитата

Можно ли заменить его на обычный двумерный массив?

конечно можно

Цитата

но у меня не получилось

что именно
так работает

Код


#include <iostream>
#include <math.h>
#include <vector>

using std::cout;
using std::cin;
using 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);

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;
    }
}

Это сообщение отредактировал(а) MAKCim - 29.5.2006, 09:26

--------------------

Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©

Atma

Дата 29.5.2006, 14:17 (ссылка)

(нет голосов)

Загрузка ...

В таком виде она даже максимальную сумму неправильно ищет (если путь начинается в элементах первой строки после середины). Почему — не знаю+)))
То, что у меня не получилось — вывести путь, по которому эта максимальная сумма складывается smile

Atma

Дата 29.5.2006, 14:44 (ссылка)

(нет голосов)

Загрузка ...

Так, с тем, почему после середины не работает, разобралась всего-то: там в цикле обнуления клеточек j должно изменяться до m=))

MAKCim

Дата 29.5.2006, 17:54 (ссылка)

(нет голосов)

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 6
Всего: 207

Цитата

j должно изменяться до m

очепятка

Цитата

То, что у меня не получилось — вывести путь, по которому эта максимальная сумма складывается

через стек
схематично

Код


#include <stack>
#Include <map>

using std::stack;
using std::pair;

typedef stack<pair<int, int> > stack_t;

...

void find(bool **field, int& sum, int i, int j, int s, stack_t& primary, stack_t& 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;
        }
        return;
    }
    if (!field[i][j])
    {
        field[i][j]=true;
        current.push(pair<int, int>(i,j));
        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;
    }
}

если STL нельзя пользоваться тогда уж думай сама, как его смоделировать smile

--------------------

Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©

Atma

Дата 29.5.2006, 18:17 (ссылка)

(нет голосов)

Загрузка ...

Мило+)) STL пользоваться нельзя... Мне надо код сдать, а не результат показать, вот в чем дело. И еще объяснить, как это все работает+)))

Я думаю, стек (у тебя их два, так?) можно заменить двумя массивами структур (вида int row, int col), я все равно динамической размерностью не пользуюсь нигде. И как-нибудь их потихонечку заполнять...
Пффф... Завтра надо это сдать, чувствую или рискану и чуть-чуть сжульничаю, или не знаю=)))

Добавлено @ 18:29
И еще вопрос: в main что-нибудь с этими стеками нужно делать? Там же тоже рекурсия m раз вызывается, может их очистить надо?

Atma

Дата 29.5.2006, 18:58 (ссылка)

(нет голосов)

Загрузка ...

Моя робкая попытка заменить стеки на массивы структур (не работает совершенно, даже близкого ничего не выдает), результат должен быть записан в массив massiv2.

Код


struct element
{
    int row;
    int col;
};

element *massiv2;
element *massivtemp;

...//в начале main все структуры обнуляются

void Recfind(bool **field, int& sum, int i, int j, int s, element *massiv2, element *massivtemp)
{
    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];
            
                         //Полностью переписываем один массив в другой (Как бы копирование одного стека в другой)
                        for (int i=0; i<n; i++)
            {
                massiv2[i].col=massivtemp[i].col;
                massiv2[i].row=massivtemp[i].row;
            }
        
        }
        return;
    }
    if (!field[i][j])
    {
        int temp_sum=0;
                                field[i][j]=true;

//Вот тут не факт, что правильно, попытка записать i и j в конец массива структур(на дно стека).
        massivtemp[n-i-1].row=i;
        massivtemp[n-i-1].col=j;
                                
   int temp=s+matrix[i][j];
    
       Recfind(field,sum,i+1,j,temp, massiv2,massivtemp);
        
        Recfind(field,sum,i+1,j-1,temp, massiv2, massivtemp);
        
        Recfind(field,sum,i+1,j+1,temp, massiv2, massivtemp);
        
//Обнуление структур (типа очищение стека)
for (int i=0; i<n; i++)
        {
            massivtemp[i].col=0;
            massivtemp[i].row=0;
        }
    
        cout<<endl;
        field[i][j]=false;
    }
}

MAKCim

Дата 30.5.2006, 09:33 (ссылка)

(нет голосов)

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 6
Всего: 207

Код


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;
   }
};
...
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;
        }
        return;
    }
    if (!field[i][j])
    {
        field[i][j]=true;
        current.push(coords(i,j));
        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;
    }
}

Добавлено @ 09:46
вся прога

Код


#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;
    }
}

--------------------

Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©

Dov

Дата 31.5.2006, 14:42 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Цитата(Atma @ 29.5.2006, 13:17

)

То, что у меня не получилось — вывести путь, по которому эта максимальная сумма складывается

Можно подсветить этот путь другим цветом, было бы неплохо, имхо.

--------------------

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

Atma

Дата 31.5.2006, 14:50 (ссылка)

(нет голосов)

Загрузка ...

Dov,

Цитата

Можно подсветить этот путь другим цветом, было бы неплохо, имхо.

Ага, да, было бы здорово, но я уже все равно сдала все так, как было+)

MAKCim, спасибо за помощь, задачу сдала и зачет получила=)

Dov

Дата 31.5.2006, 15:09 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Цитата(Atma @ 31.5.2006, 13:50

)

Ага, да, было бы здорово, но я уже все равно сдала все так, как было+)

Эх, жаль, поспешила ты, Atma, с зачетом. smile

Вот код MAKCim`а с подсветкой:

Код

#include <windows.h>
#include <iostream>    
#include <math.h>
#include <time.h>
    
using std::cout;    
using std::cin;    
using std::endl;

enum COLOR {BLACK, BLUE = 9, GREEN, TURQUOISE, RED, VIOLET, YELLOW}; // выбор цветов для подсветки

void OutWay(short x, short y, WORD color = BLACK)
{
    HANDLE stdOut = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD  coord  = {x, y};
    WriteConsoleOutputAttribute(stdOut, &color , 1, coord, NULL);
}
    
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;
        return index;
    }    
    Stack& operator=(const Stack& obj)    
    {    
        index=obj.index;    
        for (int i=0; i<index; ++i) array[i]=obj.array[i];
        return *this;
    }    
   void Print()    
   {    
        for (int i=0; i<index; ++i)
        {
            //std::cout<<"x="<<array[i].x<<", y="<<array[i].y<<std::endl;
            OutWay(array[i].x * 2, i + 1, VIOLET);
        }                
   }    
};
    
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<m; j++) field[i][j]=false;    // Первоначально никакую клетку не посетили    
    }    
    Getmatr(n,m);    
    Stack c;    
    for (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<<"\nMax: "<<sum<<endl;    
    c.Print();    
    int a;    
    cin>>a;    
    for (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-1,temp,primary,current);    
        find(field,sum,i+1,j,temp,primary,current);    
        find(field,sum,i+1,j+1,temp,primary,current);    
        current.pop();    
        field[i][j]=false;    
    }    
}

--------------------

Atma

Дата 1.6.2006, 21:50 (ссылка)

(нет голосов)

Загрузка ...

Dov, Афигеть как классно!+) Эт не я поторопилась, дедлайн был во вторник...+((
А так — вообще супер, спасибо, оставлю себе как память+)))

tymrfik

Дата 20.1.2011, 17:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 20.1.2011

Репутация: нет
Всего: нет

Здраствуйте!!!)) Конечно, я понимаю, что это тема была открыта довольно давно и не известно просмотрет ли кто-нибудь ее сейчас. Но у меня возник вопрос. (У меня сейчас уже экзамен на носу по методам программирования, а тут у меня ТОЧНО ТАКАЯ ЖЕ ЗАДАЧА,ТОЧЬ-В-ТОЧЬ! ТОлько одно но! - надо к рекурсии устроить мемоизацию!!! - А вот тут я профан=( ) Подскажите пожалуйста как сделать мемоизацию к такой задачи! Как я понимаю надо преобразовать функцию void find - могли бы вы помочь?- как это сделать?!!! В этой функции у нас значение sum передается по ссылке?!) Код вообще очень изысканный, классный!!! smile

Это круто!!!

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »