Этюды для программистов

укрупнение гнезд, в нашем алгоритме требуется, чтобы частоты встречаемости каждого из двух последовательных гнезд превысили один и тот же крайний предел.

Можно, однако, для каждого гнезда иметь свой порог. В другом варианте может быть у одного гнезда постоянный порог, а у другого — порог, являющийся функцией средней частоты гнезд. Аналогично может варьироваться начальная частота укрупненного гнезда, причем при любом способе начальная частота задается большой исходя из условия повышения шансов на сохранение данного гнезда при чистке.

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

В алгоритме кодирования употребляются диграфы, начинающиеся с не используемых во входном тексте литер. Однако, если набор диграфов кончился, а словарь еще не доделан, можно использовать триграфы и т. д. Коль скоро частоты гнезд словаря известны, их можно употребить для организации взвешенного кодирования переменной длины. Этот способ будет дороже при декодировании (почему не при кодировании?), зато обеспечит даже более высокую степень сжатия текста.

Литература

Мэйн, Джеймс (Маупе A., James Е. В.). Information Compression by Factorising Common Strings. Comput. J., 18, 2, pp. 157–160, 1975.

Этот этюд представляет собой в основном переформулировку работы Мэйна и Джеймса. Надо заметить, что наш алгоритм более прозрачен, а их работа содержит ряд существенных результатов.

Кнут (Knuth D. E.). The Art of Computer Programming, Volume 3/Sorting and Searching. Addison-Wesley, Reading, MA, 1973. [Имеется перевод: Кнут Д. Искусство программирования для ЭВМ, Т. 3. Сортировка и поиск. — M.i Мир, 1978.]

Хотя чтение любой части книги Кнута доставляет массу удовольствия, представляется, что обсуждаемому вопросу наиболее соответствует материал разд. 6.2 о дереве поиска.

12. В духе добрососедства, или Домашняя бухгалтерия

Кооперативы — довольно характерное явление в студенческой жизни. Иногда несколько студентов просто вместе платят за квартиру; порой они связаны друг с другом тесными и официальными общинными узами. Однако в любом случае им нужно вести и оплачивать счета. Немало общин распалось из-за денег, и, хотя более глубоких проблем ЭВМ решить не могут, честно вести расчеты они в состоянии.

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

Если расходы распределяются не поровну, расчет не сводится к простому делению. Обычно кто-нибудь не прочь платить побольше, но иметь еще одну комнату; тот, кто выходные проводит у родителей, платит за еду несколько меньше других и т. п. И разумеется, каждый может потратить деньги по своему усмотрению, например на междугородный телефонный разговор или пиво, что не будет фиксироваться в ежемесячном групповом расчете. Чтобы учесть отмеченные нами и подобные им обстоятельства, нужна устоявшаяся бухгалтерская система.

Тема. Напишите программу, обеспечивающую небольшую общину постатейно расписанными счетами. Исходные данные подразделяются на четыре части. Первая часть должна содержать фамилии тех, кто участвует в расходах в текущем месяце. Во второй части перечисляются основные статьи расходов, такие, как питание, квартплата, коммунальные услуги. За каждой статьей должен следовать список членов общины и их доли в общих расходах. Доля может выражаться как в долларах, так и в процентах. Если вся статья распределена явным образом, то остаток делится поровну между остальными членами. Например, если квартплата составляет 200 долл., студент А взялся платить 45 долл., а В — 35%, то на всех остальных членов общины приходятся равные доли от 85 долл.

Элементами третьей части исходных данных должны быть записи об общественно полезных расходах. Запись содержит дату, фамилию члена группы, уплаченную сумму, статью расхода и краткое описание. Четвертая часть содержит сходную информацию, но о расходах на личные нужды. Каждая запись в этой части имеет ту же структуру, что и в части 3, с очевидным дополнением — указывается фамилия человека, на нужды которого истрачены деньги. Исходные данные необходимо проверить на непротиворечивость, обращая особое внимание на даты, размеры платежей, фамилии и статьи расходов.

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

Заключительная часть вывода должна включать хронологический перечень всех расходов на общественные нужды и таблицу (люди/статьи), в которой приведены расходы, приходы, паи и сбалансированные долговые обязательства. Перекрестное суммирование таблицы позволит оценить точность бухгалтерии.

Указания исполнителю. Ничего особо сложного в предложенной задаче нет. Конечно, эффективная программа всегда лучше неэффективной, но в данном случае время счета мало по сравнению с временем ввода/вывода. Основного внимания требуют разнообразный формат исходных данных к элегантная организация проверки данных на непротиворечивость. А в общем это прозаическая программа, как и большинство производственных программ. Дайте «профессиональное» решение.

Инструментовка. Хотя Кобол — лучшее средство, можно использовать почти любой процедурный язык.

Длительность исполнения. Одному исполнителю на 2 недели.

Развитие темы. Существенная особенность коммерчески-ориентированных языков — точные вычисления и отредактированный вывод долларовых величин. При вычислениях с вещественными числами ошибки округления местами могут достигать нескольких центов; перекрестные проверки при этом дадут разные результаты. Уместно написать несложные подпрограммы для операций с числами с фиксированной точкой (но не с целыми числами!). Если вы напишите программу на Фортране, вам придется уяснить, как печатать эти надоедливые плавающие знаки доллара, «хвостовые> указатели кредита и левые нули. Если применяется Кобол или PL/I, таких трудностей не возникает.

13. Тур до Тьюрингу,