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

@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. Ну и алгоритм переделать чуть-чуть.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 31.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@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