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

Автор: 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

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

Автор: 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

Автор: volvo 22.10.2006 6:08

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

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

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

разброс по времени такой (время замерялось GetTickCount()-ом, соответственно, понятно что FPC):
(замерял только время поиска, время вывода на печать не учитывалось...)

Автор: Bokul 22.10.2006 6:12

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

Автор: volvo 22.10.2006 6:24

Поделюсь, только причешу малость ( может, еще быстрее сделаю ). Но вот это - точно завтра... Кстати, и 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 килобайт ) Кол-во скачиваний: 465


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

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

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

Автор: fanatik 22.10.2006 15:57

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

Автор: Bokul 22.10.2006 23:04

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

Ну так же вроде и надо?:

Автор: volvo 22.10.2006 23:21

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

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

i0 := i; j0 := j;

а у тебя - наоборот, тоже надо подправить... Но на скорость это не повлияет...