Форум «Всё о Паскале» _ Задачи _ процедуры и функции.Упорядоченная пос-ть при переборе змейкой.
Автор: Insomnia 13.12.2010 17:38
условие: для заданной вещественной матрицы определить, образуют ли её элементы упорядоченную последовательность при их переборе змейкой (начиная с 1 строки двигаясь по часовой стрелки).Для определения факта упорядоченности части строки(столбца) используйте функцию.
вот скудные наброски-->
Код
const n=10; m=10; type Temem=real; Tvector=array [1..n,1..m] of Telem; var a: Tvector; i,j: integer; left,right: integer; flag:boolean; begin i:=left; result:=true; while (i<right) and result do for i:=j+1 to n do if not flag (a[j+1,i],a[j+1,i+1]) then not flag for ...; ...
-идея в том, что бы проверять упорядоченность с левой части строк до правой, тоже самое со столбцами.Подскажите пожалуйста как правильно написать циклы для проверки нижней строки и левого столбца.Их же надо в обратном порядке считать как бы.И дальше, когда проверили 1 круг, при следуующей строке надо изменить в цикле только до n-1, потом до n-2 и т..д.? P.S. если не сложно, то можно ответы давать в развёрнутом виде? У меня совсем нету опыта по написанию программ.
Автор: TarasBer 13.12.2010 18:49
Чтобы цикл считался в обратном порядке, надо писать for i := n downto 1 do...
Автор: volvo 13.12.2010 19:13
Цитата
при их переборе змейкой (начиная с 1 строки двигаясь по часовой стрелки)
Вообще это называется "спираль", а не "змейка". Змейка - это первая строка слева направо - вторая - справа налево, и так далее...
Написать-то несложно. Попробуй теперь разобраться:
Код(Показать/Скрыть)
const SizeX = 7; SizeY = 5; type mx = array[1 .. SizeY, 1 .. SizeX] of Integer;
function is_sorted(const arr: mx): boolean;
var T: mx; i, j: integer;
function f(i, j: shortint): boolean; begin if (i < 1) or (i > SizeY) or (j < 1) or (j > SizeX) then f := false else f := (T[i,j] = -1); end;
function get_val(vi, vj, X: integer): integer; begin get_val := arr[vi, vj]; T[vi, vj] := X + 1; i := vi; j := vj; end;
var X: integer; prev, next: integer; begin is_sorted := false; for i := 1 to SizeY do for j := 1 to SizeX do T[i, j] := -1;
prev := get_val(1, 1, 0);
for X := 1 to pred(SizeX * SizeY) do begin if f(i-1, j) and not f(i, j-1) then next := get_val(i-1, j, X) else if f(i,j+1) then next := get_val(i, j+1, X) else if f(i+1,j) then next := get_val(i+1, j, X) else if f(i,j-1) then next := get_val(i, j-1, X);
if prev > next then exit; prev := next; end; is_sorted := true; end;
( при написании программы ни один дебаггер не пострадал, использовались фрагменты кода из FAQ-а форума: http://forum.pascal.net.ru/index.php?s=&showtopic=2694&view=findpost&p=27640 )
Идея понятна? Для того, чтоб проверить упорядоченность существующей матрицы, я создаю новую матрицу того же размера, и заполняю ее. Одновременно с этим проверяя каждое следующее значение в заполненной матрице: превышает оно предыдущее или нет. Если только встречается случай prev > next - это означает, что последовательность в матрице arr НЕупорядочена, можно сразу выходить из функции. Если дошли до конца - все нормально, порядок существует, возвращаем Истину...
Для вещественной матрицы надо поменять типы значений, все остальное останется без изменений...
Автор: Insomnia 15.12.2010 3:28
хм...впринцепи в какой то степени я тебя понял.. начало будет примерно таким?
procedure Pred(k,x,y: integer); begin if k<l then begin l:=k; u:=x; v:=y end end;
begin for i:=1 to n do for j:=1 to m do if (i>1)or(j>1) then begin l:=m; Pred(i-1, 0,-1); Pred(m-j,-1, 0); Pred(n-i, 0, 1); Pred(j-1, 1, 0); yes:=yes and (a[i,j]>=a[i+u,j+v]) end; WriteLn(yes); ReadLn end.
begin for i:=1 to n do for j:=1 to m do if (i>1)or(j>1) then begin l:=i; u:=0; v:=-1; if m-j+1<l then begin l:=m-j+1; u:=-1; v:=0; end; if n-i+1<l then begin l:=n-i+1; u:=0; v:=1 end; if j<l then begin u:=1; v:=0 end; yes:=yes and (a[i,j]>a[i+u,j+v]) end; WriteLn(yes); ReadLn end.
Автор: Insomnia 15.12.2010 15:06
я благодарен, но не могли бы вы мне помочь разобраться с решением? ответье пожалуйста на предыдущие вопросы. и ещё, что такое k,x,y? зачем используем ф-ю pred?
Автор: Lapp 15.12.2010 15:46
Цитата(Insomnia @ 15.12.2010 11:06)
и ещё, что такое k,x,y? зачем используем ф-ю pred?
Гм. Знаешь, Insomnia, тебе вряд ли подойдет мое решение. Я только сейчас заметил условие, что для сравнения элементов по условию должна использоваться функция. А у меня функция используется совсем для другого (для нахождения предыдущего элемента).
Автор: volvo 15.12.2010 15:59
Цитата
не могли бы пояснить что означают:
Ладно, поехали...
Цитата
function is_sorted(const arr: mx): boolean;
Это функция. которая получает на вход матрицу и возвращает признак ее упорядоченности при обходе по спирали. То есть, именно эта функция и решает поставленную задачу.
Цитата
function f(i, j: shortint): boolean;
Здесь мы проверяем по-первых, не выйдем ли при значениях индексов i, j за границы массива (обрати внимание, я сначала проверяю очередную ячейку вызовом F, и только потом, если F вернула Истину, то есть, эта ячейка в матрице существует и еще не была заполнена, ее заполняю). И если не выйдем - то проверяем, не заполнен ли уже тот элемент, который мы хотим заполнить... Мы T[i, j] ничего не присваиваем, только сравниваем (":=" и "=" это очень разные вещи)...
Цитата
и что подразумевается под X ?
Х - просто переменная. Дело в том, что я заполняю временную матрицу по порядку, значениями 1 .. SizeX*SizeY. Вот в этом интервале и изменяется X...
Автор: Insomnia 15.12.2010 16:52
Код
const arr: mx = ( ( 1, 2, 3, 0, 5, -6, 7), (20,21,22,23,24,25, 8), (19,32,33,44,45,26, 23), (18,31,30,29,28,27,10), (17,16,15,14,53,12,11) ); SizeX = 7; SizeY = 5; type mx = array[1 .. SizeY, 1 .. SizeX] of Integer; function is_sorted(const arr: mx): boolean; // в этой ф-ии будет идти проверка упорядоченности матрицы по спирали (вопрос: она проверяет только по спирали?) var X: integer; prev, next: integer; T: mx; function f(i, j: shortint): boolean; // почему сразу не сравнивать выходят ли i,j за границы массива нового? begin prev := get_val(1, 1, 0); // ... if (i < 1) or (i > SizeY) or (j < 1) or (j > SizeX) then f := false else f := (T[i,j] = -1); // т.е. если за границы не выходим то заполняю пустую ячейку матрицы? почему -1?? is_sorted := false; // пусть матрица изначально неупорядочена.проверяем, так ли это. for i := 1 to SizeY do for j := 1 to SizeX do T[i, j] := -1; for X := 1 to pred(SizeX * SizeY) do // в цикле заполняем матрицу единицами. begin if f(i-1, j) and not f(i, j-1) then next := get_val(i-1, j, X) else if f(i,j+1) then next := get_val(i, j+1, X) else if f(i+1,j) then next := get_val(i+1, j, X) else if f(i,j-1) then next := get_val(i, j-1, X); // вот здесь не очень понятно, у нас получается (0,1,1) , (1,2,1) , (2,1,1) или (1,0,1) ?
if prev > next then exit; // если предыдущее значение больше последующего, обрываем всё и выходим из цикла, в противном случае в ф-ии is_sorted проверка прошла успешно и пос-ть упорядочена. prev := next; end; is_sorted := true; end;
Автор: volvo 15.12.2010 17:24
Цитата
почему сразу не сравнивать выходят ли i,j за границы массива нового?
То есть, 4 раза подряд писать такие условия? Дело, конечно, твое, но я бы такую программу не принял... Если есть повторяющиеся участки кода - они должны быть вынесены в функцию...
Цитата
т.е. если за границы не выходим то заполняю пустую ячейку матрицы?
Ты читать умеешь? Я тебе русским языком сказал, что НЕ ЗАПОЛНЯЕТСЯ там ничего. ПРОВЕРЯЕТСЯ - да, но присвоения там нет. Хорошо, зайдем с другой стороны: приведи код, который проверяет, равняется ли значение переменной А единице.
Цитата
почему -1??
Потому что мне так захотелось. Захочу - поставлю (-1), захочу Low(Integer) поставлю. В самом начале я всю временную матрицу чем заполнил? Вот поэтому и смотрю, было ли занесено значение в ячейку, или там хранится то, чем матрица инициализировалась. Повторяю еще раз: уясни для себя разницу между присваиванием и сравнением.
Цитата
вот здесь не очень понятно, у нас получается (0,1,1) , (1,2,1) , (2,1,1) или (1,0,1) ?
Я не знаю, что у вас получается, у меня получается, что если функция F выдала Истину, значит, ячейку с теми координатами, которые в F передавались, можно заполнять очередным значением X. Что и делается в функции get_val. Которую ты, почему-то, вообще выкинул.
И на будущее - давай без самоуправства? Если я описал T и i, j ВЫШЕ функции f(), а все остальные переменные - НИЖЕ - значит, для этого были причины. Твой код не будет компилироваться, на всякий случай. А успешная компиляция - это один из признаков правильно написанной программы.
Зачем описание матрицы перенес выше функции? Кто просил тебя? "Меньше знаешь - лучше спишь" - слышал? Вот компилятора это тоже касается. чем меньше он знает - тем меньше вероятности ошибиться. Если он при компиляции функции не будет знать, что у тебя есть матрица Arr - ничего плохого не случится. Тем более, что описана эта матрица опять же неправильно. В следующий раз (когда что-то соберешься менять и изменишь) будь добр нажать на F9 и посмотреть, не навредили ли твои действия программе.
"Ни одно доброе дело не остается безнаказанным" (С) - это как раз этот случай. Вот и помогай после этого... Твой же код так изуродуют, что сам с трудом узнаешь.
Автор: Insomnia 16.12.2010 21:51
Иной раз бывает пишу , потом думаю. Я прошу прощения за ту чушь несусветную, что сморозил. С кодом разобрался.Сам до такой идеи не додумался бы, и уж тем более не реализовал. Вы мне очень помогли.Спасибо вам большое большое.