Двумерные массивы Опции

[Bush]

Задача на мой взгляд не простая поэтому и лбращаюсь за помощью.
Дана матрица,записанная в текстовый файл.Сдвинуть элементы заданной матрицы в пределах каждого слоя на одну позицию по часовой стрелке.Первый слой образуется из элементов находящихся по периметру матрицы,второй по периметру оставшейся подматрицы и т.д. до заполнения всей матрицы.Полученную матрицу дописать в файл.На экране расскрасить слои разными цветами.
Если есть возможность помогите пожалуйста.

[volvo]

Что именно вызывает затруднения? Чтение матрицы из файла? Поворот по часовой стрелке? ДОзапись в файл? раскрашивание разными цветами разных "слоев"?

Не может же быть, чтобы НИЧЕГО вообще не получалось?

[Bush]

Поворот слоев.

[volvo]

const
  num_row = 5;
  num_col = num_row;

type
  mx = array[1 .. num_row, 1 .. num_col] of integer;

procedure print(const arr: mx);
var i, j: integer;
begin
  for i := 1 to num_row do begin

    for j := 1 to num_col do
      write(arr[i, j]:4);
    writeln;

  end;
  writeln;

end;

procedure rotate_layer(var arr: mx; const n: integer);
var
  buf: array[1 .. num_row * num_col] of integer;
  count: integer;

  function in_buffer(save: boolean; var X: integer): integer;
  begin
    inc(count);

    if save then buf[count] := X
    else X := buf[count];

    in_buffer := 1;
  end;

var
  T, i, j: integer;
  cycle: boolean;
begin
  if n > (num_row div 2) then exit;

  // Цикл будет выполнен 2 раза: сначала при cycle = true, потом при cycle = false
  // Первый проход (при cycle = true) - это запись элементов, составляющих "слой"
  // в буферный массив (in_buffer при первом параметре = true сохраняет значение).
  // На втором проходе будет выполнена обратная процедура: на те же позиции 
  // в матрицу вернется содержимое буфера.

  // А для того, чтобы не делать пустую работу (что сохранили, то и восстановить?
  // Какой смысл в этом, "слой" же надо повернуть), сам буфер "прокручивается",
  // см. комментарии ниже по тексту
  for cycle := true downto false do begin
    count := 0;
    i := n; j := n;
  
    while j <= num_col - n do inc(j, in_buffer(cycle, arr[i, j]));
    while i <= num_row - n do inc(i, in_buffer(cycle, arr[i, j]));
    while j >= n do dec(j, in_buffer(cycle, arr[i, j]));
    inc(j); dec(i);
  
    while i > n do dec(i, in_buffer(cycle, arr[i, j]));
  
    // Вот, собственно. Пришли сюда на первой итерации. Значит, массив buf
    // уже содержит все элементы, которые в матрице составляют "слой".
    // Прокручиваем его, т.е., запоминаем последний, сдвигаем все остальные
    // на одну позицию вправо, и возвращаем бывшие последним элемент в первую
    // позицию. Если теперь вернуть элементы ТОЧНО В ТОМ ЖЕ ПОРЯДКЕ, как их
    // записывали в buf, назад в матрицу, то "слой" окажется повернутым по часовой
    // стрелке. Чтобы повернуть ПРОТИВ часовой - надо прокрутить buf в обратном
    // направлении: сдвинуть все элементы на 1 левее, а первый перенести в конец.
    T := buf[count];
    move(buf[1], buf[2], (count - 1)*sizeof(integer));
    buf[1] := T;
  end;

end;

const
  A: mx = (
    (1, 2, 3, 4, 5),
    (3, 4, 5, 6, 7),
    (7, 8, 9, 0, 2),
    (2, 7, 4, 9, 1),
    (0, 3, 7, 7, 5)
  );

begin
  print(A);
  rotate_layer(A, 2);
  print(A);
end.

Идея понятна?

(моя программа работает только с квадратными матрицами, чтобы было проще отслеживать, есть ли слой с переданным номером в матрице, или его нет... Если нужно - сделай НЕквадратную, тогда надо будет поменять условие выхода)

Сообщение отредактировано: volvo - 19.04.2011 1:54

[Bush]

Вроде ясно.Спасибо.

[Merhaba]

Объясните Пожалуйста, если вам не трудно, принцип работы procedure rotate_layer

[volvo]

Добавил немного комментариев. Так понятнее?

[Merhaba]

Добавил немного комментариев. Так понятнее?

А как можно написать эту программу без использования буферного массива?
может быть, как-нить через новые переменные двигать элементы?

[Lapp]

А как можно написать эту программу без использования буферного массива?
может быть, как-нить через новые переменные двигать элементы?

Извиняюсь за вторжение..

Можно, конечно. Например, можно делать многократный сдвиг на одну позицию. Это, конечно, сильно увеличит время выполнения, но это общий закон: либо память - либо время.
У меня тоже есть заготовочка на эту тему (без буферного массива), вот тут: и опять матрицы
Если там сделать внешний цикл по значениям k, то получишь то, что надо. Плюс уйти от квадратности.

То есть как-то вот так:

  if n<m then k:= n else k:= m;
  k:= k div 2;              {это количество слоев}
  while k>0 do begin        {цикл с уменьшением числа слоев дает нужный сдвиг каждого слоя}
    for i:=1 to k do begin  {цикл по слоям, от внешнего к внутреннему}
      b:= a[i,i];                {сохраняем левый верхний элемент}
      for j:=i to n-i do a[j,i]:= a[j+1,i]; {поэлементно двигаем левую сторону слоя вверх на одну позицию}
      for j:=i to m-i do a[n-i+1,j]:= a[n-i+1,j+1];   {двигаем нижнюю сторону влево}
      for j:=n-i downto i do a[j+1,m-i+1]:= a[j,m-i+1];   {двигаем правую сторону вниз}
      for j:=m-i downto i+1 do a[i,j+1]:= a[i,j]; {двигаем верхнюю сторону вправо кроме последнего элемента}
      a[i,i+1]:= b   {кладем сохраненный элемент во вторую позицию верхней стороны слоя}
    end;
    Dec(k)     {уменьшаем количество сдвигаемых слоев}
  end;

[Merhaba]

Извиняюсь за вторжение..

Можно, конечно. Например, можно делать многократный сдвиг на одну позицию. Это, конечно, сильно увеличит время выполнения, но это общий закон: либо память - либо время.
У меня тоже есть заготовочка на эту тему (без буферного массива), вот тут: и опять матрицы
Если там сделать внешний цикл по значениям k, то получишь то, что надо. Плюс уйти от квадратности.

То есть как-то вот так:

  if n<m then k:= n else k:= m;
  k:= k div 2;              {это количество слоев}
  while k>0 do begin        {цикл с уменьшением числа слоев дает нужный сдвиг каждого слоя}
    for i:=1 to k do begin  {цикл по слоям, от внешнего к внутреннему}
      b:= a[i,i];                {сохраняем левый верхний элемент}
      for j:=i to n-i do a[j,i]:= a[j+1,i]; {поэлементно двигаем левую сторону слоя вверх на одну позицию}
      for j:=i to m-i do a[n-i+1,j]:= a[n-i+1,j+1];   {двигаем нижнюю сторону влево}
      for j:=n-i downto i do a[j+1,m-i+1]:= a[j,m-i+1];   {двигаем правую сторону вниз}
      for j:=m-i downto i+1 do a[i,j+1]:= a[i,j]; {двигаем верхнюю сторону вправо кроме последнего элемента}
      a[i,i+1]:= b   {кладем сохраненный элемент во вторую позицию верхней стороны слоя}
    end;
    Dec(k)     {уменьшаем количество сдвигаемых слоев}
  end;

Спасибо Вам Большое за помощь!!!
а как можно переделать код, где 1-ый слой будет сдвигаться на к элементов, 2-ой на к-1 элементов, .... , где к - число слоев ?

[Lapp]

а как можно переделать код, где 1-ый слой будет сдвигаться на к элементов, 2-ой на к-1 элементов, .... , где к - число слоев ?

Что переделать??
Ты читай ВНИМАТЕЛЬНО, что тебе пишут.
А заодно, запусти код и посмотри, что он делает.
И тогда, может, не будешь спрашивать, как сделать то, что уже сделано..

[Merhaba]

Что переделать??
Ты читай ВНИМАТЕЛЬНО, что тебе пишут.
А заодно, запусти код и посмотри, что он делает.
И тогда, может, не будешь спрашивать, как сделать то, что уже сделано..

Объясните Пожалуйста, что такое Dec(k) ?
Я просто больше пишу проги на Java, чем на Паскале... немного подзабыл

Сообщение отредактировано: Merhaba - 21.04.2011 0:31

[Lapp]

Объясните Пожалуйста, что такое Dec(k) ?

Это эквивалентно выражению

k := k-1;

Или, если хочешь, то же самое, что

k-= 1;

на Си или Java.
Dec является сокращение слова decrease (уменьшать). Есть также еще процедура Inc (от increase) для увеличения на единицу.

Я просто больше пишу проги на Java, чем на Паскале... немного подзабыл

Нет проблем )

[-TarasBer-]

> Это, конечно, сильно увеличит время выполнения, но это общий закон: либо память - либо время.

В данном случае это не так.

Для того, чтобы сделать циклический сдвиг массива из m элементов на n, надо НОД(m,n) раз сделать такую операцию: взять k-ый элемент (k - это номер операции, то есть мы делаем это сначала для k=0, потом для k=1, и так далее до k=НОД(m,n)-1) и поменять его местами с k+n-ым. Потом k+n-ый поменять с k+n+n b так далее, пока не окажется, что новый элемент, с которым надо менять, имеет индекс k. Вообще в цепочке длины L надо выполнить L-1 обмен. Кстати, L = m / НОД(m,n)

Короче, если грузануть хитрую алгебру, то можно без затрат обойтись без доп.массива.

[Lapp]

> Это, конечно, сильно увеличит время выполнения, но это общий закон: либо память - либо время.

В данном случае это не так.

Для того, чтобы сделать циклический сдвиг массива из m элементов на n, надо НОД(m,n) раз сделать такую операцию: взять k-ый элемент (k - это номер операции, то есть мы делаем это сначала для k=0, потом для k=1, и так далее до k=НОД(m,n)-1) и поменять его местами с k+n-ым. Потом k+n-ый поменять с k+n+n b так далее, пока не окажется, что новый элемент, с которым надо менять, имеет индекс k. Вообще в цепочке длины L надо выполнить L-1 обмен. Кстати, L = m / НОД(m,n)

Короче, если грузануть хитрую алгебру, то можно без затрат обойтись без доп.массива.

Я в трансе
Как будет время, попробую реализовать.
Тарас, мож тиснешь для FAQ?

И, пожалуйста, кинь тут свой пост (а не гостя). Я понимаю, что ты не "кармадрочер" (модное словцо с твоей же легкой руки, подхваченное volvo, но я не могу писать его иначе как в кавычках)), но ставить +1 из другой темы - неправильно.. ))

[Merhaba]

Это эквивалентно выражению

k := k-1;

Или, если хочешь, то же самое, что

k-= 1;

на Си или Java.
Dec является сокращение слова decrease (уменьшать). Есть также еще процедура Inc (от increase) для увеличения на единицу.

Нет проблем )

Объясните Пожалуйста, что такое

b:= a[i,i]; 

?
Если переменная, то какого она типа?
И зачем мы сохраняем левый верхний элемент?
Что мы будем выводить на дисплей?

Сообщение отредактировано: Merhaba - 22.04.2011 13:31

[TarasBer]

Ну, в данном случае это извращение довольно просто реализуется.
А вот для случая обмена a и 2*a подобное провернуть не удастся (если помнишь ту старую тему), так как задача сводится к задаче дискретного логарифмирования, а она за время разумного порядка не решается. (Это используется в криптографии, кстати).
А слово это не я придумал. Это вроде с какого-то сайтика с развитой системой рейтинга (и вытекающими из неё последствиями) пошло.

[Lapp]

Объясните Пожалуйста, что такое

b:= a[i,i]; 

?
Если переменная, то какого она типа?

Естественно, b - переменная. Того же типа, что и элементы массива.

И зачем мы сохраняем левый верхний элемент?

Ты играл в игру "15" когда нибудь? Ее еще стали называть "пятнашки", хотя это неправильно. Знаешь? такая коробочка, а в ней квадратики с чиселками. Эти квадратики надо перемещать. Там цель - выстроить по порядку, но ты на это забей. Твой случай - это двигать слои. Верно?
Так вот, чтобы двигать, в этой игре есть ПУСТАЯ клетка. На ее место можно передвинуть соседнюю - и тогда освободится соседняя.. И так далее. А если бы не было пустой клетки - как тогда двигать? Никак! Вот поэтому я вынимаю один элемент сначала (кладу в буферную переменную b). А потом, когда процесс сдвига слоя закончен - я кладу ее обратно на нужное место.
Так понятнее?

Что мы будем выводить на дисплей?

Сначала - исходный массив. Потом - что получилось..
Ладно, вот тебе, только разберись, пожалуйста.

const
  n= 6;
  m= 7;

var
  a: array [1..n,1..m] of integer;
  i,j,k,l,b: integer;

begin
  {заполняем}
  for i:=1 to n do for j:=1 to m do a[i,j]:= (i-1)*m+j;
  WriteLn('before:');
  for i:=1 to n do begin
    for j:=1 to m do Write(a[i,j]:3);
    WriteLn
  end;

  {двигаем}
  if n<m then k:= n else k:= m;
  k:= k div 2;              {это количество слоев}
  while k>0 do begin        {цикл с уменьшением числа слоев дает нужный сдвиг каждого слоя}
    for i:=1 to k do begin  {цикл по слоям, от внешнего к внутреннему}
      b:= a[i,i];                {сохраняем левый верхний элемент}
      for j:=i to n-i do a[j,i]:= a[j+1,i]; {поэлементно двигаем левую сторону слоя вверх на одну позицию}
      for j:=i to m-i do a[n-i+1,j]:= a[n-i+1,j+1];   {двигаем нижнюю сторону влево}
      for j:=n-i downto i do a[j+1,m-i+1]:= a[j,m-i+1];   {двигаем правую сторону вниз}
      for j:=m-i downto i+1 do a[i,j+1]:= a[i,j]; {двигаем верхнюю сторону вправо кроме последнего элемента}
      a[i,i+1]:= b   {кладем сохраненный элемент во вторую позицию верхней стороны слоя}
    end;
    Dec(k)
  end;

  {выводим}
  WriteLn('after:');
  for i:=1 to n do begin
    for j:=1 to m do Write(a[i,j]:3);
    WriteLn
  end;
  ReadLn
end.