Народ , помогите пожалуйста , нужно сделать программу : дана двоичная матрица из 0 и 1 , в рандомной позиции появлятся человечек , которому нужно выйти в правый нижний угол , идти он может только по тем цифрам , на котрой сначала появился (то есть если появился на 1 то только по еденицам). Если выхода нет то нужно вывести на экран что нет выхода . матрица задается рандомно. Программа должна быть сделана при помощи рекурсии .
Заранее спасибо.
hiv
22.03.2007 18:19
Цитата(Positiv @ 22.03.2007 13:58)
Народ , помогите пожалуйста , нужно сделать программу :
Сам чего нибудь пробовал сделать? В принципе сложного нет ничего - просто надо в начале выйти на границу разделяющую 0,1 или границу матрицы, а потом совершать обход либо только по часовой стрелке, либо только против часовой. Если вернешся на то же место где был в начале обхода границы (так и не попав в пункт назначения), то выхода нету. Еще с самого начала можно проверить если в пункте назначения нет той цифры, на которую с самого начала встал человечек, то выхода нету.
positiv
23.03.2007 0:06
мне надо сама процедура поиска пути , хелп
St@senk@
23.03.2007 1:02
Ну смотри. псевдокод функция шаг(х,у) булен начало отметим, что в этой точке мы были. если х=(длина лабиринта) и у=(ширина лабиринта), то результат = Правда, а если нет, то если на севере свободно, то результат = шаг(х,у-1), если нет, то если на западе свободно, то результат = шаг(х+1,у), если нет, то если на юге свободно, то результат = шаг(х,у+1), если нет, то если на востоке свободно, то результат = шаг(х-1,у), если нет, то результат = ложь конец свободно = такая же цифра и мы там не были если результат работы да, то тогда выход есть. А как поиск пути найти, я думаю ты догадаешься
P.S. в алгоритме не уверен.
Алена
23.03.2007 6:06
Цитата
мне надо сама процедура поиска пути
FAQ -> Переборные алгоритмы (чуть-чуть подкорректировать "3) задача о лабиринте")
hiv
23.03.2007 13:27
Цитата(St@senk@ @ 22.03.2007 21:02)
отметим, что в этой точке мы были. если х=0 или у=0 или х=(длина лабиринта) или у=(ширина лабиринта), то результат = Правда, а если нет, то ... P.S. в алгоритме не уверен.
Направление рассуждения абсолютно верное, но не надо отмечать был ты в той или иной точке или не был. Нужно смотреть совпадение координат с первоначальной точкой обхода, когда вышел к границе в самом начале. Более того, нужно учесть, что таких совпадений может быть несколько! И внимательно читаем условие: "человечек , которому нужно выйти в правый нижний угол "
ЗЫ: Просьба к автору темы - поподробней опишите как человечек может ходить?
ДА! Совсем забыл... у человечика должно быть "направление движения" и его все время должно тянуть в какую-то сторону (или по часовой, или против). Т.е. использовать абсолютные понятия север, восток, юг и запад нельзя.
St@senk@
23.03.2007 16:16
ну тогда, алгоритм, который проходит через все доступные точки. пусть закрасить = поднять буленовское значение в этой токе в Правда
Код
процедура шаг начало если не закрашено, то начало закрасить если на севере свободно, то начало шаг на север шаг шаг на юг конец если на юге свободно, то начало шаг на юг шаг шаг на север конец если на запад свободно, то начало шаг на запад шаг шаг на восток конец если на востоке свободно, то начало шаг на восток шаг шаг на запад конец конец конец
Ну а дальше еще сюда прикрутить проверку положения
Positiv
23.03.2007 17:28
человек может ходить только по горизонтали или по вертикали . по диагонали -нельзя. и ходить может только по тем цифрам на которой появился - то есть или по нулям или по еденицам.
St@senk@
23.03.2007 17:57
ну тогда мой последний алгоритм должен работать...
hiv
23.03.2007 22:11
Цитата(St@senk@ @ 23.03.2007 13:57)
ну тогда мой последний алгоритм должен работать...
Скорее вот так он должен работать:
Код
процедура шаг начало если не закрашено, то начало закрасить если не дошли, то начало если на север можно идти и там не закрашено, то начало шаг на север конец если на юг можно идти и там не закрашено, то начало шаг на юг конец если на запад можно идти и там не закрашено, то начало шаг на запад конец если на восток можно идти и там не закрашено, то начало шаг на восток конец конец иначе начало дошли ура! конец конец конец
Но это полный перебор вариантов хождений, если матрица очень большая, то жди переполнения стека! Если матрица большая, то лучше ходить по границе.
Positiv
23.03.2007 22:41
а где в этом алгоритме рекурсия ?
St@senk@
24.03.2007 0:05
Hiv, нет, твой алгоритм отличается от моего и в том псевдо коде я просто, как я уже писал не добавлял проверку местоположения.
Positiv
24.03.2007 14:12
объясните плз подробнее , не совсем понятно , по алгоритму стасенки он вообще будет ходить по крестику !!!
Lapp
24.03.2007 14:40
positv, чем тебя не устроила ссылка Алены? Там все как ты просил, с рекурсией..
Если же хочешь алгоритм "правой/левой руки", то можешь взять тут: Лабиринт - все разложено по элементам, только без рекурсии..
St@senk@
24.03.2007 14:57
Чтобы Ввы мне поверили, то вот реализация моего алгоритма. Delphi
program Project2;
{$APPTYPE CONSOLE}
const n = 5; var lab : array [1..n,1..n] of integer; var labb : array [1..n,1..n] of boolean; var x,y : integer;
function Step : boolean; var res : boolean; begin res:=false; if (x=n) and (y=n) then res:=true else begin if not(labb[x,y]) then begin labb[x,y]:=true; if (y>1) and (lab[x,y-1]=lab[x,y]) then begin dec(y); res:=res or step; inc(y); end; if (y<n) and (lab[x,y+1]=lab[x,y]) then begin inc(y); res:=res or step; dec(y); end; if (x>1) and (lab[x-1,y]=lab[x,y]) then begin dec(x); res:=res or step; inc(x); end; if (x<n) and (lab[x+1,y]=lab[x,y]) then begin inc(x); res:=res or step; dec(x); end; end; end; step:=res; end;
var i,j : integer; begin for i:= 1 to n do begin for j:= 1 to n do begin lab[j,i]:=random(2); write(lab[j,i]); labb[j,i]:=false; end; writeln; end; readln(x,y); write(step); readln; end.
Pascal
program Project2; uses crt; const n = 5; var lab : array [1..n,1..n] of integer; var labb : array [1..n,1..n] of boolean; var x,y : integer;
function Step : boolean; var res : boolean; begin res:=false; if (x=n) and (y=n) then res:=true else begin if not(labb[x,y]) then begin labb[x,y]:=true; if (y>1) and (lab[x,y-1]=lab[x,y]) then begin dec(y); res:=res or step; inc(y); end; if (y<n) and (lab[x,y+1]=lab[x,y]) then begin inc(y); res:=res or step; dec(y); end; if (x>1) and (lab[x-1,y]=lab[x,y]) then begin dec(x); res:=res or step; inc(x); end; if (x<n) and (lab[x+1,y]=lab[x,y]) then begin inc(x); res:=res or step; dec(x); end; end; end; step:=res; end;
var i,j : integer; begin for i:= 1 to n do begin for j:= 1 to n do begin lab[j,i]:=random(2); write(lab[j,i]); labb[j,i]:=false; end; writeln; end; readln(x,y); write(step); readln; end.
Добавлено через 55 сек. Lapp, извини, твоего сообщения не видел.
Positiv
25.03.2007 2:30
'Lapp' . прога по ссылке алены вообще не работает =((
Lapp
25.03.2007 14:09
Цитата(Positiv @ 24.03.2007 22:30)
'Lapp' . прога по ссылке алены вообще не работает =((
Вот это ты зря.. В следующий раз, будь добр, если говоришь, что программа из форумского FAQ не работает - приведи конкретно, что именно не работает и как. Пустые утверждения, не подтвержденные фактами, не принимаются к рассмотрению вообще.. Я проверил программу - она работает. Я вставил в нее случайное задание лабиринта, как в твоем условии, все работает замечательно. Если тебя это интересует, приведи конкретно, что у тебя не работало, и мы продолжим разговор..
Гость
25.03.2007 21:28
когда запускаешь программу алены , так понимаю надо ввести значения , вводи вводил и ничего не произошло хоть до бесконечности вводи =(( может че то недопонял в коде ее ?
St@senk@
25.03.2007 21:29
Там нужно сначала ввести матрицу, а потом координаты видимо ты не ввел нужное количество элементов матрицы и поэтому программа не запустилась.
Добавлено через 1 мин. P.S. Можно не скромный вопрос? Чем мой сурс не устраивает?
Positiv
25.03.2007 21:39
St@senk@ . надо что бы с рекурсией было , а я не знаю как в твою прогу добавить рекурсию
St@senk@
25.03.2007 21:57
Positiv А она там уже есть
Код
res:=res or step;
- Это разве не рекурсия ?
Гость
25.03.2007 22:16
'St@senk@' . точняк , че то я туплю дико после субботы =) . И можно к тбе еще одна просьба напиши пару комментов к своей проге та не всё понятно , не до конца по крайней мере
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.