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

> Правила раздела!

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

 
 Ответить  Открыть новую тему 
> Нахождение кратчайшего пути, без использования графов
сообщение
Сообщение #1


Пионер
**

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

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


Подскажите, где почитать или подскажите как осуществляется нахождения кратчайшего пути без использования графов, чистой рекурсией??


--------------------
Рассылка: "Решение Вами Предложенных Задач На Языке PASCAL. Алгоритмы на PASCAL."
Подписка по e-mail: comp.soft.prog.pascal123-sub@subscribe.ru
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Знаток
****

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

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


ты скажи ,у тебя данные как хранятся?


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

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

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


в общем хранить их можно где угодно и как угодно... ну думаю, что хранить буду в матрице 10x10, где "0" - проход, "1" - стена, "2" - точка к которой надо найти кратчайший путь...
ну а искать его буду от 1х1 координаты...


--------------------
Рассылка: "Решение Вами Предложенных Задач На Языке PASCAL. Алгоритмы на PASCAL."
Подписка по e-mail: comp.soft.prog.pascal123-sub@subscribe.ru
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Знаток
****

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

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


Код
program recursion;
const maxn=10;
var a,b:array[1..maxn,1..maxn]of integer;
   i1,j1:integer;
   i,j,n:integer;
   cou:integer;

procedure init;
begin
  readln(n);
  for i:=1 to n do
     for j:=1 to n do
        read(a[i,j]);
end;

procedure solve(i,j:integer);
begin
  if (i<1) or (i>n) or (j<1) or (j>n) or (a[i,j]=1) then exit;
  if b[i,j]>cou then b[i,j]:=cou;
  a[i,j]:=1;
  inc(cou);
  solve(i+1,j);
  solve(i-1,j);
  solve(i,j+1);
  solve(i,j-1);
  dec(cou);
end;

procedure out;
begin
  writeln(b[i1,j1]);
end;

begin
  init;
  cou:=0;
  for i:=1 to n do
     for j:=1 to n do
        b[i,j]:=maxint;
  for i:=1 to n do
     for j:=1 to n do
     if a[i,j]=2 then
        begin
           i1:=i;
           j1:=j;
        end;
  solve(1,1);
  out;
end.


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Знаток
****

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

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


извиняюсь ,
процедура solve должна быть такой :
Код

procedure solve(i,j:integer);
begin
  if (i<1) or (i>n) or (j<1) or (j>n) or (a[i,j]=1) then exit;
  if b[i,j]>cou then b[i,j]:=cou;
  a[i,j]:=1;
  inc(cou);
  solve(i+1,j);
  solve(i-1,j);
  solve(i,j+1);
  solve(i,j-1);
  dec(cou);
  a[i,j]:=0;{!!!!!!!!!!!!!!}
end;


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


...
*****

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

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


virt теги не забывай!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Пионер
**

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

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


virt
Спасибо большое!!!


--------------------
Рассылка: "Решение Вами Предложенных Задач На Языке PASCAL. Алгоритмы на PASCAL."
Подписка по e-mail: comp.soft.prog.pascal123-sub@subscribe.ru
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Пионер
**

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

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


virt
Кстати, а как он работает?smile.gif
Я заполняю матрицу, где:
0 - проход
1 - стена
2 - конечный пункт прибытияsmile.gif

И получаю какую-то цифру 1... и матрицу b, заполненную нулями...
Путь к конечной точке имеется, причем даже не один!:)


--------------------
Рассылка: "Решение Вами Предложенных Задач На Языке PASCAL. Алгоритмы на PASCAL."
Подписка по e-mail: comp.soft.prog.pascal123-sub@subscribe.ru
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Знаток
****

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

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


по идее по b находится путь (или пути) ,и она должна быть ненулевой.???
а цифра(число) это длина пути.

З.Ы. пришли плз. свою матрицу А на которой у тебя все нули (на PM)


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Знаток
****

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

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


AlaRic
извини ,конечно ,но я хотел изменения в коде выделить.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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