OberonCore

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

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




Начать новую тему Ответить на тему  [ Сообщений: 31 ]  На страницу Пред.  1, 2
Автор Сообщение
СообщениеДобавлено: Пятница, 20 Июль, 2012 12:59 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Илья Ермаков писал(а):
Ну да, это получается, по сути, оптимизированная запись ЦД (упаковка двух циклов в один с "щёлкающими" ветками остаётся).

Я имел ввиду исходный ЦД-код, не совсем пойму , а зачем тут говорить о двух циклах?
Цикл один - последовательно "двигаем" правую границу окна одинаковых элементов до конца и в нужных местах "подтягиваем" левую.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 13:48 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Я имею виду в сравнении с напрашивающимся интуитивно построением вложенного цикла....

Придумать Ваш цикл можно таким же образом мыслей, как ЦД. Только надёжнее начать таки с чистого ЦД...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 14:44 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 575
Откуда: Россия, Санкт-Петербург
Зачем тут вложенный цикл?
Зачем тут цикл Дейкстры?

Задачка элементарная однопроходная:
Код:
    was := pass[0];  count := 1;
    FOR i := 1 TO total - 1 DO
        IF was # pass[i] THEN  stat[was] := count;  was := pass[i];  count := 1;
        ELSE INC(count);
        END;
    END;


pass - массив с номерами паспортов (pass[Индекс] = номер паспорта),
stat - массив со статистикой (stat[НомерПаспорта] = сколько раз сдавал экзамен)


Последний раз редактировалось Madzi Пятница, 20 Июль, 2012 14:49, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 14:46 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Илья Ермаков писал(а):
Я имею виду в сравнении с напрашивающимся интуитивно построением вложенного цикла....

Придумать Ваш цикл можно таким же образом мыслей, как ЦД. Только надёжнее начать таки с чистого ЦД...

Моего здесь ничего нет - я перефразировал Ваш исходный цикл. А сам я привык несколько к другими способам реализации подобных задач.
Вот на МАМПСе как то так:
Код:
 ;пусть в неком массиве pasp[i] (i от 1 до len)  несортированные номера паспортов
 ;определим к-во вхождений каждого номера
 N cnt,i
 F i=1:1:len  S cnt(pasp(i))=$g(cnt(pasp(i)))+1
 ;подсчитаем статистику
 N p  S p=""
 F  S p=$o(cnt(p))  Q:p=""  S stat(cnt(p))=$g(stat(cnt(p)))+1
 

PS.
Ляп небрежности в коде исправлен. :)


Последний раз редактировалось albobin Пятница, 20 Июль, 2012 16:51, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 14:48 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Неплохое упражнение. Притом из реальной жизни.

Программиста -- пороть.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 14:56 
Модератор
Аватара пользователя

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


Это эквивалентно
viewtopic.php?p=73513#p73513 в другой системе переменных (не i, j, а i, count).
Т.е. это тоже оптимизированный ЦД.

Вернее строить неоптимизированный, а потом уже посмотреть, про что и разговор.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 15:53 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1053
Откуда: Россия, Чебоксары
Madzi писал(а):
stat - массив со статистикой (stat[НомерПаспорта] = сколько раз сдавал экзамен)
Уловие задачи другое :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 16:00 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 575
Откуда: Россия, Санкт-Петербург
Alexey_Donskoy писал(а):
Madzi писал(а):
stat - массив со статистикой (stat[НомерПаспорта] = сколько раз сдавал экзамен)
Уловие задачи другое :)

Не принципиально. Сути это не меняет. Однопроходная задача где ЦД - ненужное усложнение.
Код:
    was := pass[0];  count := 1;
    FOR i := 1 TO total - 1 DO
        IF was # pass[i] THEN  INC(stat[count]);  was := pass[i];  count := 1;
        ELSE INC(count);
        END;
    END;

поменялся всего 1 оператор.
stat[i] - число людей, сдававших i экзаменов.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 16:30 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Я, "распробовав" ЦД, теперь воспринимаю его как общую, наиболее регулярную форму цикла, с которой удобно работать при построении - и по которой потом можно выполнить любые целесообразные "свёртки".
С ЦД стоит начинать построение, если задача требует вложенных циклов или цикла с вложенным IF, где внутри IF идёт манипулирование переменными цикла.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 16:40 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 575
Откуда: Россия, Санкт-Петербург
Илья Ермаков писал(а):
Я, "распробовав" ЦД, теперь воспринимаю его как общую, наиболее регулярную форму цикла, с которой удобно работать при построении - и по которой потом можно выполнить любые целесообразные "свёртки".
С ЦД стоит начинать построение, если задача требует вложенных циклов или цикла с вложенным IF, где внутри IF идёт манипулирование переменными цикла.

Согласен. Однако в данном случае манипулирования переменными цикла (i) не происходит, так как стоит элементарная задача подсчёта числа вхождений элемента (плюс ещё и в отсортированном массиве). Я к тому что не нужно всегда искать чёрную кошку в тёмной комнате. Иногда её там не бывает.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 20 Июль, 2012 19:32 
Аватара пользователя

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


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

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


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

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


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

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