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

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

Форум «Всё о Паскале» _ Задачи _ Матрица и массив

Автор: fanatik 22.10.2006 3:02

Кто-нить помогите решить задачку. Текст следующий: Даны целочисленная матрица X[1:n,1:m] и целочисленный массив Z[1:r]. Обнулить элементы матрицы X, которых нет в массиве Z и запомнить обнулённые элементы. Буду очень благодарен за помощь.

Автор: мисс_граффити 22.10.2006 3:05

что значит запомнить?

Автор: SuperMozg 22.10.2006 4:00

Если я правильно понял, то надо запомнить индексы обнуленных элементов матрицы:

const
r=10;
n=5;
m=7;
type
rec = record
i0,j0: integer;
end;
index = array[1..r] of rec; {массив записей для хранения индексов обнул. эл-тов}

massiv = array[1..r] of integer;
matrix = array[1..n, 1..m] of integer;
var
mas: index;
x: matrix;
z: massiv;
i, j, k: integer;
count: integer; {кол-во обнул. эл-тов}

begin
count:= 0;
for k:= 1 to r do
for i:= 1 to n do
for j:= 1 to m do
if (x[i,j] = z[k]) and (x[i,j]<>0) then
begin
x[i,j]:= 0;
count:= count+1;
mas[count].i0:= i;
mas[count].j0:= j;
end;
for i:= 1 to count do
writeln(mas[i].i0, mas[i].j0);
readln;
end.

Автор: Bokul 22.10.2006 4:13

uses crt;
const
n=10;
m=10;
r=10;
type
coor=record
x,y:byte;
end;
var
x:array[1..n,1..m] of integer;
z:array[1..r] of integer;
mem:array[1..n*m] of coor;
max:integer;
i,j,k:byte;
b:boolean;
begin
clrscr;
for i:=1 to n do
begin
for j:=1 to m do
begin
x[i,j]:=random(10);
write(x[i,j],' ');
end;
writeln;
end;
writeln('-------------------------------------');
for k:=1 to r do
begin
z[k]:=random(10);
write(z[k],' ');
end;
writeln;
writeln('-------------------------------------');
b:=false;
max:=0;
for i:=1 to n do
for j:=1 to m do
begin
for k:=1 to r do
if z[k]=x[i,j] then
b:=true;
if b=false then
begin
x[i,j]:=0;
inc(max);
mem[max].x:=j;
mem[max].y:=i;
end
else
b:=false;
end;
for i:=1 to max do
write('x=',mem[i].x,' y=',mem[i].y,'| ');
readln;
end.

Автор: volvo 22.10.2006 4:22

Ребята, это все прекрасно, конечно, но решение "в лоб" никогда быстротой не отличалось...

Заметьте, о величинах M, N и R ничего не сказано. А если они будут порядка сотен? Представляете себе время работы программы?

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

Автор: SuperMozg 22.10.2006 4:39

Цитата(volvo @ 22.10.2006 9:22) *


Заметьте, о величинах M, N и R ничего не сказано. А если они будут порядка сотен? Представляете себе время работы программы?

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


Это все верно, но задачка-то явно учебная... Вряд ли в ней нужны такие навороты. Если впихнуть в код бинарный поиск да еще и сортировку Хоара, то точно будет перебор...

Автор: Bokul 22.10.2006 4:43

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

uses crt;
const
r=10;
n=5;
m=7;type
rec = record
i0,j0: integer;
end;
index = array[1..r] of rec;
massiv = array[1..r] of integer;
matrix = array[1..n, 1..m] of integer;
var mas: index;
x: matrix; z: massiv;
i, j, k: integer;
count: integer;
begin
clrscr;
for i:=1 to n do
begin
for j:=1 to m do
begin
x[i,j]:=random(10);
write(x[i,j],' ');
end;
writeln;
end;
writeln('-------------------------------------');
for k:=1 to r do
begin
z[k]:=random(10);
write(z[k],' ');
end;
writeln;
writeln('-------------------------------------');
count:= 0;
for k:= 1 to r do
for i:= 1 to n do
for j:= 1 to m do
if (x[i,j] = z[k]) and (x[i,j]<>0) then
begin
x[i,j]:= 0;
count:= count+1;
mas[count].i0:= i;
mas[count].j0:= j;
end;
for i:= 1 to count do
write('y=',mas[i].i0, ' x=',mas[i].j0,'|');
readln;
end.


Ошибка в цикле проверки - надо сверять каждый элемент матрицы X со всема элементами массива Z, ты же сравниваешь только с одним.



volvo,
n=100;
m=500;
r=100;
Время - где-то секунда...

Автор: volvo 22.10.2006 4:50

Цитата
Время - где-то секунда...
Ты на чем компилировал? FPC? На TP будет больше... Попробую, завтра напишу, что получилось...

Цитата
но задачка-то явно учебная...
И что? Ограничений на средства достижения результата поставлено не было. Если тебя НЕ интересует оптимизированный вариант - дело твое...

Цитата
Если впихнуть в код бинарный поиск да еще и сортировку Хоара, то точно будет перебор...
Хоар на больших значениях может и захлебнуться. Я бы не стал его использовать... Есть много других методов сортировки...

Автор: Bokul 22.10.2006 4:52

Цитата
Ты на чем компилировал? FPC? На TP будет больше... Попробую, завтра напишу, что получилось...

FPC

Автор: volvo 22.10.2006 6:08

Bokul, не стал я ждать до завтра, сделал сегодня smile.gif

На не очень больших значениях тесты показывают примерно одинаковое время (порядка 16-20 ms), но при значениях:

r=1200;
n=1100;
m=1200;


разброс по времени такой (время замерялось GetTickCount()-ом, соответственно, понятно что FPC):
Цитата(Console)
Volvo:
359

Bokul:
8437
(замерял только время поиска, время вывода на печать не учитывалось...)

Автор: Bokul 22.10.2006 6:12

Цитата

Volvo:
359

Bokul:
8437

Впечетляет.
volvo, кодом поделишься?

Автор: volvo 22.10.2006 6:24

Поделюсь, только причешу малость ( может, еще быстрее сделаю smile.gif ). Но вот это - точно завтра... Кстати, и http://forum.pascal.net.ru/index.php?showtopic=3065 и http://forum.pascal.net.ru/index.php?showtopic=4159 брал с нашего форума...

Автор: volvo 22.10.2006 15:04

Bokul,
вот такой код получился (код тестовый, поэтому в нем присутствуют http://forum.pascal.net.ru/index.php?s=&showtopic=3895&view=findpost&p=34459 {$ifdef}...{$else}...{$endif}, за объяснениями - по ссылке)...

Прикрепленный файл  speed_test.pas ( 3.37 килобайт ) Кол-во скачиваний: 489


Чтобы прогнать тестовое значение, и посморреть правильность работы алгоритма достаточно определить условный символ TEST_SMALL (добавлением строки {$define TEST_SMALL} в начало программы, сейчас она уже добавлена), при этом на печать будет выведена и исходная матрица, и массив, и результат, т.е. все позиции элементов в матрице. Для тестирования на скорость (при больших массивах) эту строчку надо либо удалить, либо между символами { и $ добавить пробел (тогда эта строка превратится в комментарий), и перекомпилировать программу (!!!), и программа будет тестироваться с большими значениями, БЕЗ вывода на печать, только сам процесс поиска. То же самое касается и автора - с определенным __BOKUL будет выполняться алгоритм Bokul-а, иначе - мой...

Вот что выдала программа у меня:

Цитата(Console)
Volvo:
391

Bokul:
11356


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

Автор: fanatik 22.10.2006 15:57

Ребята, спасибо! Вы мне очень помогли good.gif Чтоб я без вас делал просто не представляю!!!!

Автор: Bokul 22.10.2006 23:04

volvo, начал разбираться.
Вот, что-то я не понимаю :

Цитата
Есть подозрение, что он находит элементы неправильно, ибо на показанных местах в матрице стоят также и НЕ присутствующие в массиве элементы

Ну так же вроде и надо?:
Цитата
Обнулить элементы матрицы X, которых нет в массиве Z и запомнить обнулённые элементы

Автор: volvo 22.10.2006 23:21

blink.gif Ну, да... Я почему-то пропустил слово "НЕТ"... Тогда в моем алгоритме "<>" поменять на "=".

Кстати, обнаружилось еще, что у нас i/j неодинаково заносятся в структуры. У меня

i0 := i; j0 := j;
а у тебя - наоборот, тоже надо подправить... Но на скорость это не повлияет...