Сложный алгоритм

← →
Брат (2003-12-17 10:41) [0]

Доброе утро! Помогите добрым советом. Имеется Двумерный массив чисел, среди которых имеются нули. Нужно построить замкнутый цикл по ненулевым числам.
Берем одну ненулевую клетку и смотрим, образовывает ли она цикл с другими, если нет, то берем следующее число.
Как такое сделать? Может кто нибудь делал такой или подобный алгоритм.

← →
Babay (2003-12-17 10:48) [1]

Что значит "смотрим, образовывает ли она цикл с другими" ?

← →
Брат (2003-12-17 11:04) [2]

> Что значит "смотрим, образовывает ли она цикл с другими"
> ?

Выберем из таблицы несколько клеток и расплоложим их друг за другом в определенном порядке: c1,...,cr. Этот набор клеток называется цепью, если любые две соседние клетки в нем находятся на одной линии, а любые три соседние клетки ни одной линии не принадлежат. Если первая и последняя клетки цепи принадлежат одной линии, то цепь называется циклом.

← →
stud (2003-12-17 11:06) [3]

это вроде нахождения маршрута?

← →
Брат (2003-12-17 11:08) [4]

подобное этому
незнаю как мне реализовать этот алгоритм.

← →
Babay (2003-12-17 11:16) [5]

Еще больше вопросов

любые две соседние клетки в нем находятся на одной линии ?

три соседние клетки ни одной линии не принадлежат ?

Может я непонятливый но чего то неясно. Мож пример нарисуешь?
типа это цикл это нет.

c1,...,cr - это клетки с координатаими X,Y ?

← →
stud (2003-12-17 11:16) [6]

ну так и бери одну клетку и проверяй клетки вокруг нее. нашел ту которая удовлетворяет твоим условиям переходи на нее и повторяй все сначала и т.д.

← →
ИдиотЪ (2003-12-17 11:19) [7]

бесконечный цикл или как ?

← →
Брат (2003-12-17 11:23) [8]

> Babay ©

Например есть массив:
i/j 0 1 2 - это индексы массива
0 4 0 7
1 5 0 3
2 0 6 2
3 9 8 0
В этом примере есть 3 цикла
1)4,5,3,7
2)4,9,8,6,2,7
3)5,9,8,6,2,3

Надеюсь, понятно

← →
Брат (2003-12-17 11:25) [9]

> ну так и бери одну клетку и проверяй клетки вокруг нее.
> нашел ту которая удовлетворяет твоим условиям переходи на
> нее и повторяй все сначала и т.д.

это непросто, вот я и спрашиваю, делал ли кто-то нечто подобное...

← →
Брат (2003-12-17 11:28) [10]

> бесконечный цикл или как ?

здесь подразумевается не обычный цикл типа for..to..do
а цикл из клеток двумерного массива

← →
stud (2003-12-17 11:29) [11]

почему не просто?
начинаеш например с 0.0 - если 1.0<>0 значит смотрим - 2.0=0 проверяеш крайнюю клетку

← →
stud (2003-12-17 11:31) [12]

и наверное не цикл из клеток двумерного массива а рекурсивный

← →
Брат (2003-12-17 11:35) [13]

> почему не просто?
> начинаеш например с 0.0 - если 1.0<>0 значит смотрим - 2.0=0
> проверяеш крайнюю клетку

я попробую, но тут придется нелегко, нужно все учесть...

> и наверное не цикл из клеток двумерного массива а рекурсивный

в смысле рекурсивный?

← →
stud (2003-12-17 11:51) [14]

рекурсивный - это процедура каторая вызывает саму себя

← →
Брат (2003-12-17 11:58) [15]

> рекурсивный - это процедура каторая вызывает саму себя

я понял
но как єто применить к моему примеру

← →
stud (2003-12-17 12:03) [16]

хотя если у тебя максимум три клетки надо проверять наверное смысла в рекурсии и нету.

← →
Брат (2003-12-17 12:15) [17]

у меня максимум будет 10 на 10 клеток
я не могу себе представить как єто сделать...
1) беру клетку (0,0) если она =0 беру (0,1) дальше мне нужно проверять есть ли в этой строке есче числа если нету оставляю клетку, беру клетку (1,0)... и т.д.? правильно я думаю?

← →
stud (2003-12-17 12:41) [18]

тебе нужно относительно текущей клетки проверять две соседние клетки.
а вообще постоновку задачи нужно подробнее

← →
Брат (2003-12-17 13:01) [19]

а как можна из всех имеющихся чисел в матрице посоставлять множества различных содержаний?

← →
stud (2003-12-17 13:03) [20]

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

← →
Брат (2003-12-17 13:22) [21]

я вот тут подумал и решил что наверное проще сделать функцию, которая будет брать две клетки и проверять лежат ли они на одной линии (т.е. находятся в одной строке или в одном столбце).

А затем сделать выборку, которая будет формировать массивы индексов i,j ненулевых клеток. Но как сделать чтобы формировались множества ненулевых клеток?

А затем с помощью вышеописаной функции проверять пары клеток лежат ли они на одной линии...

Но, проблема в том как построить множества ненулевых клеток...

А насчет постановки задачи - это транспортная задача (ее постановка здоровая очень если учитывать все ньюансы)... а я пытаюсь реализовать так называемый алгоритм "потенциалов"...

← →
stud (2003-12-17 13:49) [22]

ну что-то слышал))))
я писал программу нахождения отпимального маршрута (курсовик)
зачем тебе их строить?
по мере нахождения своих линий записываеш информацию о них и после отработки выводиш на экран если нужно. да, а если у тебя три клетки подряд на одной линии - это что значить будет?

← →
Брат (2003-12-17 14:20) [23]

три клетки подряд в цикл входить не будут, смогут войти только первая и вторая...
я кстати вот тоже пишу курсак по "Методам исследования операций" :))
ок, я учту твои советы

Сложный алгоритм Найти похожие ветки