Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.70/20: Рейтинг темы: голосов - 20, средняя оценка - 4.70
demik991
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 15
1

Нахождение всех возможных путей

08.01.2012, 18:58. Просмотров 3738. Ответов 14
Метки нет (Все метки)

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

толлько не советуйте гоогль, я знаю там есть и я находил статьи
HTML5
1
2
http://www.opita.net/node/481
http://forum.algolist.ru/algorithm-graph/50-poisk-vseh-vozmojnyh-putei-iz-odnoi-vershiny-do-drugoi.html
ладно если пощитаете нужнм можете и закрть тему.
0
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2012, 18:58
Ответы с готовыми решениями:

Нахождение всех возможных путей для спуска с вершины матрицы
имеется массив вида 1 2 х х 3 4 5 х 6 7 8 9 ...

Нахождение всех путей ориетированного графа
Есть вектор с ребрами vector< vector<int> > g; Как найти все пути методом...

Нахождение всех путей в графе от одной вершины до другой обходом в ширину
Здравствуйте, уважаемые любители и профессионалы программирования. Нужна мне...

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

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

14
Stochfard
4 / 4 / 0
Регистрация: 23.12.2011
Сообщений: 79
08.01.2012, 19:04 2
не понял суть, как двигать то надо ?
точнее как вывести движение ?
0
demik991
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 15
08.01.2012, 19:10  [ТС] 3
если находимся в (х,у) то здвигаться можно так: (х+1,у); (х,у+1); (х+1;у+1).
а с тем как надо у меня у самого проблема
0
soon
2546 / 1311 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
08.01.2012, 19:12 4
Нужно вывести сами пути, или количество?
0
demik991
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 15
08.01.2012, 19:15  [ТС] 5
количество надо, но без первого тут не обойтись как я понимаю
0
soon
2546 / 1311 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
08.01.2012, 19:18 6
Если не напутал ничего.
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
#include <iostream>
#include <iomanip>
 
int main()
{
    const int rows = 5, cols = 5;
    int arr[rows][cols];
    int rPos, cPos;
    std::cin >> rPos >> cPos;
    for(int j = 0; j < cPos; ++j)
        arr[0][j] = 1;
    for(int i = 1; i < rPos; ++i)
    {
        arr[i][0] = 1;
        for(int j = 1; j < cPos; ++j)
            arr[i][j] = arr[i - 1][j] + arr[i][j - 1] + arr[i - 1][j - 1];
    }
    for(int i = 0; i < rPos; ++i)
    {
        for(int j = 0; j < cPos; ++j)
            std::cout << std::setw(4) << arr[i][j];
        std::cout << std::endl;
    }
    return 0;
}
По сути нужно выводить только arr[rPos][cPos]. Таблица выводится для проверки.
1
demik991
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 15
09.01.2012, 02:48  [ТС] 7
а вот вопросец, если можно, еще один, а если, например, рпоз=15, а кпоз=100 то что в таком случае делать? дайте просто совет
0
soon
2546 / 1311 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.01.2012, 08:27 8
Увеличить размер матрицы. Ее можно сделать динамической под размеры rPos и cPos. Я просто показал алгоритм.
0
thick_int
Заблокирован
09.01.2012, 09:15 9
Цитата Сообщение от demik991 Посмотреть сообщение
количество надо
Очень даже можно обойтись. Число путей считается легко в уме.
Рассмотрим матрицу размером NxN.

Сперва в этой матрице рассмотрим последнюю строку и последний столбец. Эти элементы ничего не дают сс точки зрения увеличения имеющихся путей. Поэтому смело в них ставим 0.

Теперь рассмотрим все остальные элементы, кроме элемента a(0, 0). Из каждого такого элемента можно (в соответствии с имеющейся схемой прохода) двинуться в три соседние точки. Следовательно, каждая из этих точек продолжает один из имеющихся путей и порождает еще два новых. Поэтому смело ставим в каждую из этих точек по 2.

Ну и наконец точка a(0, 0). Эта точка порождает ровно три маршрута. Поэтому ставим также в нее 2, а единичку скромно записываем в сторонке.

Оссталось сложить все элементы полученной матрицы и добавить к полученной сумме отдельно стоящую единицу, что как нетрудно видеть равно 2(N-1)^2+1.
1
soon
2546 / 1311 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.01.2012, 09:24 10
Цитата Сообщение от thick_int Посмотреть сообщение
2(N-1)^2+1.
По вашей формуле для поля 3*3 получится 9. А там 13 путей.
0
thick_int
Заблокирован
09.01.2012, 19:16 11
Цитата Сообщение от soon Посмотреть сообщение
По вашей формуле для поля 3*3 получится 9. А там 13 путей.
По всей видимости Вы совершенно правы (не знаю как насчет правильно или нет насчет 13 для поля 3 х 3) в том, что в моих рассуждениях есть одна досадная ошибка, которая состоит в том, что если путь учтен один раз, как продолженный, то все последующие точки должны учитываться, как абсолютно новые пути.

Тем не менее, задача интересная и заслуживает того, чтобы над ней поломать голову.
0
demik991
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 15
09.01.2012, 20:20  [ТС] 12
Цитата Сообщение от soon Посмотреть сообщение
Увеличить размер матрицы. Ее можно сделать динамической под размеры rPos и cPos. Я просто показал алгоритм.
c алгоритмом все понятно. насколько понял динамической ето не константи, а задавать размер с клавиатуры. тогда понятно. но дело в том что количество путей, например, в точке (15,100) выдает интересные результаты, видимо из-за превышения размера int. что делать в таких случаях. занасить число в две ячейки типа int (например деситки в int a, а единици в int b) или есть какой другой итерестный способ? и вообще где и как хранить числа больше 2^32.
0
soon
2546 / 1311 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.01.2012, 20:23 13
demik991, как double объявите.
0
demik991
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 15
09.01.2012, 20:43  [ТС] 14
Цитата Сообщение от soon Посмотреть сообщение
как double
а если порядка 2^100 то делать как я писал выше
0
soon
2546 / 1311 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.01.2012, 21:16 15
demik991, много способов. Зависит от точного описания задачи. Я полагаю, нужно будет выводить по модулю. Если нет, то можно реализовать класс со строками для длинной арифметики, использовать несколько ячеек в массиве для одного числа и т.д.. Но я все-таки думаю, что double должно хватить. А если боитесь, что массив будет занимать много памяти, то можно выделять не N*N а 2*N. Ну и алгоритм переделать чуть-чуть.
0
09.01.2012, 21:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.01.2012, 21:16

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

Сортировка всех возможных комбинаций 4 из 8
Задача состоит в том, что бы сложить 4 элемента массива, который состоит из 8...

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


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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