Помощь - Поиск - Пользователи - Календарь
Полная версия: Сортировка 2D массива змейкой
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
MC-Sergey
Данн двумерный массив n на m, состоящий из любых целых чисел.
Необходимо отсортировать массив змейкой по возрастанию(убыванию), как показано на рисунке.
Задавать дополнительный массив запрещено.
Голову уже сломал себе sad.gif
klem4
решалось ... попробуй найти в поиске, сам не пробовал сделать ?
MC-Sergey
Цитата(klem4 @ 21.10.2007 15:48) *

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

Поиск результата не дал...
Решать пробовал, но все время захожу в тупик.
Большая проблема возникает с прямоугольной матрицей и четностью строк или чисел в строке.
То что нашлось поиском, примитивные задачи по сортировке строками и столбцами только в разных направлениях.
мисс_граффити
Цитата(MC-Sergey @ 21.10.2007 15:40) *

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

а эта задача - что-то другое? не сортировка "в разных направлениях"???
MC-Sergey
Цитата(мисс_граффити @ 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
мисс_граффити
запиши все диагонали в индексах.
и посмотри, нет ли закономерности... как изменяется i, как изменяется j
MC-Sergey
Цитата(мисс_граффити @ 21.10.2007 18:33) *

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

вот в этом то и проблема. мне известно что данная задаче рашается, и что определенный алгоритм решения работает как для квадратной матрицы, так и для любой другой.
Если у кого то будут еще идеи по решению данной задачи, пожалуйста пишите.
даже если это просто ваши мысли "вслух".
Мне интересно, почему еще не заинтересовались люди, которые "мозг" этого форума. Задача на мой взгляд очень интересная (в смысле сложности написания кода).
klem4
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
В смысле сложности написания - это порядка 80 строк, вместе с выводом результатов... Ты лучше скажи, что значит "сортировать"? То есть, у тебя есть массив, заполненный какими-то данными, и ты должен его отсортировать так, чтобы пройдя по тому пути, что ты нарисовал, ты получил бы упорядоченные по возрастанию/убыванию элементы массива?
MC-Sergey
Цитата(volvo @ 21.10.2007 19:02) *

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

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

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


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

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


ну сделай "так" и покажи нам. Я больше ни строки не напишу.
volvo
Ну, сортировка - так сортировка 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
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) );

Я это не понимаю.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.