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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
clozer
Сообщений: n/a
#1

Нахождение всех возможных путей для спуска с вершины матрицы - C++

04.07.2012, 20:56. Просмотров 803. Ответов 3
Метки нет (Все метки)

имеется массив вида

1 2 х х
3 4 5 х
6 7 8 9

высота массива = 3
количество вершин = 2

более удобное графическое представление
___1__2
__3__4__5
6__7__8__9

нужно получить все возможные пути спуска с вершин массива к его низу, с учетом того, что спуск проходит по диагонали.

т.е. валиден путь [0, 0, 0] для значений 1, 3 и 6. но не валиден [0, 0, 2] для веришин 1, 3 и 8

нужно получить значения типа:
[0, 0, 0]
[0, 0, 1]
[0, 1, 1]
[0, 1, 2]
[1, 1, 1]
...

помогите с алгоритмом. на крайний случай сойдет и вариант полного перебора, типа:
[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 1, 0]
[0, 1, 1]
....
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2012, 20:56     Нахождение всех возможных путей для спуска с вершины матрицы
Посмотрите здесь:

Нахождение всех возможных путей - C++
дана матрица, нужно с 1,1(Start) обоити всеми возможными путями к А,А(Finish). здвигаться можно так если находимся в (х,у) : (х+1,у);...

Нахождение всех путей в графе от одной вершины до другой обходом в ширину - C++
Здравствуйте, уважаемые любители и профессионалы программирования. Нужна мне помощь в такой задаче. Необходимо найти для любого...

Нахождение всех путей ориетированного графа - C++
Есть вектор с ребрами vector< vector<int> > g; Как найти все пути методом поиска в глубину например? Количество вершин, из каких в...

Нахождение всех возможных вариантов сумм, если такой суммы нет найти приближенное значение - C++
Всем привет! Написал программу для нахождения всех возможных сумму. Но нужно еще, что бы программа искала и приближенное к этой сумме. ...

Алгоритм для поиска всех путей между 2 вершинами графа - C++
Здравствуйте, возник вопрос какой алгоритм необходимо использовать для поиска всех путей, между 2 вершинами графа.

Можно ли создать программу для перебора всех возможных комбинаций цифр заданного большого числа? - C++
Здравствуйте. Я хочу узнать можно ли сделать программу для перебора всех возможных комбинаций из 30 чисел Пример:...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thirteen
32 / 32 / 4
Регистрация: 04.07.2012
Сообщений: 50
05.07.2012, 02:50     Нахождение всех возможных путей для спуска с вершины матрицы #2
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
#include <iostream>
#define SIZE 4
 
using namespace std;
 
void Search(int [SIZE][SIZE], int, int, int [SIZE]);
int main()
{
    int Matrix[SIZE][SIZE], String[SIZE];
    for(int i = 0; i < SIZE; i++)
    {
        String[i] = 0;
    }
    Matrix[0][0]=1; Matrix[0][1]=2; Matrix[0][2]=0; Matrix[0][3]=0;
    Matrix[1][0]=3; Matrix[1][1]=4; Matrix[1][2]=5; Matrix[1][3]=0;
    Matrix[2][0]=6; Matrix[2][1]=7; Matrix[2][2]=8; Matrix[2][3]=9;
 
    for(int i = 0; i < SIZE; i++)
    {
        if(Matrix[0][i] != 0)
        {
            String[0] = i;
            Search(Matrix, 0, i, String);
        }
    }
    return 0;
}
 
