* C for Dummies * Aleph * 2000-07-23 * 004 *
-----[00]----------[Quote of Day]-----------------------------------------
The Laws of Computer Programming
1. Any given program, when running, is obsolete.
2. Any given program costs more and takes longer each time it is run.
3. If a program is useful, it will have to be changed.
4. If a program is useless, it will have to be documented.
5. Any given program will expand to fill all the available memory.
6. The value of a program is inversely proportional to the weight of
its output.
7. Program complexity grows until it exceeds the capability of the
programmer who must maintain it.
-----[01]----------[Hot News]---------------------------------------------
Tony Zhang. Teach Yourself C in 24 Hours. (Eng.)
Удачно построенный и хорошо написанный учебник по С для начинающих.
> Several years ago, my friend Joey Burton, who was then my supervisor
> at Kinley Corporation, asked me why many computer programming books
> were written in a way that set a deep learning curve and scared a lot
> of beginners away from learning programming languages. Joey, thank
> you for the question that became the motivation for me to write a
> computer book for beginners. Today I can proudly say that there is at
> least one book available for people who want to learn C, but have no
> previous programming experience.
http://members.xoom.com/c4dummies/files/c24.zip (698,249)
-----[02]----------[Blah-Blah-Blah]---------------------------------------
Теория Групп, которую некоторые экстремисты считают основой всей
современной математики и о которой мы чуть-чуть поговорим сегодня,
неразрывно связана с именем талантливого французского математика Эваристо
Галуа (Evariste Galois, 1811-1832) в 21 год погибшего на дуэли из-за
женщины. Одни исследователи склонны думать, что это была обычная любовная
интрига, другие - что дуэль была замаскированным политическим убийством.
Легенда утверждает, что основы Теории Групп Галуа написал в ночь перед
дуэлью.
На самом деле, его работа в этой области началась гораздо раньше и уже в
16-летнем возрасте он заложил основы теории, ныне известной, как "Теория
Галуа", к которой пришел изучая условия разрешимости в радикалах
алгебраических уравнений высших степеней (пятой и выше). Формулы для
корней алгебраических уравнений третьей и четвертой степени были к тому
времени уже известны.
Биография Эваристо Галуа и его вклад в развитие науки - одна из самых
захватывающих страниц в истории математики. К сожалению, на русском языке,
кажется, почти ничего невозможно о нем найти, поэтому я подготовил краткую
биографическую справку по CD Encyclopaedia Britannica (Copyright (c) 1996
Encyclopaedia Britannica, Inc.) При этом, к сожалению, мне пришлось
пожертвовать некоторыми французскими буквами, заменив их на сходные
английские.
Будучи студентом, Галуа опубликовал несколько небольших работ, но три его
записки, посланные во Французскую Академию (Academy of Sciences) были
потеряны или отвергнуты математиками, действовавшими как редакторы. Так,
первая была потеряна Коши (Augustin-Louis Cauchy) в 1829 году.
Галуа предпринял две попытки поступления в Политехнический институт (Ecole
Polytechnique) в 1827 и 1829 году - ведущую математическую школу Франции,
но оба раза проваливался на устном экзамене.
В 1829 году его отец, после нескольких горьких стычек с консервативными
элементами в его родном городе, кончает жизнь самоубийством.
Поняв, что его надежды на карьеру профессионального математика рухнули,
Галуа поступает как 'a teacher candidate' в менее престижную Нормальную
Школу (Ecole Normale Superieure) и начинает активно заниматься политикой,
не оставляя, однако, своих исследований. Но его вторая записка, об
алгебраических функциях, посланная во Французскую Академию в 1830 была
потеряна Фурье (Jean-Baptiste-Joseph Fourier).
Революция 1830 года отправила последнего монарха из Бурбонов - Чарльза X
(Charles X), в изгнание, но республиканцы были глубоко разочарованы, когда
другой король - Луи-Филипп (Louis-Philippe), унаследовал трон, хотя он был
гражданским королем, несшим трехцветный флаг Революции. Когда Галуа
написал статью, в сильных выражениях отражавших его взгляды, он был
предупрежден об исключении его из Ecole Normale Superieure. Впоследствии,
он дважды арестовывался за республиканскую активность. В первый раз Галуа
был освобожден, но провел шесть месяцев в тюрьме после второго ареста.
Его третья записка была отвергнута в 1831 Пуассоном (Simeon-Denis Poisson)
с замечанием, что она почти невразумительна и должна быть прояснена и
дополнена.
Обстоятельства, приведшие к смерти Галуа на дуэли в Париже, так и не были
полностью выяснены.
Существуют различные предположения, что это было результатом ссоры из-за
женщины, что он был вызван роялистами, ненавидевшими его республиканские
взгляды, или что это была провокация, организованная полицейским агентом.
А. Дюма (Alexandre Dumas) в его автобиографии Mes Memoirs (1863-1865)
выводит Pecheux d'Herbinville как человека, застрелившего Галуа.
Во всяком случае, предчувствуя свою гибель на предстоящей дуэли, Галуа с
лихорадочной поспешностью пишет последнее научное завещание, адресованное
его другу и бывшему соученику Шевалье (Auguste Chevalier).
По некоторым замечаниям, можно предположить, что Галуа начал развивать
теорию алгебраических функций. Эта работа была доведена до конца 40 лет
спустя немецким математиком Риманом (Bernhard Riemann).
Рукописи Галуа с предисловием Лиувилля (Joseph Liouville), были
опубликованы в 1846 в Journal de Mathematiques Pures et Appliquees. В 1870
французский математик Жордан (Camille Jordan) опубликовал полную обработку
(full-length treatment) теории Галуа - Traite des Substitutions.
Эти публикации сделали полностью доступными его открытия, воздали должное
и уверенно утвердили его место в истории математики. 13 июня 1909 года
была установлена мемориальная доска на родине Галуа - скромном местечке
Bourg-la-Reine и математик Jules Tannery посвятил ему яркую речь,
опубликованную в том же году в Bulletin des Sciences Mathematiques.
-----[03]----------[Topic]------------------------------------------------
Типы чисел. Операция деления. Понятие группы. Коды, обнаруживающие ошибки.
Погрешности округления.
-----[04]----------[Body]-------------------------------------------------
Типы чисел
----------
Итак, с точки зрения компьютера, есть два совершенно различных типа чисел:
одни (integer) могут быть представлены совершенно точно (в пределах
размеров разрядной сетки), другие (float, double) - только приближенно,
зато в гораздо большем диапазоне значений - от очень маленьких до очень
больших, за счет хранения масштабного множителя отдельно от дробной части
числа.
В зависимости от количества отводимых для хранения числа байт, в языке С
различаются следующие несколько типов чисел:
"Целый" тип, представляемый всегда точно:
char - символьный
short int - "короткий" целый
int - обыкновенный целый
long int - "длинный" целый
"Плавающий" тип, представляемый всегда приближенно:
float - "плавающий"
double - "плавающий" удвоенной точности
Очень важно понимать, что аксиомы арифметики неприменимы в операциях
с числами с плавающей точкой, так как результат содержит погрешность
округления и существенно зависит от порядка действий.
Если Вы хотите быть уверенны в ответе, то должны использовать целый тип и
контролировать, что размер операндов не выходит за пределы разрядной сетки
данного типа.
Для работы с "целым" и "плавающим" типом данных, компьютер использует
совершенно разные методы, но для простоты, символы математических операций
обозначаются привычным образом: '+', '-', '*' и '/'.
Таким образом, для сложения двух чисел целого типа можно написать:
<integer> + <integer>
и для сложения двух чисел с плавающей точкой также можно написать:
<float> + <float>
хотя в обоих случаях, компьютер будет интерпретировать знак 'оператор +'
совершенно по-разному.
Такое "двусмысленное" использование (определяемое контекстом) называется
"перегрузкой" (overloading) и совершенно аналогично использованию омонимов
в обычном языке.
Сравните, например, предложения:
В кармане был ключ
и
Под горой бил ключ
или
Косарь взмахнул косой
и
Девушка поправила косу
и
Рыбаки расположились на косе
Хотя слова "ключ" и "коса" имеют совершенно различный смысл во всех
предложениях, никаких затруднений это не вызывает, так этот смысл
однозначно определяется тем предложением, в котором использован омоним.
Точно также, встретив символ 'оператор +', компьютер по контексту выяснит
для себя, какое сложение - "целое" или "плавающее" и какой разрядности
(один, два, четыре или восемь байтов) использовать в данном случае.
Если же в одном выражении смешаны операнды разных типов, то перед
вычислением они приводятся к разрядности самого "длинного" из них.
Так если складываются числа целого типа размером в 1 байт и в 4 байта, то
перед выполнением сложения однобайтный операнд будет приведен к типу
второго операнда - то есть, к размеру в 4 байта.
Если складываются два числа с плавающей точкой типов float и double, то
есть размером 4 байта и 8 байт, то перед выполнением сложения, float будет
преобразовано в double, то есть к размеру в 8 байт.
Выражение "будет преобразовано" означает, на самом деле, что будет создана
временная переменная нужного типа (размера), в которую будет записано
значение приводимого операнда и эта временная переменная будет подставлена
в выражение вместо операнда "неправильного" размера.
И хотя все эти действия компьютер выполняет автоматически, лучше помнить о
необходимости таких преобразований и не смешивать в одном выражении
операнды разных типов.
Аналогичные действия выполняются и если в одном выражении смешаны (Очень
Плохо !) операнды целого типа и с плавающей точкой. Поскольку действия с
плавающей точкой не могут быть выполнены точно, то все операнды приводятся
к "наихудшему" типу - с плавающей точкой.
Все сказанное верно и в отношении других арифметических операций.
Действия с операндами целых типов, обычно, реализуются непосредственно
командами процессора, а действия над операндами с плавающей точкой требуют
использования математического сопроцессора или специальных подпрограмм,
эмулирующих его работу.
Таким образом, арифметика с плавающей точкой оказывается достаточно
"накладной" с вычислительной точки зрения и, когда это возможно,
желательно использовать вычисления с целыми числами.
Операция деления
----------------
Операция деления - самая сложная из всех арифметических операций, и она
остается такой же сложной и для компьютера. Хороший программист, перед тем
как написать, к примеру, x / 100.0, всегда подумает - а нельзя ли заменить
это на x * 0.01 ?
Очевидно, что для двух разных типов "целого" и "плавающего" деление должно
выполняться по-разному: целые числа могут точно делиться нацело или с
остатком, а плавающие - всегда приближенно.
Соответственно, в языке С есть три различных операции деления:
1. "Целое" деление '/'
Числитель делится на знаменатель, остаток (если он есть) отбрасывается.
Пример: 10 / 7 = 1
2. Деление по модулю '%'
Числитель делится на знаменатель и результат деления отбрасывается, а
сохраняется, наоборот, только остаток.
Пример: 10 % 7 = 3
3. "Плавающее" деление '/'
Числитель делится на знаменатель обычным образом, результат
записывается в виде дроби. Количество значащих цифр результата зависит
от разрядности операндов (float или double).
Пример: 10.0 / 7.0 = 1.42857142857142857143
Обратите внимание, что числа 10 и 7 я записал как 10.0 и 7.0 - это
сделано для того, чтобы компилятор мог правильно распознать тип
операндов (float) и использовать перегруженный оператор '/' для
операций с плавающей точкой. Кроме того, для наглядности, я привел
результат вычислений с двойной (double), а не с одинарной (float)
точностью.
При любых операциях, но, особенно, делении всегда существует опасность
выхода результата за разрядную сетку (переполнение). Причем, при делении
чисел с плавающей точкой, это относится к обоим компонентам - дробной
части и показателю. Типичный пример - деление на очень маленькое число или
на нуль.
Ситуации переполнения перехватываются операционной системой и, обычно,
вызывают аварийное завершение программы. Однако, программист может
установить свой собственный обработчик, например, деления на нуль и
выполнить свой собственный код. Такая техника часто используется при
построении защит от несанкционированного использования (например, проверки
правильности введенного регистрационного номера).
В Кнут т. 2 "Получисленные алгоритмы" гл. 4.2.1. можно найти краткую
историческую справку об арифметике с плавающей точкой (восходящей к
вычислителям др. Вавилона - ок. 1800 B.C.)
Не берусь утверждать, что современные компьютеры реализуют именно
"школьный" алгоритм деления "уголком", но, по крайней мере, у Кнута т. 2
"Получисленные алгоритмы" гл. 4.3. "Арифметика многократной точности", Вы
можете найти разбор именно такого алгоритма.
Понятие группы
--------------
Теперь, когда Вы уже столько знаете о числах и действиях над ними,
я хочу очень коротко коснуться Теории Групп - важного обобщения
обычных арифметических операций. Некоторые понятия и результаты
нам потребуются в дальнейшем.
Вначале, краткое неформальное определение.
Если в некоторой алгебраической структуре рассматривается только одна
операция, например, сложение (или умножение), причем, вычитание (деление)
всегда выполнимо, то можно говорить о группе.
Такими группами являются, например, множество целых чисел относительно
сложения или множество положительных чисел, относительно умножения.
Несколько раньше, не вводя этого названия, говоря о кодах Цезаря, мы
рассматривали группы перестановок.
С формальной (математической) точки зрения, группа определена, если
выполняются следующие четыре аксиомы:
Аксиоматическое определение группы
----------------------------------
Некоторое непустое множество G называется группой, если
1. В множестве G определена некоторая двухместная (бинарная) операция над
его элементами, которую мы назовем умножением. То есть, любым двум
элементам A и B из G поставлен в соответствие некоторый третий элемент
из G, который обозначается через AB и называется произведением
элементов A и B.
2. Умножение ассоциативно. То есть, для любых трех элементов A, B и C из G
(AB)C = A(BC)
3. В G существует единичный элемент, то есть такой элемент E, что для
любого A из G
EA = AE = A
4. Для любого элемента в группе существует обратный ему элемент, то есть
для любого элемента A найдется такой элемент A^-1, для которого
(A^-1)A = A(A^-1) = E (где E определен выше)
Таким образом, группа представляет собой пару из множества и заданной на
нем операции, которая обладает определенными свойствами.
В информатике особенно часто используются группы, обладающие важным
дополнительным свойством коммутативности умножения:
AB = BA
Такие группы называются абелевыми, по имени предшественника Галуа,
норвежского математика Абеля (Niels Henrik Abel, 1802-1829)
Рассмотрим в качестве примера, множество всех двоичных чисел длины N
(для определенности, можете считать, что N = 8, 16 или 32).
Если теперь применить к этим числам операцию сложения по mod 2 (XOR),
легко убедиться, что они образуют группу. То есть сложение по mod 2
выступает в качестве групповой операции (умножения). Иными словами,
абстрактное "умножение", о котором мы говорили при определении группы, в
данном конкретном случае является сложением по модулю два.
Также очевидно, что эта группа является абелевой (сложение по mod 2
коммутативно).
Вспомним таблицу истинности при сложении по модулю два:
+---+---+---+
|XOR| 0 | 1 |
+---+---+---+
| 0 | 0 | 1 |
+---+---+---+
| 1 | 1 | 0 |
+---+---+---+
Нулевая последовательность (00000000) является единичным элементом группы
EA = AE = A
или, используя синтаксис языка С и обозначая произвольное двоичное
число через X:
x^0 = 0^x = x
и каждое двоичное число X является обратным к самому себе при сложении по
mod 2:
x^x = 0
Особое значение понятия группы и операции по mod 2 имеют в теории кодов,
обнаруживающих и исправляющих ошибки. (Например, такой код используется в
популярном упаковщике RAR - авт. Евг. Рошаль, - если Вы выбрали
соответствующую опцию).
Рассмотрим простой пример (по кн. М.Н. Аршинов, Л.Е. Садовский "Коды и
математика").
Коды, обнаруживающие ошибки
---------------------------
Пусть имеется разрядная сетка длины 9 и рассмотрим множество всех
двоичных слов из 9 бит. Всего, таким образом можно представить
2^9 = 512
двоичных чисел или, в терминологии теории связи, сообщений.
Обозначая биты каждого слова через x1 - x9, расположим их в квадратной
таблице следующим образом:
+----+----+----+
| x1 | x2 | x3 |
+----+----+----+
| x4 | x5 | x6 |
+----+----+----+
| x7 | x8 | x9 |
+----+----+----+
Добавим к каждой строке и каждому столбцу этой таблицы еще по одному
проверочному символу, так, чтобы в каждой строке и каждом столбце было
четное число единиц (как Вы уже догадались, такие коды называются кодами с
проверкой на четность)
+----+----+----+----+
| x1 | x2 | x3 | s1 |
+----+----+----+----+
| x4 | x5 | x6 | s2 |
+----+----+----+----+
| x7 | x8 | x9 | s3 |
+----+----+----+----+
| s4 | s5 | s6 | s7 |
+----+----+----+----+
При этом, используя синтаксис С, мы можем записать очевидные соотношения
для строк и столбцов:
s1 = x1 ^ x2 ^ x3
s2 = x4 ^ x5 ^ x6
s3 = x7 ^ x8 ^ x9
s4 = x1 ^ x4 ^ x7
s5 = x2 ^ x5 ^ x8
s6 = x3 ^ x6 ^ x9
Кроме того, для проверочного символа s7, должны выполняться те же самые
условия, так что:
s7 = s1 ^ s2 ^ s3 = s4 ^ s5 ^ s6
Такой код позволяет исправить любую одиночную ошибку (изменение только
одного бита исходного сообщения) и обнаружить (но не исправить) любую
двойную ошибку (изменение сразу двух бит).
Предположим, что при передаче сообщения по зашумленной линии был искажен
бит x5 исходного сообщения.
Из приведенных выше соотношений очевидно, что при этом изменятся сразу два
проверочных символа s2 и s5, так как бит x5 входит в оба эти уравнения.
Таким образом, мы сразу получаем пару координат (строка, столбец)
однозначно определяющих измененный бит и можем скорректировать ошибку.
Сказанное верно для любой одиночной ошибки в произвольном бите.
К сожалению, если ошибка была двойной (изменены сразу два бита), то это
приводит к нарушению проверки на четность либо в двух строках, либо в двух
столбцах, либо сразу в двух строках и двух столбцах, что позволяет только
обнаружить ошибку, но не исправить ее.
Я не стану сейчас разбирать других примеров, но мы вернемся к этому в
подходящее время.
Дополнительно по этой теме рекомендую книжку с картинками:
Э. Фрид "Элементарное введение в абстрактную алгебру"
Имеющим математическую подготовку могу также порекомендовать
В.М. Муттер "Основы помехоустойчивой телепередачи информации"
Погрешности округления
----------------------
Обычно в книгах по программированию подразумевается, что компьютеры
считают с фантастической точность, а об ошибках округления говорится
вскользь и нехотя. Мне это представляется неправильным, так что прежде чем
перейти к каким бы то ни было программам и расчетам, хочу предостеречь Вас
от опасностей.
Особенно рекомендую книгу Р. Хэмминга (R.W. Hamming), руководителя
математической службы Bell Telephon Laboratories, "Численные методы для
научных работников и инженеров".
Дальнейшее изложение основано на книге Дж. Форсайт, М. Малькольм, К.
Моулер "Машинные методы математических вычислений".
Множество F чисел с плавающей точкой характеризуется 4 параметрами:
- основанием B
- точностью T
- минимальным показателем L
- максимальным показателем U
Число X с плавающей точкой из F представляется в виде произведения
дробной части и целого показателя:
x = +/- (d1/B + d2/B^2 + ... + dT/B^T ) * B^e
где целые числа d удовлетворяют неравенствам:
0 <= d <= B - 1
и
L <= e <= U
Сумма f = (d1/B + d2/B^2 + ... + dT/B^T ) - это дробная часть числа
(Вы узнали позиционную систему счисления ?)
а целое число e - показатель.
Если для каждого ненулевого числа X из множества F справедливо
d1 != 0 (старший член десятичной дроби ненулевой)
то такая плавающая система называется нормализованной.
Очевидно, что f * B ^ T является целым числом и может храниться по обычной
схеме хранения целых чисел, в зависимости от принятой точности
представления.
При этом величина B ^ (1 - T) является оценкой относительной точности
арифметики.
Если число T не является целым, то это означает, что B = 2 ^ K и для
двоичного представления дробной части числа отводится K * T бит.
Устаревшая, но все еще интересная таблица дает представление
о точности плавающей арифметики на различных компьютерах:
------------------------+-------+---------+--------+-------+----------------
Computer | B | T | L | U | B ^ (1 - T)
------------------------+-------+---------+--------+-------+----------------
Univac 1108 | 2 | 27 | -128 | 127 | 1.49 * 10 ^ -8
Honeywell 6000 | 2 | 27 | -128 | 127 | 1.49 * 10 ^ -8
PDP-11 | 2 | 24 | -128 | 127 | 1.19 * 10 ^ -7
Control Data 6600 | 2 | 48 | -976 | 1070 | 7.11 * 10 ^ -15
Cray-1 | 2 | 48 | -16384 | 8191 | 7.11 * 10 ^ -15
Illiac-IV | 2 | 48 | -16384 | 16383 | 7.11 * 10 ^ -15
Burroughs B5500 | 8 | 13 | -51 | 77 | 1.46 * 10 ^ -11
Hewlett Packard HP-45 | 10 | 10 | -98 | 100 | 1.00 * 10 ^ -9
Texas Instruments SR-5x | 10 | 12 | -98 | 100 | 1.00 * 10 ^ -11
IBM 360 & 370 | 16 | 6 | -64 | 63 | 9.54 * 10 ^ -7
IBM 360 & 370 | 16 | 14 | -64 | 63 | 2.22 * 10 ^ -16
Telefunken TR440 | 16 | 9 1/2 | -127 | 127 | 5.84 * 10 ^ -11
Maniac II | 65536 | 2 11/16 | -7 | 7 | 7.25 * 10 ^ -9
------------------------+-------+---------+--------+-------+----------------
Как мы уже говорили, на одной машине может использоваться несколько систем
чисел с плавающей точкой. Обычно, это системы с одинарной и удвоенной
точностью.
Операции плавающего сложения и умножения коммутативны, но не ассоциативны,
и для них не выполняется дистрибутивный закон. Таким образом, анализ
погрешностей весьма затруднен и часто ограничиваются только некоторой
оценкой для среднего или наихудшего случая.
По крайней мере, мы не станем этим заниматься и я только приведу пример.
Предположим, нам требуется написать программу, вычисляющую показательную
функцию e^x, где e = 2.71828182845904523536
Для любого действительного (и даже комплексного) x, y = exp(x) может
быть представлено как сумма сходящегося бесконечного ряда:
y = exp(x) = 1 + x + x^2/2! + x^3/3! + ...
Теперь предположим, что наша плавающая система имеет параметры
B = 10, T = 5 (Десятичная, 5 разрядов)
и x = -5.5
Тогда, для y = exp(-5.5) получаем:
1.0000
-5.5000
+15.125
-27.730
+38.129
-41.942
+38.446
-30.208
+20.768
-12.692
+6.9803
-3.4902
+1.5997
.
.
.
----------
+0.0026363 (Сумма первых 25 членов)
Суммирование ограничено 25 членами, потому что при выбранной разрядности
последующие члены уже не влияют на результат.
На самом деле, правильный ответ exp(-5.5) = 0.00408677, то есть наше
вычисление привело к ответу, не имеющему верных цифр.
Что же было неправильно ?
Некоторые члены, и следовательно промежуточные суммы, на несколько
порядков больше конечного ответа. При этом такие слагаемые, как 38.129 уже
содержат ошибку округления, почти равную по величине окончательному
результату. Кроме того, четыре старших, то есть наиболее значимых разряда
каждого их восьми членов, превышающих 10 по модулю, были потеряны. Эти
восемь членов следовало бы брать с 10 значащими цифрами, чтобы получить
шесть значащих цифр в ответе. Более того, потребовалась бы еще
одиннадцатая цифра, чтобы получить верную шестую цифру вычисляемой суммы.
Это явление называется катастрофической потерей верных знаков.
Хотя иногда возможно удерживать в вычислениях большее число значащих цифр
с целью избежать катастрофической потери знаков, это всегда обходится
дорого в смысле требований к памяти и времени исполнения.
Для рассматриваемой задачи есть лучший способ: вычислить сумму для
y = exp(5.5)
а затем взять обратное число. В нашей пятизначной десятичной арифметике:
exp(-5.5) = 1/exp(-5.5) = 1/(1 + 5.5 + 15.125 + ...) = 0.0040865
При таком способе вычисления ошибка снижается до 0.007%
Важно, однако, что для некоторых задач "хорошие" ответы нельзя получить
никаким изменением алгоритма, потому что задача чувствительна к малым
ошибкам, допущенным при представлении данных и в арифметике.
-----[05]----------[Homework]---------------------------------------------
Вопросы не обязательно основаны на материалах выпуска и, как это обычно и
бывает в жизни, могут потребовать от Вас самостоятельного исследования.
1. Подарки к Новому Году. (по кн. Кордемский Б.А. "Математическая
смекалка")
Местный комитет профессионального союза нашей организации решил
устроить новогоднюю елку для детей. Приготавливая подарки, мы быстро
разложили по пакетам конфеты и печенье. Но когда дело дошло до
мандаринов, наткнулись на забавное затруднение: сначала хотели
разложить все мандарины по 10 штук в пакет - не получилось: на один из
пакетов оставалось 9 мандаринов; если бы положили по 9 мандаринов,
осталось бы по 8 мандаринов на один из пакетов; попробовали
раскладывать по 8 мандаринов, осталось 7; стали раскладывать по 7,
осталось 6; положили по 6, осталось 5. - Что за история ? Неужели и
дальше так будет продолжаться ? Взяли бумагу, карандаш и начали
рассчитывать. И что бы Вы думали: делим число имеющихся у нас
мандаринов на 5, остается 4; делим на 4, остается 3; делим на 3,
остается 2; делим на 2, остается 1. Вот такое удивительное число
мандаринов мы имели.
А сколько же все-таки ?
2. Является ли перекодировка Win1251 -> KOI8-R групповой операцией на
множестве букв русского алфавита (без учета буквы E:) ? Образуют ли все
возможные варианты последовательных перекодировок группу ?
-----[06]----------[Glossary]---------------------------------------------
B.C. (abbr.) Before Christ
-----[07]----------[Info]-------------------------------------------------
Вопросы и замечания принимаются по адресу: aleph@canada.com
Предыдущие выпуски доступны со страницы архива:
http://www.subscribe.ru/archive/comp.prog.c4dummies/
или (в упакованном виде):
http://members.xoom.com/c4dummies/archive/000.zip
. . .
http://members.xoom.com/c4dummies/archive/003.zip
-----[--]----------[The End]----------------------------------------------
© Gazlan 2009 * gazlan@yandex.ru
|