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

[Cool_abc]

Текст задачи:
Имеется N населенных пунктов, пронумерованных от 1 до N (N = 10).
Некоторые пары пунктов соединены дорогами. Определить, можно ли по
дорогам попасть из пункта 1 в N-й пункт. Информация о дорогах задается в
виде последовательности пар чисел i и j (i < j), указывающих что i-й и j-й
пункты соединены дорогой. Признак конца этой последовательности – пара
нулей.
Из условия я вынес 1 из основных положений, что по кругу между пунктами мы ходить не будем, т.е. например
1-2-3-5-6-1 (- догора), задача после этого сущаственно упростилась:) написал, но не работает прога, помогите плиз найти ошибку.. или мот я в корне был не прав.. наставьте на путь правильный

Мой код:

Program lab;
  Type int=integer;
       mas=array [1..30, 1..2]of int;
  { 30 - условное число, просто чтобы ограничить массив}
  Var fl: boolean;
      x: mas;
      k:int;

  Procedure vvod(a:mas);
    Var x,y,i:int;
  begin
    Writeln('vvedite parbl 4isel');
    x:=1;y:=1;i:=0;
    While (x<>0) and (y<>0) do
    begin
      if i<>0 then begin
        a[i,1]:=x;
        a[i,2]:=y;
      end;
      Write('vvedite 1 4islo  ');readln(x);
      Write('vvedite 2 4islo  ');readln(y);
      i:=1+i
    end
  end;
  
  procedure find(A:int;var f:boolean);
    Var i:int;
  begin
    if x[A,2]=10  then  f:=true
      else begin
        i:=1;
        while (x[i,1]<>0) and (x[i,2]<>0) and (not f) do
        begin
          if x[A,2]=x[i,1] then
            find(i,f);
          i:=i+1
        end
      end
  end;

Begin
  vvod(x);
  fl:=false;
  k:=1;
  while (x[k,1]<>0) and (x[k,2]<>0) and (not fl) do
  begin
    if x[k,1]=1
      then find(k,fl);
    k:=k+1
  end;
  
  if fl
    then writeln('yes')
    else writeln('nno')
End.

первый проход вынес в основную программу, т.к. нужно было сделать 1 проход по всем x(i,1)=1, т.е. тем. у которых первый пункт - наш начальный и в процедуре в стоке "if x[A,2]=x[i,1] then .." не смог бы подставить вместо x[i,1] единицу

[Lapp]

эм... здесь же по условию не подходят дходные данные.. x(i,j), где i < j, т.е. 10-8 и 5-3 не может быть.

Упс!.. мой фолт, извиняюсь, недосмотрел. Условие i<j как-то я пропустил.. Но оно в некотором смысле лишнее. Обрати внимание: когда я заполняю матрицу - я изменяю не только элемент i,j , но и j,i. И это обязательно нужно делать. Насколько я понимаю - дороги не с односторонним движением, то есть если есть дорога из А в Б, то по ней можно попасть и из Б в А. Так? Условие i<j нужно только для какого-то упорядочивания входных данных. Но зачем требовать соблюдения специальных правил от того, кто вводит информацию там, где это не нужно? Неужели хваленый всемогущий компьютер не может упорядочить два числа на входе?.. Повторяю, на ответ это не должно влиять (если движение двустроннее).

насчет магических числем.. я читал вашу тему "Как не надо писать программы", но тут без 10 никак)

И почему это "никак"? В этом вопросе "никак" быть просто не может. Делаешь константу n=10, а также m=30 - и все, никаких "никак"! Дальше используешь их. Стоит ли из-за одного двух вхождений огород городить, делать константы (лишняя строчка же!)? БЕЗУСЛОВНО СТОИТ. Получил задачу от препа - начни ее с того, что ВСЕ числовые значения оформь, как константы (если только это не что-то типа ряда значений функции, которые нужно вычислить. Факт тот, что НИКАКИЕ числа НЕ ДОЛЖНЫ встречаться в коде (кроме ДЕЙСТВИТЕЛЬНО МАГИЧЕСКИХ, типа, скажем, 2 при дихотомиии - да и то лучше константой). Все. БАСТА, финал, точка. Тут даже думать не нужно.
Ты уж слишком жестко привязался к поиску пути имено из первого города в последнему. Заметь, 1 у тебя ТОЖЕ выступает в роли магического числа, и его, в силу реальной уникальности единицы, трудно отследить. Вот, придешь ты на сдачу зачета, а преп скажет: хорошо, ответ правильный, а теперь то же самое, но только из 3 города в 8. И что ты будешь делать? Срочно менять все десятки на 8, а единицы на 3?? Но некоторые десятки нужно оставить (городов-то 10), и уж заведомо многие единицы (начала циклов, например). Ты уверен, что ты нигде не пропустишь и не поменяешь лишнего? Посмотри на мой код. Вызов поиска пути происходит с указанием начального и конечного города. Хотите другие - смените два числа в одной строчке. Хотите другое количество городов - смените n в самом начале, тоже в одном месте. Если преп попросит - это можно сделать в считанные секунды, он не успеет от тебя отойти даже. Сечешь фишку?

1. можно пояснить почему ответ да?.. по каким дорогам мы последовательно доберемся из 1 и N город..

Если забыть про (забить на)) условие i<j, то так:
1 -> 5 -> 3 -> 8 -> 10