void Search(int Matrix[4][4], int Row, int Column, int String[4])
{
    //Проверяем элемент слева.
    if(Column - 1 >= 0 && Matrix[Row+1][Column-1]!=0 && Row < SIZE)
    {
        //Если он есть, записываем его в массив String
        String[Row+1] = Column-1;
        //Рекурсивно переходим к левому элементу
        Search(Matrix, Row+1, Column-1, String);
    }
    //Проверяем элемент снизу
    if(Matrix[Row+1][Column]!=0 && Row < SIZE)
    {
        //Если он есть, записываем его в массив String
        String[Row+1] = Column;
        //Рекурсивно переходим к нижнему элементу
        Search(Matrix, Row+1, Column, String);
    }
    //Проверяем элемент справа
    if(Matrix[Row+1][Column+1]!=0 && Row < SIZE)
    {
        //Если он есть, записываем в массив.
        String[Row+1] = Column+1;
        //Рекурсивно переходим к правому элементу
        Search(Matrix, Row+1, Column+1, String);
    }
    //Дошли до конца - выводим.
    if(Row==2)
    {
        String[Row] = Column;
        for(int i = 0; i < SIZE-1; i++)
            cout << String[i];
        cout << endl;
    }
    //Дальше происходит размотка стека вызовов.
}
Алгоритм рекурсивный.
Можно решить как-то более интеллектуально, если ввести структуру с указателями на диагональные элементы. Если интересно, могу написать.
И переход к нижнему элементу наверное лишний... Ну пусть будет. Убрать недолго, если что.
clozer
Сообщений: n/a
06.07.2012, 00:18     Нахождение всех возможных путей для спуска с вершины матрицы #3
спасибо за ответ. подправил алгоритм под свой код. происходт обращение за пределы массива
текущий код:

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
#include <iostream>
#include <fstream>
#include <cstdio>
#include <string>
#include <stdlib.h>
#include <sstream>
 
using namespace std;
 
void Search(int **, int, int, int *, int);
 
int main()
{
  FILE *in, *out;
  in=fopen("data.in","r");
  int arr_size;
  fscanf(in,"%d",&arr_size);
 
  int** data = new int*[arr_size ];
  for(int i = 0; i < arr_size; i++)
      data[i] = new int[arr_size + 1];
 
  for(i = 0; i < arr_size; i++)
  {
    for(int j = 0; j < arr_size + 1; j++)
    {
      data[i][j] = 0;
    }
  }
 
  for(i=0; i < arr_size; i++)
  {
    for(int j = 0; j < i + 2; j++)
    {
      int number;
      fscanf(in,"%d",&number);
      data[i][j] = number;
    }
  }
 
  int* temp_indexes = new int[arr_size];
 
  for(i = 0; i < arr_size; i++)
  {
    temp_indexes[i] = 0;
  }
 
  for(i = 0; i < arr_size; i++)
  {
    if(data[0][i] != 0)
    {
      temp_indexes[0] = i;
      Search(data, 0, i, temp_indexes, arr_size);
    }
  }
  return 0;
}
 
void Search(int **Matrix, int Row, int Column, int *String, int size)
 
{
  cout << "row " << Row + 1 << endl;
  cout << "column " << Column - 1 << endl;
  if(Column - 1 >= 0 && Matrix[Row+1][Column-1]!=0 && Row < size)
  {
    String[Row+1] = Column-1;
    Search(Matrix, Row+1, Column-1, String, size);
  }
  if(Matrix[Row+1][Column]!=0 && Row < size)
  {
    String[Row+1] = Column;
    Search(Matrix, Row+1, Column, String, size);
  }
  if(Matrix[Row+1][Column+1]!=0 && Row < size)
  {
    String[Row+1] = Column+1;
    Search(Matrix, Row+1, Column+1, String, size);
  }
  if(Row==2)
  {
    String[Row] = Column;
    for(int i = 0; i < size-1; i++)
      cout << String[i];
    cout << endl;
  }
}
data.in:

3
1 2
3 4 5
6 7 8 9

помогите найти ошибку, пожалуйста

Добавлено через 45 минут
заметил свою ошибку. нужно было размер делать на +1 больше.
и вместо
C++
1
if(Row==2)
нужно
C++
1
if(Row==size - 2)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2012, 00:19     Нахождение всех возможных путей для спуска с вершины матрицы
Еще ссылки по теме:

Нахождение К путей Минимальной суммарной длины Во взвешенном графе с неотрицательными весами(Алгоритм Йена). - C++
Нахождение К путей Минимальной суммарной длины Во взвешенном графе с неотрицательными весами(Алгоритм Йена). Вот тут у меня есть код...

Обход всех путей в графе - C++
Помогите с алгоритмом поиска всех путей на графе.Обыскал весь инет робочего не нашол

Сортировка всех возможных комбинаций 4 из 8 - C++
Задача состоит в том, что бы сложить 4 элемента массива, который состоит из 8 элементов, во всех возможных комбинациях int array; //...

Поиск всех возможных A и B из формулы - C++
Есть задание: любое натуральное число N (N &gt; 7). Исходя из формулы N = 3a+5b получить все возможные A и B . Решил я это следующим...

Поиск всех различных путей в графе - C++
Задан ориентированный ациклический связный граф. Найдите различные пути, по которым из вершины под номером 1 можно добраться до вершины с...

Реализовать перебор всех возможных IP-адресов (С++) - C++
Реализовать перебор всех возможных IP-адресов, начиная с 0.0.0.0, заканчивая 255.255.255.0. (проще говоря перебор всех возможных комбинаций...


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

Или воспользуйтесь поиском по форуму:
Thirteen
32 / 32 / 4
Регистрация: 04.07.2012
Сообщений: 50
06.07.2012, 00:19     Нахождение всех возможных путей для спуска с вершины матрицы #4
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
#include <iostream>
#include <fstream>
#include <cstdio>
#include <string>
#include <stdlib.h>
#include <sstream>
 
using namespace std;
 
void Search(int **, int, int, int *, int);
 
int main()
{
  FILE *in, *out;
  in=fopen("data.in","r");
  int arr_size;
  fscanf(in,"%d",&arr_size);
 
  int** data = new int*[arr_size ];
  for(int i = 0; i < arr_size; i++)
      data[i] = new int[arr_size + 1];
 
  for(int i = 0; i < arr_size; i++)
  {
    for(int j = 0; j < arr_size + 1; j++)
    {
      data[i][j] = 0;
    }
  }
 
  for(int i=0; i < arr_size; i++)
  {
    for(int j = 0; j < i + 2; j++)
    {
      int number;
      fscanf(in,"%d",&number);
      data[i][j] = number;
    }
  }
 
  int* temp_indexes = new int[arr_size];
 
  for(int i = 0; i < arr_size; i++)
  {
    temp_indexes[i] = 0;
  }
 
for(int i = 0; i < 3; i++)
{
    for(int j = 0; j < 3; j++)
        cout << data[i][j] << ' ';
    cout << endl;
}
 
  for(int i = 0; i < arr_size; i++)
  {
    if(data[0][i] != 0)
    {
      temp_indexes[0] = i;
      Search(data, 0, i, temp_indexes, arr_size);
    }
  }
  return 0;
}
 
void Search(int **Matrix, int Row, int Column, int *String, int size)
 
{
  //cout << "row " << Row + 1 << endl;
  //cout << "column " << Column << endl;
  //cout << "element = " << Matrix[Row][Column] << endl;
  if(Row==2)
  {
    String[Row] = Column;
    for(int i = 0; i < size; i++)
      cout << String[i];
    cout << endl;
      return;
  }
  if(Column - 1 >= 0 && Matrix[Row+1][Column-1]!=0 && Row < size)
  {
    String[Row+1] = Column-1;
    Search(Matrix, Row+1, Column-1, String, size);
  }
  if(Matrix[Row+1][Column]!=0 && Row < size)
  {
    String[Row+1] = Column;
    Search(Matrix, Row+1, Column, String, size);
  }
  if(Matrix[Row+1][Column+1]!=0 && Row < size)
  {
    String[Row+1] = Column+1;
    Search(Matrix, Row+1, Column+1, String, size);
  }
}
Мой косяк. Нужно было поставить проверку на то, что ряд последний, в начало. И явно передавать управление.
А так, видимо происходило обращение к элементу несуществующего ряда, вот и ошибка сегментирования.
Yandex
Объявления
06.07.2012, 00:19     Нахождение всех возможных путей для спуска с вершины матрицы
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru