IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> прохождение лабиринта с помощью рекурсии, бинарная матрица
сообщение
Сообщение #1


Гость






Доброго времени суток !!


Народ , помогите пожалуйста , нужно сделать программу :
дана двоичная матрица из 0 и 1 , в рандомной позиции появлятся человечек , которому нужно выйти в правый нижний угол , идти он может только по тем цифрам , на котрой сначала появился (то есть если появился на 1 то только по еденицам). Если выхода нет то нужно вывести на экран что нет выхода . матрица задается рандомно.
Программа должна быть сделана при помощи рекурсии .



Заранее спасибо.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 660
Пол: Мужской
Реальное имя: Михаил

Репутация: -  11  +


Цитата(Positiv @ 22.03.2007 13:58) *
Народ , помогите пожалуйста , нужно сделать программу :
Сам чего нибудь пробовал сделать?
В принципе сложного нет ничего - просто надо в начале выйти на границу разделяющую 0,1 или границу матрицы, а потом совершать обход либо только по часовой стрелке, либо только против часовой. Если вернешся на то же место где был в начале обхода границы (так и не попав в пункт назначения), то выхода нету. Еще с самого начала можно проверить если в пункте назначения нет той цифры, на которую с самого начала встал человечек, то выхода нету.


--------------------
Никогда не жадничай. Свои проблемы с любовью дари людям!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






мне надо сама процедура поиска пути , хелп
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 48
Пол: Мужской
Реальное имя: Максим

Репутация: -  1  +


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

P.S. в алгоритме не уверен.

Сообщение отредактировано: St@senk@ -


--------------------
Три пути ведут к знанию: путь размышления - это путь самый благородный, путь подражания - это путь самый легкий и путь опыта - это путь самый горький.
Конфуций
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата
мне надо сама процедура поиска пути
FAQ -> Переборные алгоритмы
(чуть-чуть подкорректировать "3) задача о лабиринте")
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Профи
****

Группа: Пользователи
Сообщений: 660
Пол: Мужской
Реальное имя: Михаил

Репутация: -  11  +


Цитата(St@senk@ @ 22.03.2007 21:02) *
отметим, что в этой точке мы были.
если х=0 или у=0 или х=(длина лабиринта) или у=(ширина лабиринта), то результат = Правда, а если нет, то
...
P.S. в алгоритме не уверен.
Направление рассуждения абсолютно верное, но не надо отмечать был ты в той или иной точке или не был. Нужно смотреть совпадение координат с первоначальной точкой обхода, когда вышел к границе в самом начале. Более того, нужно учесть, что таких совпадений может быть несколько!
И внимательно читаем условие: "человечек , которому нужно выйти в правый нижний угол "

ЗЫ: Просьба к автору темы - поподробней опишите как человечек может ходить?

ДА! Совсем забыл... у человечика должно быть "направление движения" и его все время должно тянуть в какую-то сторону (или по часовой, или против). Т.е. использовать абсолютные понятия север, восток, юг и запад нельзя.

Сообщение отредактировано: hiv -


--------------------
Никогда не жадничай. Свои проблемы с любовью дари людям!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 48
Пол: Мужской
Реальное имя: Максим

Репутация: -  1  +


ну тогда, алгоритм, который проходит через все доступные точки.
пусть закрасить = поднять буленовское значение в этой токе в Правда

Код
процедура шаг
начало
если не закрашено, то начало
  закрасить
  если на севере свободно, то начало
   шаг на север
   шаг
   шаг на юг
  конец
  если на юге свободно, то начало
   шаг на юг
   шаг
   шаг на север
  конец
  если на запад свободно, то начало
   шаг на запад
   шаг
   шаг на восток
  конец
  если на востоке свободно, то начало
   шаг на восток
   шаг
   шаг на запад
  конец
конец
конец

Ну а дальше еще сюда прикрутить проверку положения


--------------------
Три пути ведут к знанию: путь размышления - это путь самый благородный, путь подражания - это путь самый легкий и путь опыта - это путь самый горький.
Конфуций
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






человек может ходить только по горизонтали или по вертикали . по диагонали -нельзя. и ходить может только по тем цифрам на которой появился - то есть или по нулям или по еденицам.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 48
Пол: Мужской
Реальное имя: Максим

Репутация: -  1  +


ну тогда мой последний алгоритм должен работать...


--------------------
Три пути ведут к знанию: путь размышления - это путь самый благородный, путь подражания - это путь самый легкий и путь опыта - это путь самый горький.
Конфуций
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Профи
****

Группа: Пользователи
Сообщений: 660
Пол: Мужской
Реальное имя: Михаил

Репутация: -  11  +


Цитата(St@senk@ @ 23.03.2007 13:57) *
ну тогда мой последний алгоритм должен работать...
Скорее вот так он должен работать:
Код
процедура шаг
начало
если не закрашено, то начало
  закрасить
  если не дошли, то начало
    если на север можно идти и там не закрашено, то начало
     шаг на север
    конец
    если на юг можно идти и там не закрашено, то начало
     шаг на юг
    конец
    если на запад можно идти и там не закрашено, то начало
     шаг на запад
    конец
    если на восток можно идти и там не закрашено, то начало
     шаг на восток
    конец
  конец
  иначе начало
    дошли ура!
  конец
конец
конец

Но это полный перебор вариантов хождений, если матрица очень большая, то жди переполнения стека! Если матрица большая, то лучше ходить по границе.

Сообщение отредактировано: hiv -


--------------------
Никогда не жадничай. Свои проблемы с любовью дари людям!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






а где в этом алгоритме рекурсия ?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Новичок
*

Группа: Пользователи
Сообщений: 48
Пол: Мужской
Реальное имя: Максим

Репутация: -  1  +


Hiv, нет, твой алгоритм отличается от моего smile.gif и в том псевдо коде я просто, как я уже писал не добавлял проверку местоположения.


--------------------
Три пути ведут к знанию: путь размышления - это путь самый благородный, путь подражания - это путь самый легкий и путь опыта - это путь самый горький.
Конфуций
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






объясните плз подробнее , не совсем понятно , по алгоритму стасенки он вообще будет ходить по крестику !!!
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


positv, чем тебя не устроила ссылка Алены?
Там все как ты просил, с рекурсией..

Если же хочешь алгоритм "правой/левой руки", то можешь взять тут:
Лабиринт
- все разложено по элементам, только без рекурсии..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 48
Пол: Мужской
Реальное имя: Максим

Репутация: -  1  +


Чтобы Ввы мне поверили, то вот реализация моего алгоритма.
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, извини, твоего сообщения не видел.


--------------------
Три пути ведут к знанию: путь размышления - это путь самый благородный, путь подражания - это путь самый легкий и путь опыта - это путь самый горький.
Конфуций
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Гость






'Lapp' . прога по ссылке алены вообще не работает =((



 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Positiv @ 24.03.2007 22:30) *

'Lapp' . прога по ссылке алены вообще не работает =((

Вот это ты зря.. sad.gif
В следующий раз, будь добр, если говоришь, что программа из форумского FAQ не работает - приведи конкретно, что именно не работает и как. Пустые утверждения, не подтвержденные фактами, не принимаются к рассмотрению вообще..
Я проверил программу - она работает. Я вставил в нее случайное задание лабиринта, как в твоем условии, все работает замечательно.
Если тебя это интересует, приведи конкретно, что у тебя не работало, и мы продолжим разговор..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Гость






когда запускаешь программу алены , так понимаю надо ввести значения , вводи вводил и ничего не произошло хоть до бесконечности вводи =((
может че то недопонял в коде ее ?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Новичок
*

Группа: Пользователи
Сообщений: 48
Пол: Мужской
Реальное имя: Максим

Репутация: -  1  +


Там нужно сначала ввести матрицу, а потом координаты видимо ты не ввел нужное количество элементов матрицы и поэтому программа не запустилась.

Добавлено через 1 мин.
P.S. Можно не скромный вопрос? Чем мой сурс не устраивает?


--------------------
Три пути ведут к знанию: путь размышления - это путь самый благородный, путь подражания - это путь самый легкий и путь опыта - это путь самый горький.
Конфуций
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Гость






St@senk@ . надо что бы с рекурсией было , а я не знаю как в твою прогу добавить рекурсию
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 17:09
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name