2. я конечно понимаю.. что это элегантно.. )

Про элегантность - не пустой звук. Это можно назвать "шестым чувством программера". Оно сходно с тем, что архитектор должен стремиться к красоте здания - и тогда оно будет прочным. Физиков то же самое чувство ведет к Теории Великого Объединения .

2.1. процедуры Include и Exclude нам не давали, но, как я понял через 10 минут перепрочитывания текста функции, это добавление и удаление элемента во множество.. вроде так, да?

Да. Вместо них можно использовать такие выражения:

v:= v + [i];  // Include
v:= v - [i];  // Exclude

Квадратные скобки обеспечивают перевод элемента i в множество, состоящее из одного элемента i. А на множествах определены операции сложения и вычитания. Результат тот же самый. Множества в некоторых ситациях очень удобны: например, отметить пройденные города, чтоб потом не зацикливаться. Единственный недостаток стандартного типа set - ограничение 255 элементов.

2.2. s:=false;
for i:=1 to n do s:=s or not(i in v) and r[a,i] and c(i,b,v);
c:=s
мы s присваиваем или false, или not(i in v) and r[a,i] and c(i,b,v)? поясните пожалуйста

Это ключевой момент. Хорошо, что ты спросил. После того, как ты разберешься с этим - все встанет на свои места.

Нет, мы не присваиваем s "или ложь, или..". Ты извини, но само построение фразы у тебя ущербно. Постарайся вникнуть. Нельзя присваивать "или ложь", такое присваивание не несет в себе никакого смысла, его можно просто убрать. Потому что, если первый операнд в операции "или" есть ложь, то ее результат просто равен второму операнду. И операция просто теряет смысл, как я уже сказал.

В данном случае переменная s (scan) имеет накопительный смысл. Да, в самый первый проход цикла от нее ничего не зависит, поскольку она есть ложь. Но уже ко второму проходу ее значение может измениться на true (путь найден) - и что тогда? Тогда, каким бы ни был результат последующего сканирования (по сути, его и не будет, если отключено Complete Boolean Evaluation, $B-), результат будет true. То есть как раз то, что нам и надо: выяснить, существует ли хоть один путь. Запомни эту конструкцию, она тебе еще тысячи раз пригодится:

b:=false;
for i:=n to m do b:=b or (i mod 789=0);
WriteLn('Встречается ли на участке от ',m,' до ',n,' хоть одно число, кратное 789? ',b);

С этим понятно? Поехали дальше. Остальная часть выражения выглядит так:
not(i in v) and r[a,i] and c(i,b,v).
Что означает первый член? То, что мы должны проверять только те города, в которых еще не были. Думаю, это не нуждается в пояснении, ты сам это отметил в самом первом мессадже. Второй и третий члены нужно рассматривать вместе. В переводе на русский это звучит так: если есть дорога в город i И можно найти путь из i в конечный пункт назначения. А что значит "можно найти"? Ответ на этот вопрос должна выдавать как раз наша функция! Вот тебе и рекурсия. Но - есть маленькое "но": так нельзя было бы строить алгоритм, если не добавить: ".. среди оставшихся городов". Но это мы уже обусловили (первый член, not (i in v)). Таким образом, мы идем все дальше и дальше вглубь до тех пор, пока не исчерпаем все города.

Я в общем-то хотел бы продолжить решать своим методом.. но после изменения процедуры ввода и десятка просмотра\проходу по алгоритму ничего не изменилось..*печаль* вроде все правильно, когда прохожу по алгоритму, но не работает... вообще не понимаю, почему.

А причин много, на самом деле. Например, тебе volvo уже написал, и я повторю: то, что ты вводишь в процедуре vvod НИКАК не влияет на массив x. Чтобы повлияло, используй var-параметры.

Дальше.. просматривая твою прогу, я, кажется, понял, почему ты удивляешься, что ответ для моего файла есть ДА. Тебе кажется, что дороги должны быть перечислены во входной последовательности в порядке их прохождения? То есть тут:
5 10
1 5
- нельзя пройти сначала по второй дороге, а потом уже по первой? Но откуда ты это взял? Дороги что, строят, пока ты по ним едешь?? Может, я тебя неверно интерпретировал, тогда извини.. Короче, мне кажется. у тебя уже достаточно материала на обдумывание пока )). Успехов тебе, пиши, что выходит.

[Cool_abc]

