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

@demik991 · Регистрация: 18.12.2011

Студворк — интернет-сервис помощи студентам

дана матрица, нужно с 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 · 08.01.2012, 19:04

не понял суть, как двигать то надо ?
точнее как вывести движение ?

@demik991 · 08.01.2012, 19:10 **[ТС]**

если находимся в (х,у) то здвигаться можно так: (х+1,у); (х,у+1); (х+1;у+1).
а с тем как надо у меня у самого проблема

@soon · 08.01.2012, 19:12

Нужно вывести сами пути, или количество?

@demik991 · 08.01.2012, 19:15 **[ТС]**

количество надо, но без первого тут не обойтись как я понимаю

@soon · 08.01.2012, 19:18

Если не напутал ничего.

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 · 09.01.2012, 02:48 **[ТС]**

а вот вопросец, если можно, еще один, а если, например, рпоз=15, а кпоз=100 то что в таком случае делать? дайте просто совет

@soon · 09.01.2012, 08:27

Увеличить размер матрицы. Ее можно сделать динамической под размеры rPos и cPos. Я просто показал алгоритм.

@thick_int · 09.01.2012, 09:15

Сообщение от demik991

количество надо

Очень даже можно обойтись. Число путей считается легко в уме.
Рассмотрим матрицу размером NxN.

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

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

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

Оссталось сложить все элементы полученной матрицы и добавить к полученной сумме отдельно стоящую единицу, что как нетрудно видеть равно 2(N-1)^2+1.

@soon · 09.01.2012, 09:24

Сообщение от thick_int

2(N-1)^2+1.

По вашей формуле для поля 3*3 получится 9. А там 13 путей.

@thick_int · 09.01.2012, 19:16

Сообщение от soon

По вашей формуле для поля 3*3 получится 9. А там 13 путей.

По всей видимости Вы совершенно правы (не знаю как насчет правильно или нет насчет 13 для поля 3 х 3) в том, что в моих рассуждениях есть одна досадная ошибка, которая состоит в том, что если путь учтен один раз, как продолженный, то все последующие точки должны учитываться, как абсолютно новые пути.

Тем не менее, задача интересная и заслуживает того, чтобы над ней поломать голову.

@demik991 · 09.01.2012, 20:20 **[ТС]**

Сообщение от soon

Увеличить размер матрицы. Ее можно сделать динамической под размеры rPos и cPos. Я просто показал алгоритм.

c алгоритмом все понятно. насколько понял динамической ето не константи, а задавать размер с клавиатуры. тогда понятно. но дело в том что количество путей, например, в точке (15,100) выдает интересные результаты, видимо из-за превышения размера int. что делать в таких случаях. занасить число в две ячейки типа int (например деситки в int a, а единици в int b) или есть какой другой итерестный способ? и вообще где и как хранить числа больше 2^32.

@soon · 09.01.2012, 20:23

demik991, как double объявите.

@demik991 · 09.01.2012, 20:43 **[ТС]**

Сообщение от soon

как double

а если порядка 2^100 то делать как я писал выше

@soon · 09.01.2012, 21:16

demik991, много способов. Зависит от точного описания задачи. Я полагаю, нужно будет выводить по модулю. Если нет, то можно реализовать класс со строками для длинной арифметики, использовать несколько ячеек в массиве для одного числа и т.д.. Но я все-таки думаю, что double должно хватить. А если боитесь, что массив будет занимать много памяти, то можно выделять не N*N а 2*N. Ну и алгоритм переделать чуть-чуть.

Новые блоги и статьи Все статьи Все блоги /
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере нетипового документа выдачи шин для спецтехники с табличной частью, разработанного в конфигурации КА2. Номеклатура. . .

@Stochfard 4 / 4 / 0 Регистрация: 23.12.2011 Сообщений: 80
	08.01.2012, 19:04
	не понял суть, как двигать то надо ? точнее как вывести движение ? 0

@demik991 0 / 0 / 0 Регистрация: 18.12.2011 Сообщений: 15
	08.01.2012, 19:10 [ТС]
	если находимся в (х,у) то здвигаться можно так: (х+1,у); (х,у+1); (х+1;у+1). а с тем как надо у меня у самого проблема 0

@soon 2554 / 1319 / 178 Регистрация: 09.05.2011 Сообщений: 3,086 Записей в блоге: 1
	08.01.2012, 19:12
	Нужно вывести сами пути, или количество? 0

@demik991 0 / 0 / 0 Регистрация: 18.12.2011 Сообщений: 15
	08.01.2012, 19:15 [ТС]
	количество надо, но без первого тут не обойтись как я понимаю 0

@demik991 0 / 0 / 0 Регистрация: 18.12.2011 Сообщений: 15
	09.01.2012, 02:48 [ТС]
	а вот вопросец, если можно, еще один, а если, например, рпоз=15, а кпоз=100 то что в таком случае делать? дайте просто совет 0

@soon 2554 / 1319 / 178 Регистрация: 09.05.2011 Сообщений: 3,086 Записей в блоге: 1
	09.01.2012, 08:27
	Увеличить размер матрицы. Ее можно сделать динамической под размеры rPos и cPos. Я просто показал алгоритм. 0

@soon 2554 / 1319 / 178 Регистрация: 09.05.2011 Сообщений: 3,086 Записей в блоге: 1
	09.01.2012, 20:23
	demik991, как double объявите. 0

@soon 2554 / 1319 / 178 Регистрация: 09.05.2011 Сообщений: 3,086 Записей в блоге: 1
	09.01.2012, 21:16
	demik991, много способов. Зависит от точного описания задачи. Я полагаю, нужно будет выводить по модулю. Если нет, то можно реализовать класс со строками для длинной арифметики, использовать несколько ячеек в массиве для одного числа и т.д.. Но я все-таки думаю, что double должно хватить. А если боитесь, что массив будет занимать много памяти, то можно выделять не NN а 2N. Ну и алгоритм переделать чуть-чуть. 0