Вхождение матрицы в матрицу, Вхождение матрицы в матрицу Опции

[Xopek]

Дано задание написать программу...
Тема: дихотомический поиск в матрице на включение.
Короче надо определить включает ли матрица A в себя матрицу B.
Подскажите плиз теорию и если есть мона исходники.

[klem4]

Полный перебор не подойдет ? Не очень понимаю куда тут пришпилить дихотомию, это вроде метод решения уравнений основанный на делении о трезка пополам ..

или имеется в виду вот такое вхождение :

A :

1234
5678
9000

B :

23
67

Результат : TRUE

1234
5678
9000

Сообщение отредактировано: klem4 - 21.11.2005 1:12

[Altair]

Если как сказал Клем, то вот я тут написал кое что

{$R-}
Type
  TType = Integer;
Type
  PVector = ^TVector;
  TVector = Array[1 .. 1] of TType;
  PDynMatrix = ^TDynMatrix;
  TDynMatrix = Array[1 .. 1] of PVector;

Var
  A,B: PDynMatrix;
  n1,n2, m1, m2, i, j, k, l, s, si,sj: Word;
  pr:boolean;
Begin
  pr:=false;
  Write('n1 = '); ReadLn(n1);
  Write('m1 = '); ReadLn(m1);
  Write('n2 = '); ReadLn(n2);
  Write('m2 = '); ReadLn(m2);
  GetMem(A, n1 * SizeOf(PVector));
  GetMem(B, n2 * SizeOf(PVector));
  For i := 1 To n1 Do     GetMem(A^[i], m1 * SizeOf(TType));
  For i := 1 To n2 Do     GetMem(B^[i], m2 * SizeOf(TType));

  //enter matrix

  For i := 1 To n1 Do begin
    For j := 1 To m1 Do begin
      write('a[',i,',',j,']='); readln(A^[I]^[J]);
    end;
   end;
  For i := 1 To n2 Do begin
    For j := 1 To m2 Do begin
      write('b[',i,',',j,']='); readln(B^[I]^[J]);
    end;
   end;

  for i:=1 to n1 do begin
    for j:=1 to m1 do begin
      if a^[i]^[j] = b^[1]^[1] then begin
         s:=0;
         for k:=1 to n2 do for l:=1 to m2 do begin
           if a^[i+k-1]^[j+l-1] = b^[k]^[l] then inc(s);
         end;
         if s=sqr(n2) then begin pr:=true; si:=i; sj:=j end
       end
     end
   end;

  if pr then writeln('IN!!!',' i=',si,' j=',sj) else writeln('not found');readln;
  For i := 1 To n1 Do  FreeMem(A^[i], m1 * SizeOf(TType));
  FreeMem(A, n1 * SizeOf(PVector));
  For i := 1 To n2 Do  FreeMem(b^[i], m2 * SizeOf(TType));
  FreeMem(b, n2 * SizeOf(PVector));

End.

n1 x m1 - размерность 1 матрицы (А)
n2 x m2 - размерность 2 матрицы (В)
выводит Входит или нет и если да то номер строки и столбца

[volvo]

Да простит меня Altair, но по-моему можно немного ускорить процесс поиска.
Для простоты массивы - статические...

const
  n1 = 8; m1 = 8;
  n2 = 3; m2 = 3;

  a_big: array[1 .. n1, 1 .. m1] of integer = (
    (1, 2, 3, 4, 5, 6, 7, 8),
    (6, 3, 4, 5, 6, 7, 8, 9),
    (1, 7, 2, 9, 3, 7, 3, 2),
    (6, 2, 4, 5, 6, 7, 0, 2),
    (5, 3, 3, 7, 3, 2, 5, 2),
    (1, 8, 2, 5, 1, 9, 0, 0),
    (0, 9, 2, 5, 6, 7, 2, 1),
    (2, 0, 3, 0, 6, 2, 5, 7)
  );

  a_small: array[1 .. n2, 1 .. m2] of integer = (
    (4, 5, 6),
    (5, 6, 7),
    (9, 3, 7)
  );


var
  i, j, k, l: integer;
  bad: boolean;

begin
  for i:=1 to n1 - n2+1 do begin { Зачем перебирать ВСЕ элементы строки?  }
    for j:=1 to m1 - m2+1 do begin
      if a_big[i, j] = a_small[1, 1] then begin

        bad := false;

        k := 1;
        repeat

          l := 1;
          repeat

            bad := a_big[i + k - 1, j + l - 1] <> a_small[k, l];

            inc(l);
          { Ну и здесь не идем до конца, если уже нашли неверный элемент }
          until (l > m2) or bad; 
          inc(k);
        until (k > n2) or bad;

        if not bad then writeln('found: ', i:3, j:3);
      end
    end
  end;
end.

[Altair]

{ Зачем перебирать ВСЕ элементы строки?  }

действительно!

[Xopek]

Да с этим вы правы спасибо.. Но как же с дихотомическим поиском быть - возможно ли это?

[hiv]

Даже не знаю, возможно ли это вообще! Ибо метод дихотомии справедлив только в том случае, если функция непрерывная, а в задаче дана матрица дискретных значений.