Упс!.. мой фолт, извиняюсь, недосмотрел. Условие i<j как-то я пропустил.. Но оно в некотором смысле лишнее. Обрати внимание: когда я заполняю матрицу - я изменяю не только элемент i,j , но и j,i. И это обязательно нужно делать. Насколько я понимаю - дороги не с односторонним движением, то есть если есть дорога из А в Б, то по ней можно попасть и из Б в А. Так? Условие i<j нужно только для какого-то упорядочивания входных данных. Повторяю, на ответ это не должно влиять (если движение двустроннее).
...
Ты уж слишком жестко привязался к поиску пути имено из первого города в последнему.
...
Множества в некоторых ситациях очень удобны: например, отметить пройденные города, чтоб потом не зацикливаться.

из условия i<j я понимал, что из этого следует односторонее движение, а при одностороннем движении у нас никогда не произойдет зацикливания.. считал это 1 из условий, существенно облегчающих мне задачу, а не просто как способ упорядочивания данных:)
если бы я её понял, таким же образом, как и вы, то да, конечно, у меня была бы другая процедура с 2 входными параметрами - номерами городов, между которыми нужно найти дорогу.. правда не факт, что я бы уложился в сравнительно малое число локальных и глабальных переменных, т.к. ставил бы дополнительные счетчики и условия за зацикливания:)

И почему это "никак"? В этом вопросе "никак" быть просто не может. Делаешь константу n=10, а также m=30..

теперь все понял до конца и правильно. Под избавлением от магических чисел я понимал выражение 10-ки одним из элементов массива х[i,2]=10, а не замену числа в тексте программы на константу

Физиков то же самое чувство ведет к Теории Великого Объединения .

не знаю такой)) пока что )

Да. Вместо них можно использовать такие выражения:

v:= v + [i];  // Include
v:= v - [i];  // Exclude

Квадратные скобки обеспечивают перевод элемента i в множество, состоящее из одного элемента i. А на множествах определены операции сложения и вычитания. Результат тот же самый. Множества в некоторых ситациях очень удобны: например, отметить пройденные города, чтоб потом не зацикливаться. Единственный недостаток стандартного типа set - ограничение 255 элементов.

да, операции над множествами знаю

b:=false;
for i:=n to m do b:=b or (i mod 789=0);
WriteLn('Встречается ли на участке от ',m,' до ',n,' хоть одно число, кратное 789? ',b);

супер!) здесь первый раз встретил такую контрукцию... нет слов) раньше у меня схожее с этим заменялось введением ещё 1 переменной булевского типа и заменой For на While с 2 ограничениями)
спасибо)

Остальная часть выражения выглядит так:
not(i in v) and r[a,i] and c(i,b,v).
Что означает первый член? То, что мы должны проверять только те города, в которых еще не были. Думаю, это не нуждается в пояснении, ты сам это отметил в самом первом мессадже. Второй и третий члены нужно рассматривать вместе. В переводе на русский это звучит так: если есть дорога в город i И можно найти путь из i в конечный пункт назначения. А что значит "можно найти"? Ответ на этот вопрос должна выдавать как раз наша функция! Вот тебе и рекурсия. Но - есть маленькое "но": так нельзя было бы строить алгоритм, если не добавить: ".. среди оставшихся городов". Но это мы уже обусловили (первый член, not (i in v)). Таким образом, мы идем все дальше и дальше вглубь до тех пор, пока не исчерпаем все города.

все уяснил

А причин много, на самом деле. Например, тебе volvo уже написал, и я повторю: то, что ты вводишь в процедуре vvod НИКАК не влияет на массив x. Чтобы повлияло, используй var-параметры.

после половины последнего слова я сразу открыл текст программы.. а в голове "Неужели, я не написал слово var... и несколько дней работа стояла на месте из-за процедуры ввода..?", а ведь ещё утром с одногруппником разговаривал, говорю ему, что вот.. решил лабу, но ошибку найти не могу долго, там он "тоже что-то такое было, искал 2 недели ошибку, а оказалась 1 сточка личшняя, переменная в которой используется 1 раз за программу"..
йо моё...все отлично работает, наконец-то, ура!) а то надоело расстраиваться, когда при очередном запуске был отрицательне ответ на месте положительного)

Дальше.. просматривая твою прогу, я, кажется, понял, почему ты удивляешься, что ответ для моего файла есть ДА. Тебе кажется, что дороги должны быть перечислены во входной последовательности в порядке их прохождения?

нет, далеко не обязательно в порядке прохождения, я рассматривал случай, когда из одного города может выходить сколько угожно дорог, но все.. как уже написал выше.. из условия i<j с односторонним движением

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

[Lapp]

из условия i<j я понимал, что из этого следует односторонее движение, а при одностороннем движении у нас никогда не произойдет зацикливания.. считал это 1 из условий, существенно облегчающих мне задачу, а не просто как способ упорядочивания данных:)

Гым.
Одностороннее движение ТОЛЬКО из городов с меньшим номером в больший?? Бедные жители этой страны, однако.. Даже не представляю, как такое может прийти в голову, извини.

Если бы речь шла об односторонем движении, то условия i<j как раз не могло бы быть. Именно его наличие в конце концов подтвердило для меня мои предположения о двустроннем движении. Кирилл, анализируй условие и старайся проверить его на соответствие со здравым смыслом. Хорошо понятое условие - четверть решения..