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

Литература

Мэйн, Джеймс (Маупе 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, с очевидным дополнением — указывается фамилия человека, на нужды которого истрачены деньги. Исходные данные необходимо проверить на непротиворечивость, обращая особое внимание на даты, размеры платежей, фамилии и статьи расходов.

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

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

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

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