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

предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ [Матрица] Круг или квадрат? http://www.cyberforum.ru/cpp-beginners/thread337379.html
Доброго времени суток. Условие тут. Просьба подсказать алгоритм или выложить код с кратким описанием идеи решения. Сам довольно много думал, но ничего дельного не надумал... А задача должна быть несложной.
C++ Visual C++ & Hello world Вот поставил Visual C++ 2005 Пишу: #include "stdafx.h" #include <iostream.h> int _tmain(int argc, _TCHAR* argv) { http://www.cyberforum.ru/cpp-beginners/thread337362.html
Почему тормозит играаа??? C++
Добрый день - решил недавно создать игрушку (третяя на моем счету)... но на этот раз игра не пошаговая - эдакое подобие бомбермена с инвентарем... Можете пожалуйста подсказать по какой причине игра может тормозить ? (Возможно проблема в алгоритме - основная часть которого в мейн функции(это цикл)- пожалуйста обратите внимание) Администрацию сайта просьба не переносить даное сообщение в...
C++ простые функции
Всем приветик!!! Есть код: #include<iostream.h> #include<conio.h> #include<string.h> enum Shape{prizm,parallelepiped,cube,pyramid,cone,cylinder}; class Body {
C++ Построить эйлерову цепь в графе. http://www.cyberforum.ru/cpp-beginners/thread337314.html
Всем доброго времени суток! Помогите пожалуйста или подскажите как сделать следующее. Дали задание по дискретной математике построить эйлерову цепь в графе (нужно реализовать все программе, но вот не знаю с чего начать). Задание следующее: Построить эйлерову цепь в графе. Изменить алгоритм построения эйлерова цикла так, чтобы можно было использовать его для построения эйлеровой цепи в графе....
C++ MinGW запрет неявного преобразования типов Существует ли какой то режим у gcc (MinGW) где бы компилятор "ругался" или хотя бы предупреждал о неявном преобразование типов? Причем не важно: int -> double или double -> int подробнее

Показать сообщение отдельно
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
31.07.2011, 22:09  [ТС]     предлагаю людям класс "рекурсивный обход матрицы" для решения задач на такую тематику
Хз как понятно написать. Вот такая документация.
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
class rek_obhod_matr {
 
 public:
  //Конструктор, принимает такие парамеры: указатель на матрицу,
  //количество строк, количество столбцов
  //начало (строку, столбец)
  //Функцию-предикат отвечающую за то, на какую точку будет совершён переход (прыжок)
  //Функцию- предикат, определяющую, найден ли очередной путь или нет
  //и функцию, меняющую (или не меняющую) матрицу
  rek_obhod_matr(T**, int, int,int, int,  bool(*)(rek_obhod_matr<int>* source, int, int),\
                 bool (*) (rek_obhod_matr<int>* source),\
                 void (*)(rek_obhod_matr<int>* source));
 
  //Это понятно что делает, возвращает вектор пройденных клеток
  //Это надо в основном будет для предиката poisk_kletok_
  vector< pair<int, int> > set_chto_proshli ();
 
  //Возвращает вектор клеток, куда можно йпойти.
  //Это надо в основном будет для поиска, не конец ли пути
  vector< pair<int, int> > get_kuda_poidom () {return _kuda_poidom;};
 
  //Преобразования типа, эта херь позволит перегрузить оператор [][]
  //Это я сам придумал подачи ребят
  operator T**() {return matrix;};
 
  //Это возвращает вектор найденнных путей клеток
  //Это надо в основном будет для предиката poisk_kletok_
  vector <vector <pair<int, int> > > set_puti () {return puti;}
 
  //Эти функции возвращают координаты текущей клетки
  int get_i_tek () {return i_tek;}
  int get_j_tek () {return j_tek;}
}

Ещё есть реализация. Ну вот кто разберётся в этом тому дам реализацию. Понятнее не умею написать.

Добавлено через 7 часов 53 минуты
Вот условие задачи: дана прямоугольная матрица, заполненная числами типа int. Необходимо из левого нижнего угла попасть в правый верхний. Сумма пройденный клеток не должна превышать заданного числа, количество ходов неограниченно. Ходить можно в любую сторону только на одну клетку. В одну и ту же клетку можно заходить сколько угодно раз. Не допускается ход из клетки A в клетку B если ранее уже был совершён такой ход. Вот я так решил с помощью моего класса. Матрица 2x3
0 1 2
3 4 5
Ограничение 25. Даёт 145 вариантов.


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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <windows.h>
#include "rek_obhod_matr.h" 
#include <vector>
#include <numeric> 
#define ogranichenie 25 
#define M  2 
#define N  3 
using namespace std;
 
 
 
template <class T>
bool _poisk_kletok_ (rek_obhod_matr<int>* source, int i_pot, int j_pot) {
 
 int i_tek= (* source).get_i_tek();
 int j_tek= (* source).get_j_tek();
 //Значение текущей клетки
 int znach_tek= (*source)[i_tek][j_tek];
 
 //Вектор пройденых пар
 vector< pair<int, int> > chto_proshli= (* source).set_chto_proshli (); 
 //найдём верхушку этого вектора
 pair <int, int> para;
 if (chto_proshli.size())
  para= make_pair (chto_proshli.back().first, chto_proshli.back().second);
 
  
 //Сумма пройденных клеток; 
 int sum= 0;
 //Вектор пройденных значений
 vector <int> chto_proshli_;
 for (int i= 0; i< chto_proshli.size(); i++)
  chto_proshli_.push_back ((*source)[chto_proshli[i].first][chto_proshli[i].second]);
 
 chto_proshli_.push_back (znach_tek);
 chto_proshli_.push_back ((*source)[i_pot][j_pot]);
 //Сортирнём
 sort (chto_proshli_.begin(), chto_proshli_.end());
 //Убираем повторы
 vector<int>::iterator it= unique (chto_proshli_.begin(), chto_proshli_.end());
 chto_proshli_.resize (it- chto_proshli_.begin());
 //Сама сумма 
 sum= accumulate(chto_proshli_.begin(), chto_proshli_.end(), sum); 
 
 //Это будет вектор пар клеток. Он нужен вот для чего: в одн и ту же клетку зайти допускается.
 //но повторить прыжок- ни в коем случае.
 //прыжок это всегда две клетки. Их и ищем
 
 vector < pair < pair <int, int>, pair <int, int> > > dve_kletki;
 int temp= chto_proshli.size()- 2;
 for (int i= 0; i<= temp; i++) {
  pair <int, int> temp_0 (chto_proshli[i].first, chto_proshli[i].second);    
  pair <int, int> temp_1 (chto_proshli[i+ 1].first, chto_proshli[i+ 1].second);    
  dve_kletki.push_back (pair <pair <int, int>, pair <int, int> > (temp_0, temp_1));
 }    
 
 //Сверху
 if ((i_tek== i_pot+ 1)&& (j_tek== j_pot)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end())
  if (sum<= ogranichenie) 
   return true;
 }
 
 //Снизу
 if ((i_tek== i_pot- 1)&& (j_tek== j_pot)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
  if (sum<= ogranichenie) { 
   return true;
   }
  }
 }
 
 //слева
 if ((i_tek== i_pot)&& (j_tek== j_pot+ 1)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
   if (sum<= ogranichenie) { 
    return true;
   }
  }
 }
 
 //Справа
 if ((i_tek== i_pot)&& (j_tek== j_pot- 1)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
   if (sum<= ogranichenie) 
    return true;
  }
 }
 return false;            
}
 
 
template <class T>
bool mozhno_pribavlat_put_ili_net (rek_obhod_matr<int>* source) {
 vector< pair<int, int> > chto_proshli= (* source).set_chto_proshli (); 
 if((!(* source).get_i_tek())&& ((* source).get_j_tek()== N- 1)) {
  return true; 
 }
 return false;            
}
 
 
template <class T>
void izmenenia (rek_obhod_matr<int>* source) {}
 
 
 
int main() {
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 
 //Массив тот самый
 int** array_osn= new int* [M] ;
 
 for (int i= 0; i< M; i++) {
  array_osn[i]= new int[N];
 }
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++) {
   array_osn [i] [j]= 0;
  }
 }
 
 
 //ВЫведем его
 printf ("сам массив:\n");
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++) {
   array_osn[i][j]= i*M+ j;   
   printf ("%d ", array_osn[i][j]);
  }
  printf ("\n");
 };
 
 
 
 rek_obhod_matr<int> obhod (array_osn, M, N, M-1, 0,\
                            _poisk_kletok_<int>,\
                            mozhno_pribavlat_put_ili_net<int>,\
                            izmenenia<int>);
 vector <vector <pair<int, int> > > puti= obhod.set_puti ();
 
 
 printf ("всего путей %d\n", obhod.set_puti().size());
 
 printf ("\nрешение:\n");
 for (int i= 0; i< obhod.set_puti().size(); i++) { 
  for (int j= 0; j< obhod.set_puti()[i].size(); j++)  
   printf ("%d ", obhod[obhod.set_puti()[i][j].first] [obhod.set_puti()[i][j].second]);
  printf ("\n");
  getchar ();
 }
 getchar ();
 return 0;
}
Ну то есть там мне дали задачу и сказали тестировать класс, а я её усложнил. Класс протестировал.

Добавлено через 1 минуту
Вот условие задачи: дана прямоугольная матрица, заполненная числами типа int. Необходимо из левого нижнего угла попасть в правый верхний. Сумма пройденный клеток не должна превышать заданного числа, количество ходов неограниченно. Ходить можно в любую сторону только на одну клетку. В одну и ту же клетку можно заходить сколько угодно раз. Не допускается ход из клетки A в клетку B если ранее уже был совершён такой ход. Вот я так решил с помощью моего класса. Матрица 2x3
0 1 2
3 4 5
Ограничение 25. Даёт 145 вариантов.


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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <windows.h>
#include "rek_obhod_matr.h" 
#include <vector>
#include <numeric> 
#define ogranichenie 25 
#define M  2 
#define N  3 
using namespace std;
 
 
 
