OberonCore
https://forum.oberoncore.ru/

ЦД для подсчёта количества повторяющихся элементов
https://forum.oberoncore.ru/viewtopic.php?f=82&t=4027		 Страница 2 из 2
Автор:  albobin [ Пятница, 20 Июль, 2012 12:59 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов
Илья Ермаков писал(а):
Ну да, это получается, по сути, оптимизированная запись ЦД (упаковка двух циклов в один с "щёлкающими" ветками остаётся).

Я имел ввиду исходный ЦД-код, не совсем пойму , а зачем тут говорить о двух циклах?
Цикл один - последовательно "двигаем" правую границу окна одинаковых элементов до конца и в нужных местах "подтягиваем" левую.
Автор:  Илья Ермаков [ Пятница, 20 Июль, 2012 13:48 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов
Я имею виду в сравнении с напрашивающимся интуитивно построением вложенного цикла....

Придумать Ваш цикл можно таким же образом мыслей, как ЦД. Только надёжнее начать таки с чистого ЦД...
Автор:  Madzi [ Пятница, 20 Июль, 2012 14:44 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов
Зачем тут вложенный цикл?
Зачем тут цикл Дейкстры?

Задачка элементарная однопроходная:
Код:
    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[НомерПаспорта] = сколько раз сдавал экзамен)
Автор:  albobin [ Пятница, 20 Июль, 2012 14:46 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов
Илья Ермаков писал(а):
Я имею виду в сравнении с напрашивающимся интуитивно построением вложенного цикла....

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

Моего здесь ничего нет - я перефразировал Ваш исходный цикл. А сам я привык несколько к другими способам реализации подобных задач.
Вот на МАМПСе как то так:
Код:
 ;пусть в неком массиве 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.
Ляп небрежности в коде исправлен. :)
Автор:  Info21 [ Пятница, 20 Июль, 2012 14:48 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов
Неплохое упражнение. Притом из реальной жизни.

Программиста -- пороть.
Автор:  Илья Ермаков [ Пятница, 20 Июль, 2012 14:56 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов
Madzi писал(а):
Задачка элементарная однопроходная:


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

Вернее строить неоптимизированный, а потом уже посмотреть, про что и разговор.
Автор:  Alexey_Donskoy [ Пятница, 20 Июль, 2012 15:53 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов
Madzi писал(а):
stat - массив со статистикой (stat[НомерПаспорта] = сколько раз сдавал экзамен)
Уловие задачи другое :)
Автор:  Madzi [ Пятница, 20 Июль, 2012 16:00 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов
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 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов
Я, "распробовав" ЦД, теперь воспринимаю его как общую, наиболее регулярную форму цикла, с которой удобно работать при построении - и по которой потом можно выполнить любые целесообразные "свёртки".
С ЦД стоит начинать построение, если задача требует вложенных циклов или цикла с вложенным IF, где внутри IF идёт манипулирование переменными цикла.
Автор:  Madzi [ Пятница, 20 Июль, 2012 16:40 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов
Илья Ермаков писал(а):
Я, "распробовав" ЦД, теперь воспринимаю его как общую, наиболее регулярную форму цикла, с которой удобно работать при построении - и по которой потом можно выполнить любые целесообразные "свёртки".
С ЦД стоит начинать построение, если задача требует вложенных циклов или цикла с вложенным IF, где внутри IF идёт манипулирование переменными цикла.

Согласен. Однако в данном случае манипулирования переменными цикла (i) не происходит, так как стоит элементарная задача подсчёта числа вхождений элемента (плюс ещё и в отсортированном массиве). Я к тому что не нужно всегда искать чёрную кошку в тёмной комнате. Иногда её там не бывает.
Автор:  Info21 [ Пятница, 20 Июль, 2012 19:32 ]
Заголовок сообщения:  Re: ЦД для подсчёта количества повторяющихся элементов
Madzi писал(а):
не нужно всегда искать чёрную кошку в тёмной комнате. Иногда её там не бывает.
Но упражнение (как учебное упражнение) все равно полезное в силу полной обозримости.
Страница 2 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/