Версия для печати темы

Автор: Lidroot 27.10.2005 20:31

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

Автор: volvo 27.10.2005 20:33

To: Lidroot
Каким именно способом? По столбцам? По строкам? Или просто отсортировать все данные, которые находятся НИЖЕ главной диагонали?

Автор: Lidroot 27.10.2005 21:03

Отсортировать ВСЕ данные ниже главной диагонали.

Автор: volvo 27.10.2005 21:07

Хорошо... Вот пример ДО сортировки:

Как эта матрица должна выглядеть ПОСЛЕ сортировки?

Автор: Lidroot 27.10.2005 21:19

Должно что то вроде

Автор: volvo 27.10.2005 21:35

Только не путай главную и побочную диагональ... Ты сделал относительно побочной... Вот относительно главной:

const
  n = 5;
type
  matrix = array[1 .. n, 1 .. n] of integer;
const
  mx: matrix =
    ((1, 2, 3, 4, 5),
     (2, 3, 4, 5, 6),
     (7, 6, 3, 2, 5),
     (3, 8, 5, 0, 9),
     (9, 1, 7, 5, 8));

procedure print_matrix(m: matrix);
var i, j: integer;
begin
  for i := 1 to n do begin
    for j := 1 to n do
      write(m[i, j]:4);
    writeln;
  end;
end;

var
  below: array[1 .. n*n] of integer;
  i, j, count: integer;
  T: integer;

begin
  { Если нужно вводить матрицу - вводи здесь... }

  print_matrix(mx); { До сортировки }
  count := 0;

  for i := 1 to n do
    for j := 1 to i do
      if i <> j then begin
        inc(count); below[count] := mx[i, j];
      end;

  { Сама сортировка }
  For i := 1 To count Do
    For j := count DownTo i+1 Do
      If below[Pred(j)] > below[j] Then { < } Begin
        T := below[Pred(j)]; below[Pred(j)] := below[j]; below[j] := T
      End;

  count := 0;
  for i := 1 to n do
    for j := 1 to i do
      if i <> j then begin
        inc(count); mx[i, j] := below[count];
      end;

  writeln('После сортировки:');
  print_matrix(mx);

end.

Автор: Lidroot 27.10.2005 21:51

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

Автор: volvo 27.10.2005 22:15

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

Автор: Lidroot 27.10.2005 22:30

Понятно. У меня просто было еще одно задание: Сортировка матрицы, так я делал через матрицу. Придется менять еще раз спасибо

Автор: volvo 28.10.2005 0:55

To: Lidroot
Я тут... :smoke: :smoke: ... подумал немного... Что-то у меня получилось, и не совсем сложно, отсортировать матрицу БЕЗ дополнительного массива. Вот так:

const
  n = 5;
  count = (n * pred(n)) div 2;
type
  matrix = array[1 .. n, 1 .. n] of integer;
const
  mx: matrix =
    ((1, 2, 3, 4, 5),
     (2, 3, 4, 5, 6),
     (7, 6, 3, 2, 5),
     (3, 8, 5, 0, 9),
     (9, 1, 7, 5, 8));

procedure get_index(var ix, jx: integer; k: integer);
var
  finished: boolean;
  i, j: integer;
begin
  for i := 1 to n do
    for j := 1 to i do
      if i <> j then begin
        dec(k);
        if k = 0 then begin
          ix := i; jx := j;
        end
      end;
end;

procedure print_matrix(m: matrix);
var i, j: integer;
begin
  for i := 1 to n do begin
    for j := 1 to n do
      write(m[i, j]:4);
    writeln;
  end;
end;

var
  i, j: integer;
  T: integer;

  j_ix, j_jx, pj_ix, pj_jx: integer;

begin
  print_matrix(mx);

  { sort }
  For i := 1 To count Do
    For j := count DownTo i+1 Do begin
      get_index(j_ix, j_jx, j);
      get_index(pj_ix, pj_jx, pred(j));
      If mx[pj_ix, pj_jx] > mx[j_ix, j_jx] Then Begin
        T := mx[pj_ix, pj_jx];
        mx[pj_ix, pj_jx] := mx[j_ix, j_jx];
        mx[j_ix, j_jx] := T
      End;
    end;

  writeln('sorted:');
  print_matrix(mx);

end.

Автор: klem4 29.10.2005 17:37

Могу предложить еще вот такой вариант без дополнительного массива, возможно будет даже быстрее :

   repeat

      flag := true;

      for i1 := 2 to n do
       for j1 := n-i1+2 to n do
        for i2 := 2 to n do
         for j2 := n-i2+2 to n do
          if ((i2>i1)or((i2=i1)and(j2>j1))) and not(mx[i1,j1]<=mx[i2,j2]) then begin
             flag := false;
             T := mx[i1,j1];
             mx[i1,j1] := mx[i2,j2];
             mx[i2,j2] := T;
          end;

   until flag;

:smoke:

Автор: volvo 29.10.2005 17:44

To: klem4

Вполне возможно, только ЭТО не сортирует элементы ниже главной диагонали... :no: Сортирует ниже побочной

Автор: Lidroot 29.10.2005 22:31

я тоже немного порыл и нашел неплохой пример

procedure sort(i,j:integer);
var i1,j1,tmp:integer;
begin
for i1:=1 to i do
for j1:=1 to 5 do
if (mas[i,j]>mas[i1,j1]) and ((i1<i) or (j1<j)) then
begin
tmp:=mas[i,j];
mas[i,j]:=mas[i1,j1];
mas[i1,j1]:=tmp;
sort(i1,j1);
end;
end;

for i:=1 to 5 do
for j:=1 to 5 do
sort(i,j);

Но потом хорошо подумав, понял что для чела(которому я помогаю) сортировку надо делать попроще...

P.S. Я сам пытался через матрицу, но как то не шла мысля

Автор: volvo 29.10.2005 22:36

To: Lidroot
А ты знаешь, что делает тот алгоритм, который ты привел? Он сортирует ВСЮ матрицу построчно. Запусти программу и убедись... По-моему, требовалось нечто другое

Автор: Lidroot 29.10.2005 23:53

for i:=1 to 5 do
for j:=1 to i do
sort(i,j);

тот был просто пример, изменяешь одну буковку и усе работает