OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 19 Март, 2024 07:50

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 44 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Поиск элемента матрицы
СообщениеДобавлено: Понедельник, 15 Февраль, 2010 20:06 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Отделено от viewtopic.php?f=82&t=2257

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Понедельник, 15 Февраль, 2010 21:04 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск
Мой вариант ответа. Ищем значение 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...).


Последний раз редактировалось Александр Ильин Понедельник, 15 Февраль, 2010 21:10, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Понедельник, 15 Февраль, 2010 21:05 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Там однократный while. Стандартный пример из Дейкстры.
i := 0; j := 0;
WHILE j < N DO
INC( i );
IF i = N THEN i := 0; INC( j ) END
END;

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


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

Зарегистрирован: Среда, 29 Март, 2006 12:09
Сообщения: 495
Info21 писал(а):
Там однократный while. Стандартный пример из Дейкстры.
i := 0; j := 0;
WHILE j < N DO
INC( i );
IF i = M THEN i := 0; INC( j ) END
END;

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Понедельник, 15 Февраль, 2010 21:22 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск
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


Последний раз редактировалось Александр Ильин Вторник, 16 Февраль, 2010 00:44, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Понедельник, 15 Февраль, 2010 22:22 

Зарегистрирован: Четверг, 23 Апрель, 2009 18:01
Сообщения: 219
Цитата:
(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)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Понедельник, 15 Февраль, 2010 22:51 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
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:
Для начинающего... :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Понедельник, 15 Февраль, 2010 22:57 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Никакого хака нет. Структура пространства поиска такая. Линейный поиск на упорядоченной последовательности пар (i, j). Ничего двумерного в алгоритме. Просто параметр в цикле не скалярный, а парный.


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Berserker писал(а):
Цитата:
(k < M) & ~(arr [i, k] = x)

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

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

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


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Валерий Лаптев писал(а):
Вот тут рядом "чайник" задает вопрос: а какова базовая схема двукратного вложенного цикла поиска по двумерному массиву?

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

Давайте сразу для 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;


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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Вторник, 16 Февраль, 2010 01:20 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Вторник, 16 Февраль, 2010 09:45 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Илья Ермаков писал(а):
Никакого хака нет. Структура пространства поиска такая. Линейный поиск на упорядоченной последовательности пар (i, j). Ничего двумерного в алгоритме. Просто параметр в цикле не скалярный, а парный.
Пространство поиска как раз двумерное.

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

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

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Вторник, 16 Февраль, 2010 10:22 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Info21 писал(а):
Но пример забавен тем, что приходится использовать функцию с побочным эффектом (даже если это OUT-параметр). Разумеется, такая функция должна быть локальной и обозримой, чтобы было четко видно, где побочный эффект -- если нужно, оберткой для какой-то "политически-корректной" менее локальной процедуры.
И тут некая идея:

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

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


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Info21 писал(а):
"Нечистые" функции, вообще говоря, нехороши
Надо уметь их готовить :D


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Базовые паттерны циклов
СообщениеДобавлено: Вторник, 16 Февраль, 2010 12:23 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Вторник, 16 Февраль, 2010 12:26 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 575
Откуда: Россия, Санкт-Петербург
Друзья, попробуйте мой вариант
Код:
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;


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Вторник, 16 Февраль, 2010 14:56 

Зарегистрирован: Пятница, 02 Декабрь, 2005 14:35
Сообщения: 210
Откуда: Россия, Томск
Madzi писал(а):
Друзья, попробуйте мой вариант

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Вторник, 16 Февраль, 2010 15:08 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Вопросы оптимизации и быстродействия выделены: viewtopic.php?p=42871#p42871

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Поиск элемента матрицы
СообщениеДобавлено: Вторник, 16 Февраль, 2010 16:01 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
А.П. писал(а):
Для учебных целей очень хорош.
Как пример того, за что руки отрывают.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 44 ]  На страницу 1, 2, 3  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB