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

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

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

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





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

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


Текст задачи:
Имеется 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] единицу
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


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

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

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


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

Cool_abc, подобные вещи в рекурсии - первый признак, что что-то не так. Рекурсия должна быть элегантной )). Извини, не стал глубоко вникать в твой код. Я написал решение - проанализируй и попробуй сам найти свои ошибки.
const
n=10; // no more then 255

type
tVisited= set of byte; // to remember already visited towns

var
r: array[1..n,1..n]of boolean; // roads
f: text; // input data, one pair each line


function c(a,b: byte; v: tVisited): boolean; // connected?
var
s: boolean; // scan result
i: integer;
begin
Include(v,a); // "here was i! ))"
if r[a,b] then c:=true else begin
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
end;
Exclude(v,a) // leaving the town
end;

var
a,b: integer;

begin
FillChar(r,SizeOf®,0); // roads init
Assign(f,'roads.dat');
ReSet(f);
while not EoF(f) do begin
ReadLn(f,a,b);
if a=0 then break; // added for compatiblity
r[a,b]:=true; // add a road
r[b,a]:=true // add a road back
end;
Close(f);
WriteLn(c(1,n,[]))

;ReadLn
end.

Если комментов недостаточно - спрашивай, я всегда отвечу. Удачи! smile.gif

Добавлено через 4 мин.
Да, еще: входные данные ьерутся из файла roads.dat . Вот его пример:
Код
1 5
10 8
2 10
3 8
5 3

- тут ответ ДА. Нули в конце можешь добавить, но они не нужны (правда, в этом случае не должно быть пустых строк в конце).


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


Гость






Cool_abc, поиск ошибок начинай прямо с процедуры Vvod. Ну, заполнил ты в ней массив какими-то значениями, и что? Посмотри, что у тебя хранится в массиве X после того, как Vvod отработал. Это первое.

Второе - я говорил много раз, и повторю еще раз: не пользуйся никогда магическими числами. Вот это что по-твоему:
procedure find(A:int;var f:boolean);
Var i:int;
begin
if x[A,2]=10 then f:=true { <--- Почему именно 10? }

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

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





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

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


Цитата(Lapp @ 25.04.2010 3:31) *

Добавлено через 4 мин.
Да, еще: входные данные ьерутся из файла roads.dat . Вот его пример:
Код

1 5
10 8
2 10
3 8
5 3

- тут ответ ДА. Нули в конце можешь добавить, но они не нужны (правда, в этом случае не должно быть пустых строк в конце).

эм... здесь же по условию не подходят дходные данные.. x(i,j), где i < j, т.е. 10-8 и 5-3 не может быть. Первое число ( x[i,1] ) - это город, в который мы приходим, а 2 число ( x[i,2] ) - это город, в который ведет дорога из города x[i,1], я так понимаю. Поиск мы останавливаем, когда наткнулись на элемент x[i,2]=10, т.е. дорога из текущего города ведет в город под номером 10, а до этого элемента уже есть дорога (т.е. мы до него шли от одного из x[i,1] = 1 (по 1 из дорого, ведущих из 1 города))
но если бы даже не было условия i<j, то мы все равно бы не попали..
смотрим, где x[i,1]=1, нашли все такие элементы, их число = 1, значит смотрим дальше x[i,2] = 5, значит ищем все x[i,1]=5, их опять 1, это 5 3, дальше ищем x[i,1]=3, нашли, это 3 8, ищем x[i,1]=8, таких нет, дорога оборвалась и разветвлений никаких не было (т.е. до этого из каждого города выходило по 1 дороге), значит ответ "нет".
насчет кода с решением, спасибо, сёчас буду читать, разбираться в нём

Цитата(volvo @ 25.04.2010 9:09) *

Cool_abc, поиск ошибок начинай прямо с процедуры Vvod. Ну, заполнил ты в ней массив какими-то значениями, и что? Посмотри, что у тебя хранится в массиве X после того, как Vvod отработал. Это первое.

Второе - я говорил много раз, и повторю еще раз: не пользуйся никогда магическими числами. Вот это что по-твоему:
procedure find(A:int;var f:boolean);
Var i:int;
begin
if x[A,2]=10 then f:=true { <--- Почему именно 10? }

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

В общем, если хочешь продолжить разбираться со своим методом решения - скажи...

да, сейчас буду продолжать разбираться, за процедуру vvod спасибо:) понял, где там ошибка, у нас в локальных переменных x,y будут оставаться храниться нули, но мы их в массив не занесли;
вот насчет магических числем.. я читал вашу тему "Как не надо писать программы", но тут без 10 никак), потому что по условию задачи, нам нужно найти дорогу из города 1 в город 10, т.е. в предпоследнем городе перед 10 городом из него будет идти дорога в город 10, что описано условием x[A,2]=10, поэтому имеено 10..
число городов у нас есть, оно ограничено, самый большой номер города м.б. равен 10; неограничено только число дорог, которые могуд идти из одного города, т.е. из первого города могут идти дороги во 2, 3,4,5,6,7 города, что будет выглядеть как
1-2
1-3
1-4
1-5
1-6
1-7
в массиве

дошел дальше разбираться smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





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

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


Цитата(Lapp @ 25.04.2010 3:31) *

Рекурсия должна быть элегантной )).

function c(a,b: byte; v: tVisited): boolean; // connected?
var
s: boolean; // scan result
i: integer;
begin
Include(v,a); // "here was i! ))"
if r[a,b] then c:=true else begin
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
end;
Exclude(v,a) // leaving the town



Если комментов недостаточно - спрашивай, я всегда отвечу. Удачи! smile.gif

Да, еще: входные данные ьерутся из файла roads.dat . Вот его пример:
Код
1 5
10 8
2 10
3 8
5 3

- тут ответ ДА.

1. можно пояснить почему ответ да?.. по каким дорогам мы последовательно доберемся из 1 и N город..
2. я конечно понимаю.. что это элегантно.. )
можно пояснить основную рекурсивную функцию? непонятно следущее:
2.1. процедуры Include и Exclude нам не давали, но, как я понял через 10 минут перепрочитывания текста функции, это добавление и удаление элемента во множество.. вроде так, да?
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)? поясните пожалуйста

Цитата(volvo @ 25.04.2010 9:09) *

В общем, если хочешь продолжить разбираться со своим методом решения - скажи...


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

после изменения процедуры ввода:

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;
a[i,1]:=x; {вот здесь 2 строчки дописал и все...}
a[i,2]:=y
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.






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


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

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

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


Цитата(Cool_abc @ 25.04.2010 14:46) *
эм... здесь же по условию не подходят дходные данные.. 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. я конечно понимаю.. что это элегантно.. )
Про элегантность - не пустой звук. Это можно назвать "шестым чувством программера". Оно сходно с тем, что архитектор должен стремиться к красоте здания - и тогда оно будет прочным. Физиков то же самое чувство ведет к Теории Великого Объединения smile.gif.

Цитата
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
- нельзя пройти сначала по второй дороге, а потом уже по первой? Но откуда ты это взял? Дороги что, строят, пока ты по ним едешь?? blink.gif Может, я тебя неверно интерпретировал, тогда извини.. Короче, мне кажется. у тебя уже достаточно материала на обдумывание пока )). Успехов тебе, пиши, что выходит.


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





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

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


Цитата(Lapp @ 26.04.2010 6:17) *

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



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

Цитата(Lapp @ 26.04.2010 6:17) *

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

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

Цитата(Lapp @ 26.04.2010 6:17) *

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


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

Цитата(Lapp @ 26.04.2010 6:17) *

Да. Вместо них можно использовать такие выражения:
v:= v + [i];  // Include
v:= v - [i]; // Exclude
Квадратные скобки обеспечивают перевод элемента i в множество, состоящее из одного элемента i. А на множествах определены операции сложения и вычитания. Результат тот же самый. Множества в некоторых ситациях очень удобны: например, отметить пройденные города, чтоб потом не зацикливаться. Единственный недостаток стандартного типа set - ограничение 255 элементов.


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


Цитата(Lapp @ 26.04.2010 6:17) *

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



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

Цитата(Lapp @ 26.04.2010 6:17) *

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


все уяснил

Цитата(Lapp @ 26.04.2010 6:17) *

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

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

Цитата(Lapp @ 26.04.2010 6:17) *

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

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

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


Злостный любитель
*****

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

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


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

Одно из них - когда счётчик доходит до конца, другое - когда мы нашли элемент, удовлетворяющий условию?
Так

b := false;
for i := n to m do if i mod 789 = 0 then begin
b := true;
break;
end;



Я одно время увлекался такими конструкциями типа b := b or a, но в них проще запутаться, например, легко забыть лишнюю скобку вокруг a, если а сложное выражение, типа c and d (c и d тоже состоят из кучи подвыражений и окружены тройными скобками по бокам), то вместо b := b or (c and d) получается по смыслу b := (b or c) and d. После того, как у меня один вагон стал проезжать сквозь другой, я отказался от таких конструкций. Оператор |= тут бы пригодился, но он всё равно не даст возможности выхода при достижении условия.

А если a - простое выражение, то запись b := b or a всё так же генерирует ветвления, причём делает это ещё хуже, чем при явной форме if a then b := true;
Вот на примере D7:

Хотя да, разницы тут, если всмотреться, нет, просто если b уже достигнуто, то надо выходить и не делать каждый раз новых проверок. Короче, так делать имеет смысл только для компактности исходного кода.

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


Эскизы прикрепленных изображений
Прикрепленное изображение

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





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

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


Цитата(TarasBer @ 26.04.2010 16:04) *

...
Хотя да, разницы тут, если всмотреться, нет, просто если b уже достигнуто, то надо выходить и не делать каждый раз новых проверок. Короче, так делать имеет смысл только для компактности исходного кода.


лишние знания не помешают.. во всяком случае мне, а использовать ту или иную конструкцию нужно исходя из конкретной ситуации

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


Злостный любитель
*****

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

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


Это программа, которую я специально написал только что и которая состоит только из обсуждаемой конструкции. В D7 можно во время отладки нажать Ctrl+Alt+C и увидеть, в какие инструкции переходят конструкции языка.


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


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

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

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


Цитата(Cool_abc @ 26.04.2010 15:34) *
из условия i<j я понимал, что из этого следует односторонее движение, а при одностороннем движении у нас никогда не произойдет зацикливания.. считал это 1 из условий, существенно облегчающих мне задачу, а не просто как способ упорядочивания данных:)
Гым.
Одностороннее движение ТОЛЬКО из городов с меньшим номером в больший?? Бедные жители этой страны, однако.. blink.gif Даже не представляю, как такое может прийти в голову, извини.

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


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


Гость






Цитата
А если a - простое выражение, то запись b := b or a всё так же генерирует ветвления, причём делает это ещё хуже, чем при явной форме if a then b := true;
Вот на примере D7:
Я тебе открою тайну: если перед этим самым циклом поставить {$b-}, то ассемблерный листинг будет длиннее, чем если поставить {$b+}. Однако выполняться первый случай будет в несколько раз быстрее, чем второй. И что? Количество инструкций еще не прямо пропорционально времени их выполнения.

Еще одна тайна: Дельфи 2006 может показать другой листинг. 2009 - третий, а 2010? Сколько компиляторов - столько и мнений... Хочешь - еще открою тебе неизведанное? На твоем процессоре код Х будет выполняться за время Т, на другом - за время Т/3. Не веришь? Уже забыл, что я тебе показывал (когда твоя супер-вылизанная программа проиграла по скорости у меня на машине по скорости моей программе, написанной в лоб, безо всяких ухищрений в два раза). Опять начинаешь старую песню? dry.gif

Повторяю еще раз: у этого форума задача - научить программировать. Точка. Ни о какой оптимизации (тем более - предварительной) речи не идет. Все оптимизации кончаются одинаково: "я оказался не готов к способности окон менять размеры и к тому, что у всех разное разрешение экрана." (С) кто_это_написал_ты_мне_не_напомнишь_?

Точно так же ты можешь оказаться не готов читать чужой код, содержащий совершенно легитимные синтаксические конструкции. А таких "программистов" (которые изо всех конструкций языка знают только for/while/if, и даже про case не слышали никогда, потому что вот подобный тебе "исследователь" говорил им, что case работает медленнее чем несколько if-ов, забывая однако уточнить, на какой машине и с использованием какого компилятора, и вообще КАК он это выяснил) я видел достаточно.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Злостный любитель
*****

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

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


> Количество инструкций еще не прямо пропорционально времени их выполнения.

Поэтому я и дописал поправку.

> Уже забыл, что я тебе показывал (когда твоя супер-вылизанная программа проиграла по скорости у меня на машине по скорости моей программе, написанной в лоб, безо всяких ухищрений в два раза).

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

> Точно так же ты можешь оказаться не готов читать чужой код, содержащий совершенно легитимные синтаксические конструкции.

Я вообще не люблю читать чужой код (как и все мы). И, к счастью, у меня нет такой необходимости.

> которые изо всех конструкций языка знают только for/while/if

А может, так и надо? Дедушка Вирт любил выкидывать избыточные конструкции.


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


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

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

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


Цитата(volvo @ 27.04.2010 13:01) *
Повторяю еще раз: у этого форума задача - научить программировать.
Главная и единственная задача этого форума, на мой взгляд - общение. Плюс обучение общению, как естественное приложение. Каждый может поучавствовать в беседе и высказать мнение (если это не троллинг).

На мой взгляд, Тарас дело сказал. Это не оптимизация даже, это прямое улучшение алгоритма. Оно не во всех случаях удобно и даже применимо, но тут вполне к месту. Использование IF тут сильно картину не портит, я согласен. Экономия не такая большая, но тем не менее..

Давайте держаться в рамках темы и доброжелательности.


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


Гость






Цитата
Главная и единственная задача этого форума, на мой взгляд - общение.
В таком случае извините, что столько времени вам надоедал... я, видимо, просто ошибся форумам...
 К началу страницы 
+ Ответить 

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

 





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