OberonCore

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

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

Мой вариант ответа. Ищем значение x в массиве arr размером N раз по M строк.
Это было с дополнительной переменной. Без переменной - ещё проще: используем подпрограмму.
Во втором случае - два типичнейших линейных поиска, даже без дополнительных условий для инкрементов (IF ~found THEN INC...).

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

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

Если я правильно понял Info21, поиск значения = x в arr NxM будет выглядеть так:

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



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



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

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

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

В общем виде:

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

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

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

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

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;

Этот алгоритм не эффективен:
1) Во "вложенном" цикле нужно идти по строкам, а не по столбцам.
2) Во время прохода по строке достаточно проверки только одного индекса, а здесь на каждом шаге проверяются оба индекса.

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

Пространство поиска как раз двумерное.

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

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

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

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

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

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

И тут некая идея:

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

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

Надо уметь их готовить

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

Друзья, попробуйте мой вариант

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

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

Текущая тема:

Как пример того, за что руки отрывают.