OberonCore
https://forum.oberoncore.ru/

Поиск элемента матрицы
https://forum.oberoncore.ru/viewtopic.php?f=82&t=2356
Страница 1 из 3

Автор:  Валерий Лаптев [ Понедельник, 15 Февраль, 2010 20:06 ]
Заголовок сообщения:  Поиск элемента матрицы

Отделено от viewtopic.php?f=82&t=2257

Вот тут рядом "чайник" задает вопрос: а какова базовая схема двукратного вложенного цикла поиска по двумерному массиву? С полным проходом по всем элементам матрицы - тут вопросов нет. А именно поиск по двумерному массиву первого удовлетворяющего заданному условию элемента вызывает затруднение с завершением цикла - внешнего.
Заводить булевскую переменную?
Сначала она = false. Если во внутреннем цикле нашли - она = true.
Более того, она, видимо в условии внешнего цикла должна стоять в качестве одного из операндов логического выражения. Тогда при обнаружении во внутреннем цикле происходит выход и из внешнего цикла.
Но просьба к Илье - запишите явным образом и этот паттерн. А то для новичков представляет некоторую сложность правильно записать. А выход по goto из внутреннего цикла - нефиг делать понять. Так и пишут .

Автор:  Александр Ильин [ Понедельник, 15 Февраль, 2010 21:04 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Мой вариант ответа. Ищем значение x в массиве arr размером N раз по M строк.
Код:
VAR
   arr: ARRAY N, M OF INTEGER;
   i, k: INTEGER;
   found: BOOLEAN;
BEGIN
   i := 0;
   found := FALSE;
   WHILE (i < N) & ~found DO
      k := 0;
      WHILE (k < M) & ~found DO
         found := arr [i, k] = x;
         IF ~found THEN
            INC (k)
         END
      END;
      IF ~found THEN
         INC (i)
      END
   END;
   POST: (i >= N) OR (k >= M) OR (arr [i, k] = x)
END
Это было с дополнительной переменной. Без переменной - ещё проще: используем подпрограмму.
Код:
TYPE
   Line = ARRAY M OF INTEGER;
VAR
   arr: ARRAY N OF Line;
   i: INTEGER;

   PROCEDURE FindInLine(IN line: Line; OUT pos: INTEGER): BOOLEAN;
   BEGIN
      pos := 0;
      WHILE (pos < M) & ~(line [pos] = x) DO
         INC (pos)
      END;
      RETURN pos < M (* если на выходе TRUE, pos = положению искомого *)
   END FindInLine;

BEGIN
   i := 0;
   WHILE (i < N) & ~FindInLine(arr [i], k) DO
      INC (i)
   END;
   POST: (i >= N) OR (k >= M) OR (arr [i, k] = x)
END
Во втором случае - два типичнейших линейных поиска, даже без дополнительных условий для инкрементов (IF ~found THEN INC...).

Автор:  Info21 [ Понедельник, 15 Февраль, 2010 21:05 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Там однократный while. Стандартный пример из Дейкстры.
i := 0; j := 0;
WHILE j < N DO
INC( i );
IF i = N THEN i := 0; INC( j ) END
END;

Валерий Лаптев писал(а):
Вот тут рядом "чайник" задает вопрос: а какова базовая схема двукратного вложенного цикла поиска по двумерному массиву?

Автор:  Димыч [ Понедельник, 15 Февраль, 2010 21:11 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Info21 писал(а):
Там однократный while. Стандартный пример из Дейкстры.
i := 0; j := 0;
WHILE j < N DO
INC( i );
IF i = M THEN i := 0; INC( j ) END
END;

Наверное так?

Автор:  Александр Ильин [ Понедельник, 15 Февраль, 2010 21:22 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Info21 писал(а):
Там однократный while. Стандартный пример из Дейкстры.
Если я правильно понял Info21, поиск значения = x в arr NxM будет выглядеть так:
Код:
VAR
   arr: ARRAY N, M OF INTEGER;
   i, k: INTEGER;
BEGIN
   i := 0;
   k := 0;
   WHILE (k < M) & ~(arr [i, k] = x) DO
      INC (i);
      IF i = N THEN
         i := 0;
         INC (k)
      END
   END;
   POST: (i >= N) OR (k >= M) OR (arr [i, k] = x)
END

Автор:  Александр Шостак [ Понедельник, 15 Февраль, 2010 22:22 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Цитата:
(k < M) & ~(arr [i, k] = x)

А почему принцип извращаться с неестественным отрицанием не применяем к первому условию? (не только в вашем примере):

Код:
~(k >= M) & ~(arr [i, k] = x)


Или вообще дико:

Код:
~((k >= M) OR (arr [i, k] = x))


Естественный и понятный вид:

Код:
(k < M) & (arr [i, k] # x)

Автор:  Валерий Лаптев [ Понедельник, 15 Февраль, 2010 22:51 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Info21 писал(а):
Там однократный while. Стандартный пример из Дейкстры.
i := 0; j := 0;
WHILE j < N DO
INC( i );
IF i = N THEN i := 0; INC( j ) END
END;

Проход по двумерному массива как одномерному - это "грязный хак"! :mrgreen: :mrgreen: :mrgreen:
Для начинающего... :)

Автор:  Илья Ермаков [ Понедельник, 15 Февраль, 2010 22:57 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Никакого хака нет. Структура пространства поиска такая. Линейный поиск на упорядоченной последовательности пар (i, j). Ничего двумерного в алгоритме. Просто параметр в цикле не скалярный, а парный.

Автор:  Сергей Губанов [ Вторник, 16 Февраль, 2010 00:25 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Berserker писал(а):
Цитата:
(k < M) & ~(arr [i, k] = x)

А почему принцип извращаться с неестественным отрицанием не применяем к первому условию?
В общем виде:

WHILE (есть где искать) & ~(условие поиска) DO искать END;
IF ~(есть где искать) THEN нашли ELSE не нашли END

отрицание вынесенное за скобку есть часть общего паттерна. Польза выноса отрицания за скобку становится очевидна когда условие поиска сложное.

Автор:  Сергей Губанов [ Вторник, 16 Февраль, 2010 00:38 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Валерий Лаптев писал(а):
Вот тут рядом "чайник" задает вопрос: а какова базовая схема двукратного вложенного цикла поиска по двумерному массиву?

Это пишется через цикл Дейкстры.

Давайте сразу для 4-х мерного :D

i0 := 0; i1 := 0; i2 := 0; i3 := 0;
WHILE (i3 < N3) & ~(m[i0, i1, i2, i3] = v) DO INC(i3)
ELSIF (i3 = N3) & (i2 < N2) DO INC(i2); i3 := 0
ELSIF (i2 = N2) & (i1 < N1) DO INC(i1); i2 := 0
ELSIF (i1 = N1) & (i0 < N0) DO INC(i0); i1 := 0
END;
IF i0 < N0 THEN нашли ELSE не нашли END;

Автор:  Сергей Губанов [ Вторник, 16 Февраль, 2010 00:45 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Александр Ильин писал(а):
WHILE (k < M) & ~(arr [i, k] = x) DO
INC (i);
IF i = N THEN
Этот алгоритм не эффективен:
1) Во "вложенном" цикле нужно идти по строкам, а не по столбцам.
2) Во время прохода по строке достаточно проверки только одного индекса, а здесь на каждом шаге проверяются оба индекса.

Автор:  Александр Ильин [ Вторник, 16 Февраль, 2010 01:20 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Сергей Губанов писал(а):
2) Во время прохода по строке достаточно проверки только одного индекса, а здесь на каждом шаге проверяются оба индекса.
Да, диагноз верный, и эмпирически проверено уже. Вопрос: я хоть правильно понял идею цикла, изложенную Info21? А то он какой-то полуфабрикат написал, даже без критерия окончания поиска (видимо, не хотел много времени тратить).

Автор:  Info21 [ Вторник, 16 Февраль, 2010 09:45 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Илья Ермаков писал(а):
Никакого хака нет. Структура пространства поиска такая. Линейный поиск на упорядоченной последовательности пар (i, j). Ничего двумерного в алгоритме. Просто параметр в цикле не скалярный, а парный.
Пространство поиска как раз двумерное.

А вот алгоритм -- *последовательный* перебор.

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

Не "не хотел", а спешил. Да и детский сад, что ли -- обход указан, и хватит.

Накладной расход на вызов процедуры (который в Обероне сравнительно дешев) есть O(N), а полная экономия от экономии на каждом шаге (упрощение индексных вычислений, которые за кадром) -- O(N^2).

Вариант с локальной процедурой вполне корректен: при усложнении задачи он вообще может остаться единственно возможным из корректных.
Аналогичный прием систематически использован в алгоритмах с возвратом в новой версии Алгоритмов -- там без него выявить структуру проблематично.

Но пример забавен тем, что приходится использовать функцию с побочным эффектом (даже если это OUT-параметр). Разумеется, такая функция должна быть локальной и обозримой, чтобы было четко видно, где побочный эффект -- если нужно, оберткой для какой-то "политически-корректной" менее локальной процедуры.

Автор:  Info21 [ Вторник, 16 Февраль, 2010 10:22 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Info21 писал(а):
Но пример забавен тем, что приходится использовать функцию с побочным эффектом (даже если это OUT-параметр). Разумеется, такая функция должна быть локальной и обозримой, чтобы было четко видно, где побочный эффект -- если нужно, оберткой для какой-то "политически-корректной" менее локальной процедуры.
И тут некая идея:

"Нечистые" функции, вообще говоря, нехороши, но в подобных ситуациях отчетливо полезны.
Напрашивается такая идея:
На глобальном уровне их запретить.
Но оставить на локальном именно для подобных ситуаций.

Интересно, кстати, как тут (скорее, в алгоритмах с возвратом) ФЯ ведут себя.

Автор:  Сергей Губанов [ Вторник, 16 Февраль, 2010 12:05 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Info21 писал(а):
"Нечистые" функции, вообще говоря, нехороши
Надо уметь их готовить :D

Автор:  Info21 [ Вторник, 16 Февраль, 2010 12:23 ]
Заголовок сообщения:  Re: Базовые паттерны циклов

Сергей Губанов писал(а):
Info21 писал(а):
"Нечистые" функции, вообще говоря, нехороши
Надо уметь их готовить :D
Ну, вроде, я показал где и как их готовить.
Вы еще знаете по-настоящему полезные способы, на уровне организации логики алгоритмов?
Поделитесь, пожалуйста.

Автор:  Madzi [ Вторник, 16 Февраль, 2010 12:26 ]
Заголовок сообщения:  Re: Поиск элемента матрицы

Друзья, попробуйте мой вариант
Код:
VAR
    arr: ARRAY N, M OF INTEGER;
    i: INTEGER;
BEGIN
    i := 0;
    WHILE (i < N*M) & ~(arr[i MOD N, i DIV N] = x) DO INC (i) END
END;

Автор:  А.П. [ Вторник, 16 Февраль, 2010 14:56 ]
Заголовок сообщения:  Re: Поиск элемента матрицы

Madzi писал(а):
Друзья, попробуйте мой вариант

Замечательный по краткости и изяществу вариант!
Для учебных целей очень хорош. Браво!!
Быстродействие не оценивал.

Автор:  Евгений Темиргалеев [ Вторник, 16 Февраль, 2010 15:08 ]
Заголовок сообщения:  Re: Поиск элемента матрицы

Вопросы оптимизации и быстродействия выделены: viewtopic.php?p=42871#p42871

Текущая тема:
Валерйи Лаптев писал(а):
какова базовая схема двукратного вложенного цикла поиска по двумерному массиву?

Автор:  Info21 [ Вторник, 16 Февраль, 2010 16:01 ]
Заголовок сообщения:  Re: Поиск элемента матрицы

А.П. писал(а):
Для учебных целей очень хорош.
Как пример того, за что руки отрывают.

Страница 1 из 3 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/