Указания исполнителю. В рассматриваемой задаче существует интересный побочный вопрос. Даты проведения банковских операций задаются в обычном виде: месяц/число/год. А для решения задачи требуется иметь отрезки времени Ti, прошедшие после операции, выраженные в годах. У банкиров и юристов имеется несколько способов определения момента времени, когда прекращается начисление процентов на деньги (подозревают, что метод расчета зависит от того, кто кому должен). В программе достаточно вычислять годы в виде вещественных чисел с учетом високосных лет, предполагая, что все даты лежат в диапазоне от 1900 до 1999 включительно. Вообще говоря, перевод дат из одного календаря в другой может оказаться отнюдь не простым делом.
Инструментовка. Годится любой процедурный язык, предусматривающий действия с вещественными числами.
Длительность исполнения. Одному исполнителю на одну неделю.
* Аникин А. В. Кредитная система современного капитализма. — М.: Наука, 1964.
Эту книгу можно рекомендовать читателю, желающему подробнее ознакомиться с деятельностью различных финансовых институтов капиталистических стран, особенно США.
11.
Меньше copy — меньше и вздору,
или Избыточность текста и сжатие файла
Все знают, что большинству людей свойственно излишнее многословие. Гораздо менее широко известно, что даже самые лаконичные высказывания можно было бы значительно сократить. Вообще, естественные языки отличаются чрезвычайной избыточностью. Даж есл нсклко бкв вбрсть, эт прдлжн ещ мжн прчть. Языки, используемые для вычислений, обладают той же особенностью. Для экономии памяти компьютера, объем которой ограничен, имеет смысл ликвидировать избыточность текста.
Существует несколько способов уплотнения текста. Самый очевидный из них — поиск различных по длине цепочек из одной повторяющейся литеры. Такая группа может быть заменена тройкой литер mcn, где m обозначает признак повторения, специальную литеру, не используемую нигде в тексте для других целей, с — сама повторяющаяся литера и n — длина цепочки. Один такой триграф[17] экономит n — 3 литер, причем значение n не может превышать максимального числа, представимого в поле одной литеры. Описанный способ обработки весьма неплохо оправдывает себя для текстов, содержащих длинные цепочки повторяющихся литер, например длинные цепочки пробелов, характерных для большинства программ. К сожалению, этот прием не столь хорош для других текстов, поскольку большинство данных не отличается такой же строгой формой записи, как программы.
Второй способ основан на том, что в различных системах кодировки литер, применяемых на ЭВМ, большинство литер практически не используется (из 256 литер обычного 8-разрядного кода, как правило, употребляется лишь около 100). Сначала в тексте отыскиваются наиболее распространенные диграфы, и каждому из них ставится в соответствие одна из не используемых в тексте одиночных литер. Уплотнение текста производится при просмотре его слева направо путем последовательной замены выявленных диграфов их однолитерными эквивалентами. При этом может быть достигнута значительная экономия, поскольку, например, 150 наиболее часто встречающихся диграфов уже составляют большу́ю долю текста на естественном языке. И если не ставить целью слишком высокую степень уплотнения текста, можно написать довольно эффективные программы кодирования и декодирования, работающие с машинным представлением литер.
Однако существуют все же определенные трудности. Кто сказал, что наиболее часто встречающиеся диграфы в английском тексте должны быть теми же, что и во французском, или в наборе файлов, содержащих почтовые адреса, или в тексте на Алголе? А если даже это и так, то как насчет триграфов, квадриграфов или более длинных групп? Ведь более длинные группы, даже если они и реже встречаются, дают большую экономию, а бывает, что определенный фрагмент появляется в большом куске текста намного чаще, чем можно было бы ожидать. И, возвращаясь назад, как подсчитать частоты появления диграфов?
17
В лингвистике диграф — комбинация из двух букв, обозначающая один звук; аналогично, триграф — из трех букв, квадриграф — из четырех и т. д. —