1. Заголовок темы должен быть информативным. В противном случае тема удаляется ... 2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения. 3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали! 4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора). 5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM! 6. Одна тема - один вопрос (задача) 7.Проверяйте программы перед тем, как разместить их на форуме!!! 8.Спрашивайте и отвечайте четко и по существу!!!
Рекурсия, не могу найти ошибку, N нас. пунктов, пары пунктов соединены, узнать, можно ли попасть из
Текст задачи: Имеется 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] единицу
эм... здесь же по условию не подходят дходные данные.. 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 в самом начале, тоже в одном месте. Если преп попросит - это можно сделать в считанные секунды, он не успеет от тебя отойти даже. Сечешь фишку?
Цитата(Cool_abc @ 25.04.2010 20:12)
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 - нельзя пройти сначала по второй дороге, а потом уже по первой? Но откуда ты это взял? Дороги что, строят, пока ты по ним едешь?? Может, я тебя неверно интерпретировал, тогда извини.. Короче, мне кажется. у тебя уже достаточно материала на обдумывание пока )). Успехов тебе, пиши, что выходит.
--------------------
я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой