Поиск в матрице n*n

[ilovb]

Тема перекликается с http://oberspace.dyndns.org/index.php/topic,591.0.html
Яркий пример на тему "ниасилил while (и линейный поиск)"

Выдержка из http://kpolyakov.blogspot.ru/2012/10/break-break.html

Пример 5. Разработать функцию, которая определяет, если ли в квадратной матрице элемент, равный заданному значению.

Будем предполагать, что введен тип данных
type Matrix = array[1..N,1..N] of integer;
Тогда функцию можно написать так:
function Find(const A: Matrix; X: integer): boolean;
var i, j: integer;
begin
  Result := True;
  for i:=1 to N do
    for j:=1 to N do
      if A[i,j] = X then exit;
  Result := False
end;
Здесь оператор exit фактически выполняет роль break для вложенного цикла. С формальной точки зрения у функции два выхода. В общем, «я своим ученикам никогда такое не зачту» — уже слышу я от учителей информатики.

А давайте подумаем, какие альтернативы? Можно вот так:
function Find(const A: Matrix; X: integer): Boolean;
var i, j: integer;
label finish;
begin
  Result := True;
  for i:=1 to N do
    for j:=1 to N do
      if A[i,j] = X then goto finish;
  Result := False;
finish:
end;
Но тут вообще «криминал» — метка и goto! Хотя по сути ничего не изменилось, тот же выход из вложенного цикла.

Конечно, здесь можно использовать исключение:
function Find(const A: Matrix; X: integer): Boolean;
var i, j: integer;
begin
  Result := False;
  try
    for i:=1 to N do
      for j:=1 to N do
        if A[i,j] = X then
          raise Exception.Create('');
  except
    Result := True
  end
end;
Но ведь это далеко не «исключительная ситуация», поэтому по смыслу исключения здесь всё-таки не особо уместны. Кроме того, нужно учитывать, что при обработке исключений выполняется большое число машинных команд, что снижает эффективность программы.

Любителей «чистого» структурного программирования наверняка устроит такой вариант решения:
function Find(A: Matrix; X: integer): Boolean;
var i, j: integer;
begin
  Result := False;
  for i:=1 to N do
    for j:=1 to N do
      if A[i,j] = X then Result := True
end;
Но, к сожалению, по эффективности он не может составить конкуренцию предыдущим, так как в любом случае рассматриваются все N2 элементов массива, даже если элемент A[1,1] равен X.

[vlad]

Яркий пример на тему "ниасилил while (и линейный поиск)"

И чего? Лично я предпочту пройтись по этой матрице std::find. Но если уж слишком много для этого писать (писатель матрицы не позаботился об итераторах), то тогда в отдельную функцию с двумя return.

Цикл Дейкстры напишу только если настроение поглумиться

[ilovb]

Тут не нужен никакой цикл Дейкстры. Обычный лин.поиск. Просто инкремент нужно делать не в одном измерении, а в двух.

Код: [Выделить]

PROCEDURE Inc2d(VAR d1, d2: INTEGER);
BEGIN
   INC(d2);
   IF d2 = n THEN
      d2 := 0;
      INC(d1);
   END;
END Inc2d;


Код: [Выделить]

i := 0; j := 0;
WHILE (i < n) & (m[i, j] # x) DO
   Inc2d(i, j);
END;
IF i < n THEN
   // нашли
END;


[vlad]

Тут не нужен никакой цикл Дейкстры. Обычный лин.поиск. Просто инкремент нужно делать не в одном измерении, а в двух.

Не, VAR-параметры это моветон. Тем более для индексов.
ИМХО, у тебя, собственно, и получился завуалированный ЦД.

[ilovb]

Не, VAR-параметры это моветон. Тем более для индексов.

С каких это пор? 

INC() тоже моветон?

[ilovb]

ИМХО, у тебя, собственно, и получился завуалированный ЦД.

Думаю, что многие циклы "завуалированный ЦД" 
90 процентов чего угодно

[vlad]

Не, VAR-параметры это моветон. Тем более для индексов.

С каких это пор? 

С тех пор как я ознакомился с хаскелем Точно не помню, но примерно в то время пришло осознание, что результат должен возвращаться как результат, а не в виде изменяемых аргументов.
А до этого была просто неудовлетворенность существующим синтаксисом C++ (причем в ББ/обероне точно такая же проблема) - в точке вызова не видно, что аргументы передаются по ссылке и будут изменены.

INC() тоже моветон?

Да. ++ намного лучше В крайнем случае  i += 1

P.S. NEW - тоже дурной. Запись p := NEW смотрится намного естественнее.

P.S.S. Не говоря о том, что не сильно оптимизирующий компилятор породит ужасный код для инкремента индексов из твоего примера.

[vlad]

в точке вызова не видно, что аргументы передаются по ссылке и будут изменены.

В C# это фикснули, но для меня было уже поздно Для меня, теперь испорченного хаскелем, возврат результата как результата все равно лучше.

[ilovb]

Ну я пока функциональщиной не заболел.  Так что воспринимаю нормально. Помечать не мешало бы, да.
В любом случае Inc2d написана только для иллюстрации схемы цикла.

[valexey_u]

Многомерные массивы в языке - моветон :-) Не было бы их, и проблемы не было бы.

[ilovb]

Матрицы - это моветон. Не было бы их, и проблемы не было бы.

[ilovb]

Чтобы не казалось, что я только других умею дерьмом поливать.
Пожалста: https://code.google.com/p/1c-toolkit/source/browse/lua/cf_tools/cf_inside.lua#108

Прекрасно помню почему так сделал - было лень писать while 

[Geniepro]

Код: [Выделить]

i := 0; j := 0;
WHILE (i < n) & (m[i, j] # x) DO
   Inc2d(i, j);
END;
IF i < n THEN
   // нашли
END;

Не понимаю я такого паттерна:

Код: [Выделить]

i := 0;
while i < len(arr) and not p(arr[i]) do
  i := i + 1
end;
if i < len(arr) then
  -- нашли!
end;Всегда делаю так:

Код: [Выделить]

i := 0; found := false;
while i < len(arr) and not found do
  if p(arr[i]) then
    found := true
  else
    i := i + 1
end;
if found then
  -- нашли!
end;
или так (учитывая что на паскалях я вапще-то не работаю лет 10):

Код: [Выделить]

bool found = false;
for (int i = 0; i < arr.Length && !found; i++)
{
    if (p(arr[i])) found = true;
}
if (found)
{
    // нашли!
}

[ilovb]

Из той же оперы: http://ic.asf.ru/~/docs/cpp/cppd_ifstruct.htm

Хотя оператор goto как метод управления программой давно "впал в немилость", он порой оправдывает свое существование. Одним из таких особых случаев является выход из глубоко вложенной процедуры. Рассмотрим, например, следующий фрагмент программы.

int i, j, k;
int stop = 0;

for(i=0; i<100 && istop; i++) {
   for(j=0; j<10 && istop; j+ + ) {
      for(k=0; k<20; k++) {
         // ...
         if(something()) {
            stop = 1;
            break;
         }
      }
   }
}
Переменная stop используется для отмены двух внешних циклов при условии возникновения некоторого программного события. Однако все же лучше достичь того же эффекта с помощью оператора goto.

int i, j, k;

for(i=0; i<100; i++) {
   for(j=0; j<10; j + +) {
      for(k=0; k<20; k++) {
         // . ..
         if(something()) {
            goto done;
         }
      }
   }
}

done: // ...
Как видите, используя оператор goto, можно обойтись без дополнительных затрат ресурсов, которые связаны с повторением проверки значения переменной stop в предыдущем варианте.

[Kemet]

Не понимаю я такого паттерна:

вот здесь-то и пригодился бы цикл-паук