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 Во втором случае - два типичнейших линейных поиска, даже без дополнительных условий для инкрементов (IF ~found THEN INC...).
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 |
Автор: | 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; Проход по двумерному массива как одномерному - это "грязный хак"! Для начинающего... |
Автор: | Илья Ермаков [ Понедельник, 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-х мерного 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 писал(а): "Нечистые" функции, вообще говоря, нехороши Надо уметь их готовить
|
Автор: | Info21 [ Вторник, 16 Февраль, 2010 12:23 ] |
Заголовок сообщения: | Re: Базовые паттерны циклов |
Сергей Губанов писал(а): Info21 писал(а): "Нечистые" функции, вообще говоря, нехороши Надо уметь их готовить Вы еще знаете по-настоящему полезные способы, на уровне организации логики алгоритмов? Поделитесь, пожалуйста. |
Автор: | 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/ |