Помощь - Поиск - Пользователи - Календарь
Полная версия: Алгоритмы на матрицах
Форум «Всё о Паскале» > Pascal, Object Pascal > Теоретические вопросы
Флогримм
28.10.2004 11:39
вчера сел решать задачи на тему двумерных массивов - матриц и столкнулся с проблемой; какие можете посоветовать приемы программиования для алгоритмов, вида "заполнить матрицу по спирали, зигзагом" и т.д.

мне не конкретной задачи нужно решение, а метод в целом

пришла в голову такая идея: написать процедуры движения по матрице в четырех направленияъ (вверх, вниз, влево, вправо) до тех пор, пока не встретим либо конец матрицы ("крайнюю стенку") или же уже заплненный алгоритм и циклически повторять их до тех пор пока не заполним всю матрицу... да, наверное так и попробую

хотя мне кажется, что выход, который предложил выше не совсем правильный; может все можно свести все к основной (единственной формуле) формуле где меняться будет только значение i,j-счетчиков в цикле?

вобщем матрицы для меня проблема; помогите чем могите; в книгах же только и делают, что задачки пишут, а концепцию разъясникть - :no:

вот так
а еще вопрос: 1)как в вин2к в ТП7 установить русскую раскладку клавы; 2)как прервать зациклившийся процесс? (Ctrl-Break и Ctrl-F2 не работают)

зосим откланиваюсь, с уважением, Флогримм
Altair
28.10.2004 12:12
Цитата
как в вин2к в ТП7 установить русскую раскладку клавы;

Это тема неоднократно обсуждалась!
Методтаков: создать BET файл, где прописать русификатор и TP.
Цитата
как прервать зациклившийся процесс? (Ctrl-Break и Ctrl-F2 не работают)


Прежде всего, зациклившихся процессов быть не должно!
Везде где есть рекурсия, надо писать на всякий случай
Код
If keypressed then HALT;

Это останов проги по нажатию люой клавиши. (пропиши модуль CRT)
Цитата
написать процедуры движения по матрице в четырех направлениях

Это очень хорошие алгоритм. Лучше пожалуй (в смысле универсальности), не придумать!
ТОлько это должны быть функции. Смысл в том, что достаточно указать алгоритм движения, и можно хаполнить любую матрицу как угодно... хм.. а это интересно, сейчас займусь этим... посмотрим что получится...
Флогримм
28.10.2004 13:02
вот еще несколько вопросов, пожалуй, размещу здесь, влом новую тему создавать

1) как пользоваться операторами input/output? насколько это актуально? зачем нужно(хотя догадываюсь smile.gif )? почему упоминается только в старых книгах?
2) как передавать параметры программе, запуская ее через командную строку? как оформить это в самой программе?

зы вчера при компиляции программы, где использовались функции работы с файлами (assign, reset,close и т.д.) мой докторвэб выдал мне перл: "D:\TP\BIN\OLEG\PRACTP~1\LINES812.EXE инфицирован модификацией Ithaqua.12310" ;)) вот такой мя вэб умный

потом комп проверил на наличие вирей, вроде чисто...
Цитата
Это очень хорошие алгоритм. Лучше пожалуй (в смысле универсальности), не придумать!

blink.gif ого... я еще и шарю smile.gif

Цитата
Прежде всего, зациклившихся процессов быть не должно!
Везде где есть рекурсия, надо писать на всякий случай

это у мя не в рекурсивных алгоритма, в обычных циклах бывает в основном в результате очепяток.. бр-рр т.е. опечаток
volvo
28.10.2004 13:16
Цитата
как передавать параметры программе, запуская ее через командную строку?


В меню Run -> Parameters вводишь параметры для передачи программе так, как если бы запускал ее через DOS (но НЕ включая имя самой программы)...

Цитата
как оформить это в самой программе?


Получить доступ к параметрам командной строки можно с помощью функций ParamCount - (возвращает количество параметров) и ParamStr(i) (возвращает i-ый параметр в виде строки). Пример:

Код

var I: Word;
begin
 for I := 1 to ParamCount do
   Writeln(ParamStr(I));
end.
Altair
28.10.2004 13:32
Цитата
это у мя не в рекурсивных алгоритма, в обычных циклах бывает в основном в результате очепяток

Да это неважно, все равно вставляй эту сроку.
Цитата
) как пользоваться операторами input/output? насколько это актуально? зачем нужно(хотя догадываюсь  )? почему упоминается только в старых книгах?

Это не операторы, это переменные ИМХО.... их когда-то использовали ...
Эта переменная типа FILE - определяет файл ввода\вывода по умолчанию... никто этим не пользуется особо, потому что неудобно, и вносит путанницу ИМХО...
Лучше опредедлить файл как FILE и не мучаться smile.gif
Флогримм
28.10.2004 14:19
volvo, спасибо. Усвоил. Ща попробую.


Цитата
Это не операторы, это переменные ИМХО.... их когда-то использовали ...
Эта переменная типа FILE - определяет файл ввода\вывода по умолчанию... никто этим не пользуется особо, потому что неудобно, и вносит путанницу ИМХО...
Лучше опредедлить файл как FILE и не мучаться

ясно

Цитата
ТОлько это должны быть функции.

почему? что будет результатом работы функции? конечная точка пройденного пути(текущая координата)?
Altair
28.10.2004 14:26
Цитата
почему?

Зависит от задачи.

и от способа реализации...
Флогримм
1.11.2004 15:41
вот как на мой взгляд лучше всего решать задачу на заполнение массива значениями по спирали

Код

01|02|03|04
12|13|14|05
11|16|15|06
10|09|08|07


ГЛАВНОЕ установить ПРИОРИТЕТ направеления движения!
в данном примере это (->, \/, <-, /\)


Код
program spirall;
uses crt;
const Size=7;
k=0;
var mas:array[1..size,1..size]of shortint;
i,j,a:integer;

procedure draw;
begin
writeln;
for i:=1 to size do begin
   for j:=1 to size do write(mas[i,j]:2,'|');
   writeln;
   end;
end;
begin
for i:=1 to size do
   for j:=1 to size do mas[i,j]:=k;

clrscr;
i:=1;
j:=1;
mas[i,j]:=1;

for a:=1 to sqr(size) do
begin
write(i,'-',j,' ');
  if mas[i,j+1]=k then begin inc(j); mas[i,j]:=a+1; end else{если пустая ячейка справа, тогода перейти на эту ячейку и присвоить ей очередное значение а...}
  if mas[i+1,j]=k then begin inc(i); mas[i,j]:=a+1; end else {иначе, если пустая ячейка снизу, тогда...}
  if mas[i,j-1]=k then begin dec(j); mas[i,j]:=a+1; end else {иначе если пустая ячейка слева...}
  if mas[i-1,j]=k then begin dec(i); mas[i,j]:=a+1; end; {...пустая сверху...}
end;

draw;
end.


я вот код написал, но где-то ошибка sad.gif у мя такое бывает, вроде все правильно, но могу чассами сидеть искать опечатку или ошибку в алгоритме
если кто в задачу врубился, помогите...

в комментария к коду именно тот приоритет, о котором я говорил, то есть если вся матрица пустая(все ячейки имеют значение 0), а текущее позиция, например, ячейка mas[1,1] то у нее рядом 2 свободных клетки - снизу и справа, но мы не можем двигаться вниз, т.к. у движения вправо более высокий приритет
идея, надеюсь, понятна
задавая, таким образом, приотритет и напрвление можно заполнять матрицы различними "узорами", не только спиральными
volvo
1.11.2004 16:59
Смотри, что я наваял: blink.gif

Код

program spirall;
uses crt;
const Size=7;
k=0;
var mas:array[1..size,1..size]of shortint;
i,j,a:integer;

type
 direction = (go_right, go_down, go_left, go_up);

var current: direction;

function check_direction(i, j: integer): boolean;

 function next_direction(x: direction): direction;
   begin
     if x <> go_up then
       next_direction := succ(x)
     else
       next_direction := go_right
   end;

 var change: boolean;
 begin
   check_direction := true;

   change := false;
   case current of
     go_right:
       if (j = size) then
         change := true
       else
         if mas[i, j+1] <> k then
           change := true
         else exit;
     go_down:
       if (i = size) then
         change := true
       else
         if mas[i+1, j] <> k then
           change := true
         else exit;
     go_left:
       if (j = 1) then
         change := true
       else
         if mas[i, j-1] <> k then
           change := true
         else exit;
     go_up:
       if (i = 1) then
         change := true
       else
         if mas[i-1, j] <> k then
           change := true
         else exit;
   end;

   if change then
     current := next_direction(current);
   check_direction := false
 end;

procedure draw;
begin
writeln;
for i:=1 to size do begin
  for j:=1 to size do write(mas[i,j]:2,'|');
  writeln;
  end;
end;
begin
for i:=1 to size do
  for j:=1 to size do mas[i,j]:=k;

clrscr;
i:=1;
j:=1;
mas[i,j]:=1;


for a := 1 to pred(sqr(size)) do
 begin
   while not check_direction(i, j) do;
   case current of
     go_right: inc(j);
     go_down : inc(i);
     go_left : dec(j);
     go_up   : dec(i);
   end;
   mas[i, j] := succ(a)
 end;

draw;
end.


Добавлено:

Оптимизированный код... :D
Код

Uses Crt;

Const
 size = 7;
 k = 0;

Var
 mas: Array[1 .. size, 1 .. size] Of ShortInt;

Type
 direction = (go_right, go_down, go_left, go_up);

Var
 current: direction;

{$F+}
Function getPred(x: Integer): Integer;
 Begin getPred := Pred(x) end;
Function getSucc(x: Integer): Integer;
 Begin getSucc := Succ(x) end;
{$F-}

Function check_direction(i, j: Integer): Boolean;

 Function next_direction(x: direction): direction;
   Begin
     If x <> go_up Then
       next_direction := Succ(x)
     Else
       next_direction := go_right
   End;

 Type
   TAxis = (isVert, isHoriz);
   TFunc = Function(x: Integer): Integer;

 Function check_range(is: TAxis; range: Integer;
          f: TFunc): Boolean;
   Begin
     check_range := True;
     Case is Of
       isVert:
         If (i = range) Then
           check_range := False
         Else
           If mas[f(i), j] <> k Then
             check_range := False;
       isHoriz:
         If (j = range) Then
           check_range := False
         Else
           If mas[i, f(j)] <> k Then
             check_range := False
     End
   End;

 Begin
   check_direction := True;

   Case current Of
     go_right:
       If check_range(isHoriz, size, getSucc) Then exit;
     go_down:
       If check_range(isVert, size, getSucc) Then exit;
     go_left:
       If check_range(isHoriz, 1, getPred) Then exit;
     go_up:
       If check_range(isVert, 1, getPred) Then exit;
   end;

   current := next_direction(current);
   check_direction := False
 End;


Procedure draw;
 Var
   i, j: Integer;
 Begin
   WriteLn;
   For i := 1 To size Do
     Begin
       For j := 1 To size Do
         Write(mas[i,j]:2,'|');
       WriteLn
     End
 End;

Var
 i, j, a: Integer;

Begin
 For i := 1 To size Do
   For j := 1 To size Do
     mas[i, j] := k;

 ClrScr;
 i := 1; j := 1;
 mas[i, j] := 1;

 For a := 1 To Pred(Sqr(size)) Do
   Begin
     While not check_direction(i, j) Do;
     Case current Of
       go_right: Inc(j);
       go_down : Inc(i);
       go_left : Dec(j);
       go_up   : Dec(i)
     End;
     mas[i, j] := Succ(a)
   End;

 draw
End.
Флогримм
1.11.2004 17:24
Вольво, спасибо, ща попробую разобраться.
А с моим алгоритмом кто-нить поможет? в чем моя ошибка?
volvo
1.11.2004 17:39
Флогримм

У твоего алгоритма есть очень существенный недостаток: ты не проверяешь, достигло ли значение i или j максимально возможного для данной матрицы (т.е. значения size...).
Флогримм
1.11.2004 19:00
volvo
а зачем проверять?
вот смотри: доходим до правого края матрицы, пусть size=4 (т.е. текущая позиция mas[1,4] ), на следующей же итеррации цикла, у нас есть такой условный оператор
Код

...
if mas[i,j+1]=k then begin inc(j); mas[i,j]:=a+1; end else
if mas[i+1,j]=k then begin inc(i); mas[i,j]:=a+1; end else
...

т.е. мы проверяем есть ли у ячейки mas[1,4] "свободный"(значение ячейки =0) сосед: да - inc(j); mas[i,j]:=a+1; нет - переходим к проверке других "свободных" соседей

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

тока че то мой алгоритм неработает smile.gif непойму! вроде все правильно
volvo
1.11.2004 19:13
Цитата
а зачем проверять?

А попробуй откомпилировать и запустить свою программу в таком режиме:


Код

{$R+}
Amro
1.11.2004 21:05
Можно здеся посмотреть
http://forum.pascal.net.ru/forum/index.php?showtopic=162
Тема ещё в том году обсуждалась, там есть несколько вариантов решения :D
Кстати Oleg_Z Неплохо было бы в ЧаВо такую темку создать "Олимпиадные задачи" :yes:
Altair
1.11.2004 21:19
Согласен. Можно. Так кто тебе мешает это сделать? smile.gif ;)
Внесу, как появится материал...
Флогримм
2.11.2004 4:15
Цитата
{$R+}

Код
201 Range check error (Ошибка при проверке границ).

Ошибка генерируется операторами, скомпилированными в состоянии {$R+}, при возникновении одной из следующих ситуаций:

индексное выражение массива находилось вне допустимого диапазона;
была осуществлена попытка присвоить переменной значение, находящееся вне диапазона переменной;
была осуществлена попытка передать значение, находящееся вне допустимого диапазона, в качестве параметра процедуре или функции.


это я понимаю, но у мя же есть проверка! если мы находимся на "приграничной" ячейке массива, мы НЕ МОЖЕМ перещагнуть, выйти за границы массива на следующую ячейку! если size=4 то мы НЕ МОЖЕМ попасть на mas[1,5] и т.д.!!

не оебята, свой код мне ненадо! ненадо за меня код писать, я прошу помочь мне ошибку найти в моем;

можно поробовать такое условие ввести:
Код

...
if (mas[i,j+1]=k) and (j<=size) then begin inc(j); mas[i,j]:=a+1; end else
if (mas[i+1,j]=k) and (i<=size) then begin inc(i); mas[i,j]:=a+1; end else
....


где в моем коде ошибка? помогите найти
volvo
2.11.2004 5:13
Цитата
мы НЕ МОЖЕМ попасть на mas[1,5]


но при прогоне программы мы туда-таки попадаем !!!
blink.gif
Флогримм
2.11.2004 11:11
я понимаю!! прога работает НЕПАРВИЛЬНО! но алгоритм, на мой взгляд - правильный, попробуй устно прогнать его для нескольких значений, все получается вроде

где моя ошибка??
Бродяжник
2.11.2004 14:51
Флогримм
Вы слишком широко понимаете смысл слов "у ячейки есть свободная соседняя ячейка". Вы непроизвольно предполагаете, что это выражение значит, что а) ячейка с индексами i,j существует для данной матрицы, т.е. выражение mas[i,j] имеет смысл, а также, что б) значение mas[i,j] равно заданному к. Однако у компьютера другое мышление. Если при компиляции отключена проверка Range check, то компилятор просто генерит код, в котором адресация [i,j] заменяется относительными адресами памяти. И в этом случае адрес памяти, соответсвующий адресации [1,5] для матрицы 4х4, скорее всего, будет соответствовать адресации [2,1]. И по этому адресу записано корректное с точки зрения программы значение, а именно значение к, указывающее на то, что ячейка свободна. При этом программа не знает, что полученное значение было взято вовсе не из мифической ячейки [1,5]. Она смело переходит к не менее мифической ячейке [1,6] (а на деле [2,2])... и снова находит там значение к. "Рулез!"- думает программа. Поэтому я бы заменил прямое обращение к ячейкам [i,j] на вызов функции
Код
function freemas(i,j: shortint): boolean;
begin
if (i<1) or (i>size) or (j<1) or (j>size)
 then freemas:=false
 else freemas:=(mas[i,j]=k);
end;

При этом общая структура Вашего алгоритма практически не изменится. Просто вместо
Код
if mas[i,j]=k then

будет
Код
if freemas(i,j) then

...Я неправ?
Флогримм
3.11.2004 0:56
Бродяжник!
Ваше сообщение - это то, чего я так долго ждал в этой теме! спасибо огромное!
я с вашей помощи наконец решил эту задачу. Ниже приведен код.

Код

program spirall;
uses crt;
const Size=7;
k=-1; {"пустая ячейка" содержит значение k}
var mas:array[1..size,1..size]of shortint;
i,j,a:integer;

function freemas(i,j: shortint): boolean; {(с) Бродяжник - функция проверяет,}
begin                                     {является ли ячейка с координатами i,j "пустой ячейкой"}
if (i<1) or (i>size) or (j<1) or (j>size)
then freemas:=false
else freemas:=(mas[i,j]=k);
end;

procedure draw; {печать массива}
begin
writeln;
for i:=1 to size do begin
   for j:=1 to size do write(mas[i,j]:2,'|');
   writeln;
   end;
end;

begin
for i:=1 to size do
   for j:=1 to size do mas[i,j]:=k; {заполнение массива "пустыми ячейками"}

clrscr;
i:=1;
j:=1;
mas[i,j]:=1;

{algorithm}
for a:=1 to sqr(size)-1 do
begin
  if (freemas(i-1,j)) and (not freemas(i,j-1)) then begin dec(i); mas[i,j]:=a+1; end else
  if freemas(i,j+1) then begin inc(j); mas[i,j]:=a+1; end else
  if freemas(i+1,j) then begin inc(i); mas[i,j]:=a+1; end else
  if freemas(i,j-1) then begin dec(j); mas[i,j]:=a+1; end else
  continue;
end;
{/algorithm}

draw;
end.

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

Я считаю, что это один из наиболее универсальных алгоритмов, потому что:
1) количество действий минимальное, для матрицы порядка n оно равно n*n
2) изменяя очередность проверки(приоритет направления) и условия перехода на новую ячейку можно задавать многие виды движений! Например, поменял местами только строки и движ-е уже абсолютно иное, чсмотрите

Код
if (freemas(i-1,j)) and (not freemas(i,j-1)) then begin dec(i); mas[i,j]:=a+1; end else
  if freemas(i+1,j) then begin inc(i); mas[i,j]:=a+1; end else
  if freemas(i,j+1) then begin inc(j); mas[i,j]:=a+1; end else
  if freemas(i,j-1) then begin dec(j); mas[i,j]:=a+1; end else continue;


в данном случае движ-е следующее:
Код
01|08|09|16
02|07|10|15
03|06|11|14
04|05|12|13

Не в обиду Вольво будет сказано, но по-моему мой алгоритм более лаконичен и понятен, чем его продвинутые вышеприведенные алгоритмы.

2 Олег_З
если хочешь, можешь включить этот алгоритм в ФАК по матрицам.

только я до сих пор не пойму, почему компиллятор ведет себя именно так, как описал Бродяжник (я понял как ведет, только не понял почему, не логичное поведение какое-то)
Puzik89
12.06.2007 21:02
ДОБРЫЙ ДЕНЬ! Может ли кто - то мне подсказать алгоритм записи элементов матрици по спирали!
1 2 6 7 15
3 5 8 14 16
4 9 13 17 22
10 12 18 21 23
11 19 20 24 25
volvo
12.06.2007 21:06
Это не спираль, а "змейка" - в поиске найдешь...

(P.S. - сегодня день любителей некро...?)
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.