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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.90
demik991
 Аватар для demik991
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 15
08.01.2012, 18:58     Нахождение всех возможных путей #1
дана матрица, нужно с 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
ладно если пощитаете нужнм можете и закрть тему.
Изображения
 
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Stochfard
4 / 4 / 1
Регистрация: 23.12.2011
Сообщений: 79
08.01.2012, 19:04     Нахождение всех возможных путей #2
не понял суть, как двигать то надо ?
точнее как вывести движение ?
demik991
 Аватар для demik991
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 15
08.01.2012, 19:10  [ТС]     Нахождение всех возможных путей #3
если находимся в (х,у) то здвигаться можно так: (х+1,у); (х,у+1); (х+1;у+1).
а с тем как надо у меня у самого проблема
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
08.01.2012, 19:12     Нахождение всех возможных путей #4
Нужно вывести сами пути, или количество?
demik991
 Аватар для demik991
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 15
08.01.2012, 19:15  [ТС]     Нахождение всех возможных путей #5
количество надо, но без первого тут не обойтись как я понимаю
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 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]. Таблица выводится для проверки.
demik991
 Аватар для demik991
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 15
09.01.2012, 02:48  [ТС]     Нахождение всех возможных путей #7
а вот вопросец, если можно, еще один, а если, например, рпоз=15, а кпоз=100 то что в таком случае делать? дайте просто совет
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.01.2012, 08:27     Нахождение всех возможных путей #8
Увеличить размер матрицы. Ее можно сделать динамической под размеры rPos и cPos. Я просто показал алгоритм.
thick_int
Заблокирован
09.01.2012, 09:15     Нахождение всех возможных путей #9
Цитата Сообщение от demik991 Посмотреть сообщение
количество надо
Очень даже можно обойтись. Число путей считается легко в уме.
Рассмотрим матрицу размером NxN.

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

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

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

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

Тем не менее, задача интересная и заслуживает того, чтобы над ней поломать голову.
demik991
 Аватар для 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.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.01.2012, 20:23     Нахождение всех возможных путей #13
demik991, как double объявите.
demik991
 Аватар для demik991
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 15
09.01.2012, 20:43  [ТС]     Нахождение всех возможных путей #14
Цитата Сообщение от soon Посмотреть сообщение
как double
а если порядка 2^100 то делать как я писал выше
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.01.2012, 21:16     Нахождение всех возможных путей
Еще ссылки по теме:

C++ Обход всех путей в графе
Нахождение всех путей в графе от одной вершины до другой обходом в ширину C++
C++ Сортировка всех возможных комбинаций 4 из 8

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

Или воспользуйтесь поиском по форуму:
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.01.2012, 21:16     Нахождение всех возможных путей #15
demik991, много способов. Зависит от точного описания задачи. Я полагаю, нужно будет выводить по модулю. Если нет, то можно реализовать класс со строками для длинной арифметики, использовать несколько ячеек в массиве для одного числа и т.д.. Но я все-таки думаю, что double должно хватить. А если боитесь, что массив будет занимать много памяти, то можно выделять не N*N а 2*N. Ну и алгоритм переделать чуть-чуть.
Yandex
Объявления
09.01.2012, 21:16     Нахождение всех возможных путей
Ответ Создать тему
Опции темы

Текущее время: 16:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru