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

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Сортировка 2D массива змейкой

Автор: MC-Sergey 21.10.2007 17:46

Данн двумерный массив n на m, состоящий из любых целых чисел.
Необходимо отсортировать массив змейкой по возрастанию(убыванию), как показано на рисунке.
Задавать дополнительный массив запрещено.
Голову уже сломал себе sad.gif


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

Автор: klem4 21.10.2007 17:48

решалось ... попробуй найти в поиске, сам не пробовал сделать ?

Автор: MC-Sergey 21.10.2007 18:40

Цитата(klem4 @ 21.10.2007 15:48) *

решалось ... попробуй найти в поиске, сам не пробовал сделать ?

Поиск результата не дал...
Решать пробовал, но все время захожу в тупик.
Большая проблема возникает с прямоугольной матрицей и четностью строк или чисел в строке.
То что нашлось поиском, примитивные задачи по сортировке строками и столбцами только в разных направлениях.

Автор: мисс_граффити 21.10.2007 18:57

Цитата(MC-Sergey @ 21.10.2007 15:40) *

То что нашлось поиском, примитивные задачи по сортировке строками и столбцами только в разных направлениях.

а эта задача - что-то другое? не сортировка "в разных направлениях"???

Автор: MC-Sergey 21.10.2007 19:14

Цитата(мисс_граффити @ 21.10.2007 16:57) *

а эта задача - что-то другое? не сортировка "в разных направлениях"???

тут по диагонали.
Если не понятно с картинки, вот в цифрах чтобы было понятнее(напрвление сортировки):
01 02 06 07 14 15
03 05 08 13 16 21
04 09 12 17 20 22
10 11 18 19 23 24


Если можно, в кратце как работает алгоритм и код программы(если есть; в Паскале)
Вся надежда на вас, у меня на этот момент идеи закончились свои... unsure.gif

Автор: мисс_граффити 21.10.2007 20:40

запиши все диагонали в индексах.
и посмотри, нет ли закономерности... как изменяется i, как изменяется j

Автор: MC-Sergey 21.10.2007 20:41

Цитата(мисс_граффити @ 21.10.2007 18:33) *

Матрица, по-моему, может быть только квадратной.

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

Автор: klem4 21.10.2007 20:59

uses crt;

const
n = 5;
m = 3;

type
TArray = array [1..n, 1..m] of Integer;

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

procedure Create(var arr: TArray);
var
i, j, value: integer;
begin

value := 1;

i := 1;
j := 1;

arr[i, j] := value;

repeat

if j < m then begin
inc(j);
inc(value);
arr[i, j] := value;
end else begin
inc(i);
inc(value);
arr[i, j] := value;
end;

while (j > 1) and (i < n) do begin
dec(j);
inc(i);
inc(value);
arr[i, j] := value;
end;

if i < n then begin
inc(i);
inc(value);
arr[i, j] := value;
end else if j < m then begin
inc(j);
inc(value);
arr[i, j] := value;
end;

while (i > 1) and (j < m) do begin
dec(i);
inc(j);
inc(value);
arr[i, j] := value;
end;

until (i = n) and (j = m);
end;

var
arr: TArray;
begin
clrscr;
Create(arr);
Print(arr);
readln;
end.

Автор: volvo 21.10.2007 21:02

В смысле сложности написания - это порядка 80 строк, вместе с выводом результатов... Ты лучше скажи, что значит "сортировать"? То есть, у тебя есть массив, заполненный какими-то данными, и ты должен его отсортировать так, чтобы пройдя по тому пути, что ты нарисовал, ты получил бы упорядоченные по возрастанию/убыванию элементы массива?

Автор: MC-Sergey 21.10.2007 21:21

Цитата(volvo @ 21.10.2007 19:02) *

В смысле сложности написания - это порядка 80 строк, вместе с выводом результатов... Ты лучше скажи, что значит "сортировать"? То есть, у тебя есть массив, заполненный какими-то данными, и ты должен его отсортировать так, чтобы пройдя по тому пути, что ты нарисовал, ты получил бы упорядоченные по возрастанию/убыванию элементы массива?

Да ты прав... Я вроде написал об этом в задании (см. первый пост).

По твоему решению:
klem4, а вот и не так...
Массив задается рандомом (или вручную - не важно) и уже потом сортируется, как ты сказал ранее.

Автор: klem4 21.10.2007 21:43

Цитата
Массив задается рандомом (или вручную - не важно)


dry.gif а я по твоему телепат ?!

Цитата
а вот и не так...


ну сделай "так" и покажи нам. Я больше ни строки не напишу.

Автор: volvo 21.10.2007 21:48

Ну, сортировка - так сортировка smile.gif

const
max_col = 6;
max_row = 4;

type
tdirection = (right, left_down, down, right_up);
const
delta: array[tdirection] of record X, Y: integer end =
( (X: 1; Y: 0), (X:-1; Y: 1), (X: 0; Y: 1), (X: 1; Y:-1) );

function get_next(var dir: tdirection; var col, row: integer): boolean;
var
new_col, new_row: integer;
ok: boolean;
begin
get_next := false;
if (row = max_row) and (col = max_col) then exit;

case dir of
right:
if row = 1 then dir := left_down
else dir := right_up;
down:
if col = 1 then dir := right_up
else dir := left_down;
end;

repeat

new_col := col + delta[dir].x; new_row := row + delta[dir].y;
ok := (new_col >= 1) and (new_col <= max_col) and
(new_row >= 1) and (new_row <= max_row);

if not ok then
case dir of
right: dir := down;
left_down: dir := down;
down: dir := right;
right_up: dir := right;
end;

until ok;
col := new_col; row := new_row;
get_next := true;

end;

var
a: array[1 .. max_row, 1 .. max_col] of integer;
dir: tdirection;

i, j,
_col, _row,
first_row, first_col, mx_row, mx_col: integer;
value: integer;
T: integer;

begin
for _row := 1 to max_row do
for _col := 1 to max_col do
a[_row, _col] := random(20);

for i := 1 to max_row * max_col - 1 do begin

_col := 1; _row := 1;
dir := right_up;

for j := 1 to pred(i) do get_next(dir, _col, _row);
first_col := _col; first_row := _row;

mx_row := first_row; mx_col := first_col;
repeat

if a[mx_row, mx_col] > a[_row, _col] then begin
mx_row := _row; mx_col := _col;
end

until not get_next(dir, _col, _row);
T := a[first_row, first_col];
a[first_row, first_col] := a[mx_row, mx_col];
a[mx_row, mx_col] := T;

end;

for _row := 1 to max_row do begin
for _col := 1 to max_col do begin
write(a[_row, _col]:4);
end;
writeln;
end;

end.


Попробуй разобраться...

Автор: MC-Sergey 21.10.2007 22:46

volvo дааа... ну ты и голова! blink.gif good.gif
А более простого рещения точно нет? rolleyes.gif
Пытаюсь разобраться, пока с трудом...
Не можешь в кратце изложить как программа работает. А то я путаюсь в твоих тщательно продуманных лабиринтах. wacko.gif

Как то бы вот это заменить

const
delta: array[tdirection] of record X, Y: integer end =
( (X: 1; Y: 0), (X:-1; Y: 1), (X: 0; Y: 1), (X: 1; Y:-1) );

Я это не понимаю.