template <class T>
bool _poisk_kletok_ (rek_obhod_matr<int>* source, int i_pot, int j_pot) {
 
 int i_tek= (* source).get_i_tek();
 int j_tek= (* source).get_j_tek();
 //Значение текущей клетки
 int znach_tek= (*source)[i_tek][j_tek];
 
 //Вектор пройденых пар
 vector< pair<int, int> > chto_proshli= (* source).set_chto_proshli (); 
 //найдём верхушку этого вектора
 pair <int, int> para;
 if (chto_proshli.size())
  para= make_pair (chto_proshli.back().first, chto_proshli.back().second);
 
  
 //Сумма пройденных клеток; 
 int sum= 0;
 //Вектор пройденных значений
 vector <int> chto_proshli_;
 for (int i= 0; i< chto_proshli.size(); i++)
  chto_proshli_.push_back ((*source)[chto_proshli[i].first][chto_proshli[i].second]);
 
 chto_proshli_.push_back (znach_tek);
 chto_proshli_.push_back ((*source)[i_pot][j_pot]);
 //Сортирнём
 sort (chto_proshli_.begin(), chto_proshli_.end());
 //Убираем повторы
 vector<int>::iterator it= unique (chto_proshli_.begin(), chto_proshli_.end());
 chto_proshli_.resize (it- chto_proshli_.begin());
 //Сама сумма 
 sum= accumulate(chto_proshli_.begin(), chto_proshli_.end(), sum); 
 
 //Это будет вектор пар клеток. Он нужен вот для чего: в одн и ту же клетку зайти допускается.
 //но повторить прыжок- ни в коем случае.
 //прыжок это всегда две клетки. Их и ищем
 
 vector < pair < pair <int, int>, pair <int, int> > > dve_kletki;
 int temp= chto_proshli.size()- 2;
 for (int i= 0; i<= temp; i++) {
  pair <int, int> temp_0 (chto_proshli[i].first, chto_proshli[i].second);    
  pair <int, int> temp_1 (chto_proshli[i+ 1].first, chto_proshli[i+ 1].second);    
  dve_kletki.push_back (pair <pair <int, int>, pair <int, int> > (temp_0, temp_1));
 }    
 
 //Сверху
 if ((i_tek== i_pot+ 1)&& (j_tek== j_pot)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end())
  if (sum<= ogranichenie) 
   return true;
 }
 
 //Снизу
 if ((i_tek== i_pot- 1)&& (j_tek== j_pot)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
  if (sum<= ogranichenie) { 
   return true;
   }
  }
 }
 
 //слева
 if ((i_tek== i_pot)&& (j_tek== j_pot+ 1)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
   if (sum<= ogranichenie) { 
    return true;
   }
  }
 }
 
 //Справа
 if ((i_tek== i_pot)&& (j_tek== j_pot- 1)) {
  pair < pair <int, int>, pair <int, int> > para_ (pair <int, int> (i_tek, j_tek), pair <int, int> (i_pot, j_pot));
  if (find (dve_kletki.begin (), dve_kletki.end(), para_)== dve_kletki.end()) {
   if (sum<= ogranichenie) 
    return true;
  }
 }
 return false;            
}
 
 
template <class T>
bool mozhno_pribavlat_put_ili_net (rek_obhod_matr<int>* source) {
 vector< pair<int, int> > chto_proshli= (* source).set_chto_proshli (); 
 if((!(* source).get_i_tek())&& ((* source).get_j_tek()== N- 1)) {
  return true; 
 }
 return false;            
}
 
 
template <class T>
void izmenenia (rek_obhod_matr<int>* source) {}
 
 
 
int main() {
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 
 //Массив тот самый
 int** array_osn= new int* [M] ;
 
 for (int i= 0; i< M; i++) {
  array_osn[i]= new int[N];
 }
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++) {
   array_osn [i] [j]= 0;
  }
 }
 
 
 //ВЫведем его
 printf ("сам массив:\n");
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++) {
   array_osn[i][j]= i*M+ j;   
   printf ("%d ", array_osn[i][j]);
  }
  printf ("\n");
 };
 
 
 
 rek_obhod_matr<int> obhod (array_osn, M, N, M-1, 0,\
                            _poisk_kletok_<int>,\
                            mozhno_pribavlat_put_ili_net<int>,\
                            izmenenia<int>);
 vector <vector <pair<int, int> > > puti= obhod.set_puti ();
 
 
 printf ("всего путей %d\n", obhod.set_puti().size());
 
 printf ("\nрешение:\n");
 for (int i= 0; i< obhod.set_puti().size(); i++) { 
  for (int j= 0; j< obhod.set_puti()[i].size(); j++)  
   printf ("%d ", obhod[obhod.set_puti()[i][j].first] [obhod.set_puti()[i][j].second]);
  printf ("\n");
  getchar ();
 }
 getchar ();
 return 0;
}
Ну то есть там мне дали задачу и сказали тестировать класс, а я её усложнил. Класс протестировал.
 
Текущее время: 12:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru