16 статей
В велокроссе участвуют `130` спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объём сообщения, записанного устройством, после того как промежуточный финиш прошли `75` велосипедистов?
Первым делом нужно определить, сколько бит необходимо для кодирования `130` номеров спортсменов. Поскольку номера записываются в некотором устройстве, количество бит для кодирования каждого номера обязательно должно быть целым: `H=log_2 130`. После округления результата в большую сторону получим число `8`. Следовательно, для кодирования `1` номера необходим `1` байт. Таким образом, информационный объём сообщения, записанного устройством, составляет `75` байт.
В некоторой стране автомобильный номер состоит из `7` символов. В качестве символов используют `18` различных букв и десятичные цифры в любом порядке.
Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов, при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.
Определите объём памяти, отводимый этой программой для записи `60` номеров.
Первое действие аналогично предыдущей задаче – нужно установить, каким количеством бит кодируется `1` символ. Всего используется `18` букв и `10` десятичных цифр, то есть `28` символов. По формуле Хартли `H=log_2 28`. После округления получается `5` бит на `1` символ. Вторым действием нужно узнать, какой объём памяти занимает `1` номер. Поскольку номер состоит из `7` символов, а каждый символ кодируется `5` битами, нам потребуется `35` бит памяти для хранения `1` номера. Однако по условию каждый номер должен записываться целым количеством байтов, а в каждом байте `8` бит. Ближайшее сверху к `35` число, делящееся на `8` – это число `40`, следовательно, на каждый номер отводится `5` байт. Таким образом, для записи `60` номеров программе потребуется `60*5 = 300` байт памяти.
Сигналы с судна на берег передают, используя различное положение рук. Каждая рука может быть поднята вверх, отведена в сторону или опущена вниз. Сколько различных сигналов можно подать двумя руками, если важно то, какая рука была в каком положении, но обе руки могут находиться и в одинаковом положении?
Главная ловушка этой задачи заключается в следующем неверном ходе мыслей: «Раз одной рукой передаётся `3` сигнала, значит, двумя в `2` раза больше, то есть `6`». На самом деле число исходов с добавлением новой руки увеличивается в `3` раза, поскольку можно продублировать все положения первой руки для каждого из `3` возможных положений второй. Таким образом, в ответе получается `9` сигналов.
В течение `5` секунд было передано сообщение, объём ко-торого составил `375` байт. Каков размер алфавита, с помощью кото-рого записано сообщение, если скорость его передачи составила `200` символов в секунду?
Первым делом найдём скорость передачи этого сообщения: `375//5 = 75` байт в секунду. Далее, нам известно, что в секунду передавалось `200` символов, которые занимают `75` байт памяти. Поэтому следующим действием найдём объём памяти, отводимый под `1` символ, переведя ответ в биты (ибо уже из входных чисел очевидно, что под каждый символ отводится менее `1` байта): `75^(**)8//200 = 600//200 = 3`. Таким образом, под каждый символ отводится `3` бита.
Применяя формулу Хартли, находим, что алфавит состоит из `8` символов.
Информация является одним из фундаментальных понятий современной науки наряду с такими понятиями, как «вещество» и «энергия».
Общее определение этому термину дать невозможно. Однако в раз-личных предметных областях даётся специализированное определение информации, подходящее для данной предметной области. В рамках этого задания мы будем говорить о математической теории информации и рассмотрим два подхода - содержательный (Клод Шеннон) и алфавитный (А.Н.Колмогоров). Начнём с определения понятия «инфор-мация» в каждом из этих подходов.
В содержательном подходе, информация - это снятая неопределённость. Неопределённость некоторого события - это количество возможных результатов (исходов) данного события.
Например, если мы подбрасываем вверх монету, то она может упасть двумя различными способами (орлом вверх или решкой вверх). Соответственно, у данного события два возможных исхода. Если же подбрасывать игральный кубик, то исходов будет шесть.
В алфавитном подходе информация - это сообщение (последовательность символов некоторого алфавита). Причём существенными являются только размер алфавита и количество символов в сообщении. Конкретное содержание сообщения интереса не представляет. Чаще всего алфавит является двоичным (состоит из `2` символов – «`0`» и «`1`»).
После таких определений понятия «информация» можно говорить об её измерении. Введём несколько основных единиц измерения информации.
Чаще всего в качестве основной единицы измерения информации используется бит. При алфавитном подходе один бит - это количество информации, которое можно передать в сообщении, состоящем из одного двоичного знака (`«0»` или `«1»`). С точки же зрения содержательного подхода один бит - это количество информации, уменьшающее неопределённость знания в два раза.
Наряду с битами можно использовать и другие единицы измерения информации, например, триты или диты. При алфавитном подходе один трит - это количество информации, которое можно передать в сообщении, состоящем из одного троичного знака `(«0»`, `«1»` или `«2»)`. С точки же зрения содержательного подхода один трит - это количество информации, уменьшающее неопределённость знания в три раза. Соответственно, один дит - это количество информации, уменьшаю-щее неопределённость знания в десять раз, и количество информации, которое можно передать в сообщении, состоящем из одного десятичного знака (арабской цифры). В некоторых задачах (например, в задаче взлома кодового замка) удобнее в качестве основной единицы измерения информации использовать не биты, а диты, поскольку угадывание каждой цифры из кода уменьшает количество комбинаций в `10` раз.
Для каждой основной единицы измерения информации существуют производные более крупные единицы измерения. Поскольку чаще всего мы будем использовать в качестве основной единицы бит, рассмотрим производные единицы измерения для бита. На практике чаще всего используется не бит, а байт.
`1` байт (`1`B) `= 8` бит;
Далее существует две линейки производных единиц для байта – линейка десятичных приставок и линейка двоичных приставок. В случае десятичных приставок каждая следующая единица измерения равна `1000` предыдущих единиц. Обозначаются десятичные приставки латинскими буквами (буква префикса из системы СИ и заглавная «B», обозначающая «байт») Итак:
`1` килобайт (`1` kB) `= 1000` B (1000 байт);
`1` мегабайт (`1` MB) `= 1000` kB ;
`1` гигабайт (`1` GB) `= 1000` MB;
`1` терабайт (`1` TB) `= 1000` GB;
`1` петабайт (`1` PB) `= 1000` TB;
`1` эксабайт (`1` EB) `= 1000` PB;
`1` зеттабайт (`1` ZB) `= 1000` EB;
`1` йоттабайт(`1` YB) `= 1000` ZB.
Более крупных единиц на настоящий момент не введено.
При использовании двоичных приставок, каждая следующая едини-ца измерения равна 1024 предыдущих единиц. В России принято обозначать двоичные приставки, записывая префикс заглавной русской буквой и после него слово «байт» целиком и тоже русскими буквами. За рубежом для обозначения двоичных приставок между префиксом и «B» добавляется маленькая буква «i» (от слова «binary»). Кроме того, все префиксы записываются заглавными буквами. Итак:
`1` кибибайт (`1` Кбайт, `1` KiB) `=2^10` байт `= 1024` байт;
`1` мебибайт (`1` Мбайт, `1` MiB) `=2^20` байт `= 1024` Кбайт;
1 гибибайт (`1` Гбайт, `1` GiB) `=2^30` байт `= 1024` Мбайт;
1 тебибайт (`1` Тбайт, `1` TiB) `=2^40` байт `= 1024` Гбайт;
1 пебибайт (`1` Пбайт, `1` PiB) `=2^50` байт `= 1024` Тбайт;
1 эксбибайт (`1` Эбайт, `1`EiB) `=2^60` байт `= 1024` Пбайт;
1 зебибайт (`1` Збайт, `1` ZiB) `=2^70` байт `= 1024` Эбайт;
1 йобибайт (`1` Йбайт, `1` YiB) `=2^80` байт `= 1024` Збайт.
Как уже упоминалось выше, в качестве основной единицы измерения информации мы будем использовать бит. Соответственно, с точки зрения алфавитного подхода мы будем кодировать информацию при помощи нулей и единиц (двоичных знаков).
Для того чтобы измерить количество информации в сообщении, надо закодировать сообщение в виде последовательности нулей и единиц наиболее рациональным способом, позволяющим получить самую короткую последовательность. Длина полученной последовательности нулей и единиц и является мерой количества информации в битах.
Поставим себе одну из наиболее часто встречающихся задач в теории информации. Пусть у нас есть `N` возможных равновероятных вариантов исходов некоторого события. Какое количество информации нам нужно получить, чтобы оставить только один вариант?
Например, пусть мы знаем, что некоторая интересная для нас книга находится на одной из полок нашего книжного шкафа, в котором `8` полок. Какое количество информации нам нужно получить, чтобы однозначно узнать полку, на которой находится книга?
Решим эту задачу с точки зрения содержательного и алфавитного подходов. Поскольку изначально в шкафу было `8` полок, а в итоге мы выберем одну, следовательно, неопределённость знания о местоположении книги уменьшится в `8` раз. Мы говорили, что один бит – это количество информации, уменьшающее неопределённость знания в `2` раза. Следовательно, мы должны получить `3` бита информации.
Теперь попробуем использовать алфавитный подход. Закодируем номера всех полок при помощи `0` и `1`. Получим следующие номера: `000, 001, 010, 011, 100, 101, 110, 111`. Для того чтобы узнать, на какой полке находится книга, мы должны узнать номер этой полки. Каждый номер состоит из `3` двоичных знаков. А по определению, `1` бит (в алфавитном подходе) – это количество информации в сообщении, состоящем из `1` двоичного знака. То есть мы тоже получим `3` бита информации.
Прежде чем продолжить рассмотрение поставленной общей задачи введём важное математическое определение.
Назовём логарифмом числа `N` по основанию `a` такое число `X`, что Обозначение:
`X=log_aN`.
На параметры логарифма налагаются некоторые ограничения. Число `N` обязательно должно быть строго больше `0`. Число `a` (основание логарифма) должно быть также строго больше нуля и при этом не равняться единице (ибо при возведении единицы в любую степень получается единица).
Теперь вернёмся к нашей задаче. Итак, какое же количество информации нам нужно получить, чтобы выбрать один исход из `N` равновероятных? Ответ на этот вопрос даёт формула Хартли: `H=log_aN`, где `N` – это количество исходов, а `H` – количество информации, которое нужно получить для однозначного выбора `1` исхода. Основание логарифма обозначает единицу измерения количества информации. То есть если мы будем измерять количество информации в битах, то логарифм нужно брать по основанию `2`, а если основной единицей измерения станет трит, то, соответственно, логарифм берётся по основанию `3`.
Рассмотрим несколько примеров применения формулы Хартли.
В библиотеке `16` стеллажей, в каждом стеллаже `8` полок. Какое количество информации несёт сообщение о том, что нужная книга находится на четвёртой полке?
Решим эту задачу с точки зрения содержательного подхода. В переданном нам сообщении указан только номер полки, но не указан номер стеллажа. Таким образом, устранилась неопределённость, связанная с полкой, а стеллаж, на котором находится книга, мы всё ещё не знаем. Так как известно, что в каждом стеллаже по `8` полок, следовательно, неопределённость уменьшилась в `8` раз. Следовательно, количество информации можно вычислить по формуле Хартли `H=log_2 8=3` бита информации.
Имеется `27` монет, одна из которых фальшивая и легче всех остальных. Сколько потребуется взвешиваний на двухчашечных весах, чтобы однозначно найти фальшивую монету?
В этой задаче неудобно использовать бит в качестве основной единицы измерения информации. Двухчашечные весы могут принимать три положения: левая чаша перевесила, значит, фальшивая монета находится в правой; правая чаша перевесила, значит, монета находится в левой; или же весы оказались в равновесии, что означает отсутствие фальшивой монеты на весах. Таким образом, одно взвешивание может уменьшить неопределённость в три раза, следовательно, будем использовать в качестве основной единицы измерения количес-тва информации трит.
По формуле Хартли `H = log _3 27 = 3` трита. Таким образом, мы видим, что для того чтобы найти фальшивую монету среди остальных, нам потребуется три взвешивания.
Логарифмы обладают очень важным свойством: `log_a(X*Y)=log_aX+log_aY`.
Если переформулировать это свойство в терминах количества информации, то мы получим закон аддитивности информации: Коли-чество информации`H(x_1, x_2)`, необходимое для установления пары `(x_1, x_2)`, равно сумме количеств информации `H(x_1)` и `H(x_2)`, необходимых для независимого установления элементов `x_1` и `x_2`:
`H(x_1,x_2)=H(x_1)+H(x_2)`.
Проиллюстрируем этот закон на примере. Пусть у нас есть игральная кость в форме октаэдра (с `8` гранями) и монета. И мы одновременно подбрасываем их вверх. Нужно узнать, какое количество информации несёт сообщение о верхней стороне монеты после падения (орёл или решка) и числе, выпавшему на игральной кости.
Игральная кость может упасть `8` различными способами, следовательно, по формуле Хартли можно вычислить, что, определив число, выпавшее на игральной кости, мы получаем `3` бита информации. Соответственно, монета может упасть только `2` способами и несёт в себе `1` бит информации. По закону аддитивности информации мы можем сложить полученные результаты и узнать, что интересующее нас сообщение несёт `4` бита информации.
Рассмотрим другой способ решения этой задачи. Если мы сразу рассмотрим все возможные исходы падения `2` предметов, то их будет `16` (кость выпадает `8` способами, а монета - орлом вверх, и кость выпадает `8` способами, а монета - решкой вверх). По формуле Хартли находим, что интересующее нас сообщение несёт `4` бита информации.
Если в результате вычислений по формуле Хартли получилось нецелое число, а в задаче требуется указать целое число бит, то результат следует округлить в большую сторону.
Всякий текст состоит из символов - букв, цифр, знаков препинания и т. д., - которые человек различает по начертанию. Однако для компьютерного представления текстовой информации такой метод неудобен, а для компьютерной обработки текстов - и вовсе неприемлем. Используется другой способ: все символы кодируются числами, и текст представляется в виде набора чисел - кодов символов, его составляющих. При выводе текста на экран монитора или принтер необходимо восстановить изображения всех символов, составляющих данный текст. Для этого используются кодовые таблицы символов, в которых для каждого символа устанавливается соответствие между его кодом и изображением. Все кодовые таблицы, используемые в любых компьютерах и любых операционных системах, подчиняются международным стандартам кодирования символов.
Основой для компьютерных стандартов кодирования символов послужил ASCII (American Standard Code for Information Interchange) - американский стандартный код для обмена информацией, разработанный в 1960-х годах и применяемый в США для любых видов передачи информации. В нём используется `7`-битное кодирование: общее количество символов составляет `2^7=128`, из них первые `32` символа - «управляющие», а остальные - «изображаемые», т. е. имеющие графическое изображение. Управляющие символы должны восприниматься устройством вывода текста как команды, например:
|
Cимвол |
Действие |
Английское название |
|
№7 |
Подача стандартного звукового сигнала |
Beep |
|
№8 |
Затереть предыдущий символ |
Back Space (BS) |
|
№13 |
Перевод строки |
Line Feed (LF) |
|
№26 |
Конец текстового файла |
End Of File (EOF) |
|
№27 |
Отмена предыдущего ввода |
Escape (ESC) |
К изображаемым символам в ASCII относятся буквы английского (латинского) алфавита (заглавные и прописные), цифры, знаки препинания и арифметических операций, скобки и некоторые специальные символы. Фрагмент кодировки ASCII приведён в таблице.
|
Символ |
Десятичный код |
Двоичный код |
Символ |
Десятичный код |
Двоичный код |
|
Пробел |
`32` |
`00100000` |
`0` |
`48` |
`00110000` |
|
`!` |
`33` |
`00100001` |
`1` |
`49` |
`00110001` |
|
# |
`35` |
`00100011` |
`2` |
`50` |
`00110010` |
|
$ |
`36` |
`00100100` |
`3` |
`51` |
`00110011` |
|
`**` |
`42` |
`00101010` |
`4` |
`52` |
`00110100` |
|
`+` |
`43` |
00101011 |
5 |
53 |
`00110101` |
|
, |
`44` |
`00101100` |
`6` |
`54` |
`00110110` |
|
`–` |
`45` |
`00101101` |
`7` |
`55` |
`00110111` |
|
. |
`46` |
`00101110` |
`8` |
`56` |
`00111000` |
|
/ |
`47` |
`00101111` |
`9` |
`57` |
`00111001` |
|
`A` |
`65` |
`01000001` |
`N` |
`78` |
`01001110` |
|
`B` |
`66` |
`01000010` |
`O` |
`79` |
`01001111` |
|
`C` |
`67` |
`01000011` |
`P` |
`80` |
`01010000` |
|
`D` |
`68` |
`01000100` |
`Q` |
`81` |
`01010001` |
|
`E` |
`69` |
`01000101` |
`R` |
`82` |
`01010010` |
|
`F` |
`70` |
`01000110` |
`S` |
`83` |
`01010011` |
|
`G` |
`71` |
`01000111` |
`T` |
`84` |
`01010100` |
|
`H` |
`72` |
`01001000` |
`U` |
`85` |
`01010101` |
|
`I` |
`73` |
`01001001` |
`V` |
`86` |
`01010110` |
|
`J` |
`74` |
`01001010` |
`W` |
`87` |
`01010111` |
|
`K` |
`75` |
`01001011` |
`X` |
`88` |
`01011000` |
|
`L` |
`76` |
`01001100` |
`Y` |
`89` |
`01011001` |
|
`M` |
`77` |
`01001101` |
`Z` |
`90` |
`01011010` |
Хотя в ASCII символы кодируются `7`-ю битами, в памяти компьютера под каждый символ отводится ровно `1` байт (`8` бит). И получается, что один бит из каждого байта не используется.
Главный недостаток стандарта ASCII заключается в том, что он рассчитан на передачу только текста, состоящего из английских букв. Со временем возникла необходимость кодирования и неанглийских букв. Во многих странах для этого стали разрабатывать расширения ASCII-кодировки, в которых применялись однобайтные коды символов; при этом первые `128` символов кодовой таблицы совпадали с кодировкой ASCII, а остальные (со `128`-го по `255`-й) использовались для кодирования букв национального алфавита, символов национальной валюты и т. п. Из-за несогласованности этих разработок для многих языков было создано по нескольку вариантов кодовых таблиц (например, для русского языка их около десятка).
Впоследствии использование кодовых таблиц было несколько упорядочено: каждой кодовой таблице было присвоено особое название и номер. Указав кодовую таблицу, автоматически выбирают и язык, которым можно пользоваться в дополнение к английскому; точнее, выбирается то, как будут интерпретироваться символы с кодами более `127`.
Для русского языка наиболее распространёнными являются однобайтовые кодовые таблицы СР-`866`, Windows-`1251`, ISO `8859-5` и КОИ-`8`. В них первые `128` символов совпадают с ASCII-кодировкой, а русские буквы помещены во второй части таблицы (с номерами `128-255`), однако коды русских букв в этих кодировках различны! Сравните, например, кодировки КОИ-`8` (Код Обмена Информацией `8`-битный, международное название «koi-`8`r») и Windows-`1251`, фрагменты которых приведены в таблицах на странице `13`.
Несовпадение кодовых таблиц приводит к ряду неприятных эффектов: один и тот же текст (неанглийский) имеет различное компьютерное представление в разных кодировках, соответственно, текст, набранный в одной кодировке, будет нечитабельным в другой!
Однобайтовые кодировки обладают одним серьёзным ограничением: количество различных кодов символов в отдельно взятой кодировке недостаточно велико, чтобы можно было пользоваться одновременно несколькими языками. Для устранения этого ограничения в 1993-м году был разработан новый стандарт кодирования символов, получивший название Unicode, который, по замыслу его разработчиков, позволил бы использовать в текстах любые символы всех языков мира.
В Unicode на кодирование символов отводится `32` бита. Первые `128` символов (коды `0-127`) совпадают с таблицей ASCII, все основные алфавиты современных языков полностью умещаются в первые `65536` кодов (`65536=2^16`), а в целом стандарт Unicode описывает все алфавиты современных и мёртвых языков; для языков, имеющих несколько алфавитов или вариантов написания (например, японский и индийский), закодированы все варианты; внесены все математические и иные научные символьные обозначения, и даже - некоторые придуманные языки (например, письменности эльфов и Мордора из эпических произведений Дж.Р.Р. Толкиена). Потенциальная информационная ёмкость Unicode столь велика, что сейчас используется менее одной тысячной части возможных кодов символов!
В современных компьютерах и операционных системах используется укороченная, `16`-битная версия Unicode, в которую входят все современные алфавиты; эта часть Unicode называется базовой многоязыковой страницей (Base Multilingual Plane, BMP).
|
`I=8000*16*128=1384000` бит `I=8000*16*128//8=2048000` байт `I=8000*16*128//8//1024=2000` Кбайт `I=8000*16*128//8//1024//1024~~1,95` Мбайт |
`1` мин `= 60` сек `~~64` сек `= 2^6` сек
`1000~~1024=2^(10)`
Итак, объём музыкального файла вычисляется по формуле
`I=f*r*k*t`,
где `f` – частота дискретизации, `r` – разрешение (глубина кодирования), `k` – количество каналов, `t` – время звучания.
Теперь применим полученные знания о представлении текстовой информации на практике. В языке программирования Паскаль для работы с текстовой информацией есть специальный символьный тип переменных, который называется char (от английского character). Переменные этого типа занимают в оперативной памяти по `1` байту и, соответственно, могут принимать `256` различных значений. Значениями переменных этого типа являются элементы какой-либо однобайтовой кодовой таблицы (например, KOI-`8` или Windows-`1251`). Какие именно символы являются значениями данного типа, зависит от того, какая кодовая таблица используется в момент выполнения (а не написания) программы. То есть одна и та же программа, например, печатающая изображение всех символов кодовой таблицы, на компьютерах с различными текущими кодировками будет иметь различные результаты работы.
Переменным символьного типа можно присваивать значения при помощи оператора присваивания. При этом есть два способа записи символьных констант. Первый способ – записать явное изображение символа, заключив его в апострофы. Пусть, например, переменная C имеет тип char. Присвоим ей значение: C:= 'a'; Описанный способ записи символьных значений удобно применять практически всегда. Единственный недостаток этого способа заключается в том, что так невозможно представить служебные символы, которые не имеют явных изображений (в кодовой таблице это первые `32` символа). Поэтому существует ещё один способ записи символьных констант – сначала указать спецсимвол решётку (#), а потом код интересующего нас символа. Например, C:=#13; Недостаток этого способа заключается в том, что нужно помнить коды всех символов, поэтому обычно его применяют только для записи символов без явного изображения.
Переменные типа char можно выводить на экран при помощи оператора вывода и вводить с клавиатуры. Апострофы при вводе набирать не нужно (каждый апостроф также будет считаться отдельным символом). Служебные символы вводятся следующим образом: нужно зажать alt и на правой цифровой клавиатуре набрать код символа (например, 13).
К переменным типа char можно применять операции сравнения (> , < , >= , <= , = , <>). При этом сравниваются коды символов и большим признаётся символ, имеющий больший код (то есть символ, находящийся дальше от нулевого). Результатом операции сравнения является логическое значение – true или false.
Существует `5` стандартных функций для работы с переменными символьного типа:
|
Функция |
Действие |
Тип аргумента |
Тип результата |
|
Ord(c) |
Выдаёт код символа |
Char |
Integer |
|
Chr(x) |
Выдаёт символ по коду |
Integer |
Char |
|
Succ(c) |
Выдаёт следующий символ кодовой таблицы. Не определена для последнего символа |
Char |
Char |
|
Pred(c) |
Выдаёт предыдущий символ кодовой таблицы. Не определена для нулевого символа |
Char |
Char |
|
Upcase(c) |
Если аргумент является строчной латинской буквой, превращает его в соответствующую заглавную. Иначе ничего не делает |
Char |
Char |
Тип char является порядковым, то есть для каждого символа можно назвать его порядковый номер в типе, а также следующий и предшествующий элементы типа. Например, символ '1' имеет код `49`, следующий символ – это '2', а предыдущий – '0'. Благодаря этому свойству переменные типа char могут использоваться в качестве счётчиков в цикле for. Например, распечатать все заглавные латинские буквы можно следующим образом:
For c:= 'A' to 'Z' do write (c);
где переменная c имеет тип char.
Если в цикле for используется слово to, то на каждом шаге цикла счётчик будет принимать следующее значение в типе, в случае же downto – предыдущее значение в типе.
Рассмотрим несколько примеров задач на символьные переменные.
Вывести на экран все символы кодовой таблицы.
Эту задачу можно решать двумя способами: перебрать все символы или все их коды – разница только в типе счётчика цикла.
Способ 1:
var c:char;
begin
for c:=#0 to #255 do
write(ord(c),'-',c,' ');
readln
end.
Способ 2:
var i:integer;
begin
for i:=0 to 255 do
write(i, '-',chr(i), ' ');
readln
end.
Дана последовательность символов, заканчивающаяся точкой. Подсчитайте сумму цифр, входящих в эту последовательность.
Эта задача демонстрирует очень важную вещь – как превратить символ-цифру в целое число. Это осуществляется следующим образом: необходимо вычислить код интересующего нас символа (например, код единицы `49`) и вычесть из него код символа «ноль». В любой кодировочной таблице символы-цифры идут подряд, поэтому, выполнив указанные действия, мы гарантированно получим числовое значение символа-цифры. Приведём полный текст решения.
var c: char; s: integer;
begin
s :=0;
read (c);
while c <> '.' do
begin
if (c >= '0')and(c <= '9')
then s:= s+ord(c)–ord('0');
read (c);
end;
writeln ('s=',s);
readln
end.
Дана непустая последовательность слов, состоящих из заглавных и строчных латинских букв в любом порядке. Между соседними словами запятая, за последним словом – точка. Никакие другие символы в последовательность не входят. Определить количество слов, которые начинаются на букву `Z`.
Это ещё один классический тип задач на обработку последовательностей символов. При её решении у нас возникнет конструкция из вложенных циклов: внутренний цикл анализирует слово, а внешний перебирает слова. Приведём полный текст решения.
var c:char; s:integer;
begin
s:=0;
repeat
read(c);
if c='Z' then s:=s+1;
repeat
read(c)
until (c=',')or(c='.')
until c='.';
writeln('s=',s);
readln
end.
Данный оператор представляет собой естественное расширение условного оператора. В общем виде он записывается следующим образом:
case <выражение порядкового типа> of
константа_1: оператор_1;
константа_2: оператор_2;
...
Константа_n: оператор_n;
else оператор
end
Слова: case, of, else, end - являются ключевыми словами языка. Выражение, стоящее между словами case и of, называется селектором и должно иметь порядковый тип. Тип является порядковым, если можно для каждого значения назвать порядковый номер в типе, предыдущее и следующее значение в типе (кроме первого и последнего значения в типе). Из известных нам стандартных типов порядковыми являются типы integer, longint, boolean и char. Тип real порядковым не является.
Работает оператор выбора следующим образом. Сначала вычисляется значение селектора, затем оно сравнивается с константами. В случае совпадения селектора с какой-нибудь константой выполняется оператор, стоящий после этой константы, далее управление переходит на следующий за case оператор программы. Если селектор не совпал ни с одной из констант, то выполняется оператор после слова else. Очевидно, что селектор и константы должны иметь одинаковые типы. Иначе невозможно будет провести операции сравнения.
Если нужно для многих различных значений селектора выполнить один и тот же набор команд, то можно не записывать множество строк с одинаковой правой частью, а перечислить константы через запятую, затем поставить двоеточие и один раз написать нужную последовательность команд. Если константы идут подряд, можно также записать их в виде диапазона: константа_1..константа_2. В этом случае команда будет выполняться при совпадении селектора с любой константой из диапазона. Граничные значения считаются включёнными в диапазон. Можно также указать несколько диапазонов через запятую.
Оператор выбора предполагает однозначный выбор варианта. То есть нельзя одной и той же константой пометить два различных варианта. Все константы должны быть различны. Особенно аккуратно следует обращаться с диапазонами. Широко распространённая ошибка – указывать одну и ту же константу в качестве начальной границы одного диапазона и конечной – другого. Однако поскольку границы входят в диапазон, получается, что это значение будет входить в два разных диапазона.
Последнее замечание заключается в том, что в отличие от оператора if перед else необходимо ставить точку с запятой. И кстати, аналогично оператору if, если в ветке else должен стоять пустой оператор, её можно не записывать. Приведём примеры нескольких различных операторов варианта.
case c of
'+': x := x + y;
'-': x := x - y;
'*': x := x * y;
else writeln('error')
end;
case c of
'a'..'z','A'..'Z': writeln('letter');
'0'..'9': writeln('digit')
end;
Ввести значения $$ x$$ и $$ n$$. Вычислить сумму ряда $$ 1+x+{x}^{2}+{x}^{3}+\dots +{x}^{n}$$.
Сумма вычисляется накопительным путём: сначала вычисляется каждое слагаемое, а потом оно добавляется в сумму. Каждое слагаемое также вычисляется накопительным путём.
var x,n,i,s,a:integer;
begin
write('введите значения x и n');
readln(x,n);
S:=1; a:=1
for i:=1 to n do
begin
a:=a*x; s:=s+a
end;
writeln(s);
readln
end.
Заметим, что эту задачу можно решить, воспользовавшись формулой суммы первых `n` членов геометрической прогрессии, но наша цель не решить конкретную задачу, а понять принцип накапливания (суммы). Ибо далеко не любая последовательность чисел является геометрической или арифметической прогрессией.
Вводится последовательность натуральных чисел. Признак конца ввода – число `0`. Вывести среднее арифметическое чисел из последовательности (`0` не учитывается).
Эта задача относится к очень важному классу задач – обработка последовательностей с признаком конца и заранее неизвестным количеством элементов. В таких задачах нужно пользоваться операторами while и repeat. Причём, если оговаривается, что последовательность непустая, можно использовать repeat, а если этого не оговаривается, как в данной задаче, то нужно обязательно пользоваться циклом while, так как цикл repeat всегда выполняется, по крайней мере, один раз. Приведём полный текст решения. Переменная `s` подсчитывает сумму элементов последовательности, а переменная `k` – их количество.
var a,s,k:integer;
begin
s:=0; k:=0;
writeln('Введите последовательность натуральных чисел. Ноль – признак конца');
read(a);
while a<>0 do
begin s:=s+a; k:=k+1; read(a) end;
Writeln('среднее арифметическое=',s/k:0:4)
end.
Обратите внимание, что для ввода данных используется оператор read. Это позволяет набивать элементы в строчку через пробел. Если же использовать readln, то набивать значения придётся в столбик, что неудобно. Ещё одно важное замечание в этой задаче – оператор ввода внутри цикла должен быть последним, чтобы сразу попадать на проверку признака конца. Эти замечания относятся ко ВСЕМ задачам на обработку последовательностей с признаком конца.
Ввести целое число `n`. Вывести YES, если оно простое, и NO, если оно составное.
Эта задача демонстрирует сразу две важные вещи. Во-первых, как проверять делимость целых чисел, а во-вторых, технику флажков. Флажком называется переменная, которая имеет некоторое начальное значение и меняет его, если происходит определённое событие. Как правило, флажок имеет тип boolean.
В нашей задаче мы будем перебирать числа от `2` до квадратного корня из `n` и проверять, делится ли `n` на каждое из них. Изначально предположим, что `n` – простое, и присвоим флажку значение true, но если `n` поделится на какое-нибудь число, это будет значить, что оно составное, и, соответственно, флажок «упадёт» на значение false. Проверять на делимость нужно, сравнивая остаток от деления с нулём.
var n,i:integer;
f:boolean;
begin
Write('Введите значение n ');
Readln(n);
f:=true;
for i:=2 to round(sqrt(n)) do
if n mod i = 0 then f:=false else;
if f=true
then writeln('YES')
else writeln('NO');
Readln
end.
Зачастую в задаче нужно повторять одни и те же действия много раз. Повтор некоторого фрагмента программы несколько раз называется циклом. Рассмотрим следующий пример.
Вывести на экран квадраты чисел от `1` до `100`.
Очевидно, что для решения этой задачи нам придётся `100` раз выполнять команду вывода соответствующего числа на экран. Писать `100` операторов вывода как-то не хочется (слишком трудоёмко), поэтому будем знакомиться с операторами цикла. В языке Pascal существует три оператора цикла: for, while, repeat. Начнём с цикла for. Этот оператор цикла реализует следующую идею: «Повторять некоторую последовательность команд `N` раз, где `N` известно до начала повторения». Познакомимся с синтаксисом этого оператора.
for имя переменной := начальное значение to конечное значение do оператор
В этой конструкции переменная, стоящая после слова for, называется параметром или счётчиком цикла, а оператор, стоящий после слова do, называется телом цикла. Начальное и конечное значения, по сути, являются константами или выражениями одного типа со счётчиком.
Алгоритм выполнения цикла for следующий:
1) вычисляются начальное и конечное значения;
2) счётчику цикла присваивается начальное значение;
3) значение счётчика сравнивается с конечным. Если оно больше конечного, то выполнение цикла завершается и начинает выполняться следующий оператор программы, в противном случае переход к пункту 4;
4) выполняется тело цикла;
5) значение счётчика увеличивается на `1`;
6) переход к пункту 3.
В качестве примера рассмотрим решение задачи, поставленной выше. В качестве счётчика будем использовать переменную `i`.
var i:integer;
begin
for i:=1 to 100 do write(i*i,' ');
Readln
end.
Согласитесь, что решение фактически в одну строчку выглядит гораздо приятнее, чем в `100` строк (если не пользоваться оператором цикла).
Необходимо сделать несколько замечаний по поводу цикла for.
1) Типы счётчика начального и конечного значений должны совпадать, при этом в настоящий момент из известных нам типов можно использовать только integer и boolean. Вещественный тип использовать нельзя.
2) Начальное и конечное значения вычисляются один раз до начала цикла (и после не перевычисляются). Рассмотрим пример.
i:=1; for i:=i to i do writeln('HI');
Этот оператор цикла выполнится всего один раз, а не бесконечно много.
3) В теле цикла значение счётчика изменять нельзя. Так прописано в стандарте языка Pascal, и это требование поддерживается в системах семейства Delphi. Однако в системах семейства Borland Pascal значение счётчика изменять можно, что может приводить к непредсказуемым последствиям (поэтому будем считать, что независимо от системы значение счётчика изменять нельзя).
4) После завершения цикла значение счётчика не определено, то есть нельзя считать, что оно равно конечному значению или больше на единицу и пользоваться этим в дальнейшем алгоритме.
5) Тело цикла по грамматике должно состоять только из `1` оператора. Если же там по алгоритму должно быть несколько, нужно использовать составной оператор.
6) Можно слово to заменить на слово downto. В этом случае значение счётчика после каждого выполнения тела цикла будет уменьшаться на `1`, а выход из цикла произойдёт, когда значение счётчика окажется меньше, чем конечное.
Перейдём к знакомству с другими операторами цикла: while и repeat. Эти операторы реализуют следующие идеи: «Повторять некоторую последовательность команд пока выполняется некоторое условие» (цикл while) и «Повторять некоторую последовательность команд до тех пор, пока не выполнится некоторое условие» (цикл repeat). Познакомимся с синтаксисом оператора цикла while.
while условие do оператор.
После слова while должно быть логическое выражение (называемое условием), которое может принимать значение true или false. Оператор, стоящий после do, аналогично оператору for является телом цикла. Выполняется цикл while так:
1) вычисляется значение условия, если получилось true, то переход к пункту 2, иначе выход из цикла и переход на следующий оператор программы;
2) выполняется тело цикла;
3) переход к пункту 1.
Фактически оператор while является многократным применением оператора if с пустой веткой else. Аналогично оператору for, тело цикла должно состоять из `1` оператора. Однако в отличие от цикла for возможна ситуация, когда цикл будет выполняться бесконечное количество раз (зациклится). Например, while 2*2=4 do... . Что написать после do, совершенно не важно, важно, что оно будет выполняться, пока 2*2=4, а это всегда так и никогда не изменится. Значит, чтобы избегать зацикливания, параметры условия должны быть переменными, например while x*x=4 do ... . Хотя это тоже не гарантирует отсутствие зацикливания.
Осталось познакомиться с последним оператором цикла. Рассмотрим его синтаксис.
repeat
Оператор 1;
Оператор 2;
... .
Оператор N
until условие
Все операторы, написанные между repeat и until, являются телом цикла. Это выгодно отличает оператор repeat от других циклов – составной оператор здесь не требуется, а операторными скобками можно считать слова repeat и until. Работает этот оператор по следующему алгоритму:
1) выполняется тело цикла;
2) вычисляется значение условия. Если получилось true, то выход из цикла и переход к следующему оператору программы, в противном случае переход к пункту 1.
Отличительная особенность оператора цикла repeat заключается в том, что тело всегда выполняется, по крайней мере, один раз. Это нужно учитывать в задачах при выборе оператора цикла. Аналогично оператору while, цикл repeat может зациклиться, правда в случае, когда условие никогда не принимает значение true, например,
repeat...until 2*2=5.
В рассматриваемых ранее задачах процесс вычисления был линейным, то есть программа не должна была выполнять разные действия в зависимости от того, какие данные ей ввели. Теперь вспомним задачи с ветвящимся алгоритмом.
Ввести номер года. Вывести слово YES, если год високосный, и NO, если он – не високосный.
По условию очевидно, что в зависимости от входных данных программа должна будет выполнить один из двух операторов вывода: Writeln('YES') или Writeln('NO'). При этом написать в программе нам придётся оба, а вот выполняться должен будет только один из них. Для того чтобы реализовывать подобные ветвления алгоритма, в языке Pascal существует условный оператор. В общем виде он выглядит следующим образом:
if логическое выражение
then оператор
else оператор
В этой конструкции слова if, then и else являются служебными зарезервированными словами языка. Работает эта конструкция так: сначала вычисляется логическое выражение, стоящее после if. Если получилось значение true, то выполняется оператор, стоящий после слова then, а если получилось значение false, то выполняется оператор, стоящий после слова else.
Обратите внимание, что внутри условного оператора нет никаких точек с запятой, поскольку он является единой конструкцией, а точка с запятой – это разделитель между операторами. Для удобства чтения программ принято условие записывать на одной строке, а ветви then и else начинать с новой строки, однако это не является синтаксическим правилом языка.
В качестве примера условного оператора рассмотрим решение задачи, поставленной выше. Год считается високосным, если он делится нацело на `400`, или если он делится нацело на `4`, но не делится нацело на `100`. Приведём полный текст решения:
var y:integer;
begin
write('Введите номер года ');
readln(y);
if (y mod 400 = 0)or(y mod 4 = 0)and(y mod 100 <> 0)
then writeln('YES')
else writeln('NO');
end.
По грамматике языка после слов then и else должен стоять только один оператор языка. То есть запись if x>0 then x:=4; y:=0 else z:=9; является синтаксически неверной. А как быть, если всё-таки нужно выполнить более одного оператора? Для таких случаев в языке Pascal предусмотрен составной оператор, который позволяет превратить группу операторов в один. Выглядит он следующим образом: сначала записывается ключевое слово begin, далее – интересующая нас последовательность операторов через точку с запятой, а в конце пишется ключевое слово end. В отличие от конца программы, точка после этого слова не ставится. Слова begin и end называются операторными скобками. Запишем правильную версию условного оператора, приведённого выше: if x>0 then begin x:=4; y:=0 end else z:=9;
Обратите внимание на следующий тонкий момент: если требуется выполнить более одного оператора в ветке then, и при этом мы забудем написать операторные скобки, то это является синтаксической ошибкой, и программа просто не будет работать. Если же забыть написать операторные скобки в ветке else, то программа работать будет, но не так, как предполагалось. Рассмотрим пример: if x>0 then y:=9 else z:=8; c:=5;
В этом примере условный оператор заканчивается после z:=8; в то время как оператор c:=5; является следующим оператором программы и выполняется независимо от результата сравнения `x` с нулём. Если же написать операторные скобки, то присваивание в `c` числа `5` произойдёт только в случае x<=0.
Последнее замечание заключается в том, что в ветке else в качестве оператора может стоять и пустой оператор.
Рассмотрим следующий пример.
Вводятся `3` целых числа – `a`,`b`,`c`. Требуется в переменную `a` записать минимальное из этих чисел, в `b` – среднее и в `c` – максимальное.
Алгоритм решения этой задачи такой: сначала сравним значения переменных `a` и `b`, если значение `a` – больше, поменяем их местами. После этого сравним значения переменных `a` и `c`, и если значение `a` – больше, поменяем их местами. После этих двух сравнений в переменной `a` гарантированно окажется наименьшее из трёх чисел. Осталось сравнить переменные `b` и `c`, и в случае, когда в переменной `b` находится большее значение, поменять их местами.
Очевидно, что в этом алгоритме у нас три сравнения, следовательно, три последовательных условных оператора. При этом в каждом из них какие-то действия (поменять местами значения двух переменных) нужно выполнять только в ветке then, в ветке else (например, если в первом сравнении в переменной a находится уже более маленькое число, чем в переменной `b`) никаких действий выполнять не нужно. Но мы всё равно будем её записывать, чтобы избегать путаницы. Приведём полный текст решения, используя для обмена значений двух переменных дополнительную переменную `x`.
var a,b,c,x:integer;
begin
writeln('введите три целых числа ');
readln(a,b,c);
if a>b then begin x:=a; a:=b; b:=x end else;
if a>c then begin x:=a; a:=c; c:=x end else;
if b>c then begin x:=b; b:=c; c:=x end else;
writeln(a,b,c); readln
end.
В языке Pascal кроме уже изученных нами числовых типов ещё есть логический, который называется Boolean. Переменные этого типа занимают `1` байт оперативной памяти и могут принимать всего два значения – true и false (истина и ложь). Логическим переменным можно присваивать значения точно так же, как и числовым. Так же можно выводить их значения на экран, а вот вводить их с клавиатуры нельзя!
В языке Pascal определены `6` операций сравнения, результатом которых является логическое значение. Это операции: «больше» (>), «больше или равно» (>=), «меньше» (<), «меньше или равно» (<=), «равно» (=), и «не равно» (<>). Например, операция 5 > 2 выдаст значение true, а операция x<>3 выдаст значение true, если переменная `X` имеет любое значение, кроме `3`. Сравнивать можно не только числа (причём как целые, так и вещественные), но и логические значения. При этом считается, что значение true больше, чем значение false.
Помимо операций сравнения ещё существуют и логические операции: AND (конъюнкция, логическое умножение, операция «И»), OR (дизъюнкция, логическое сложение, операция «ИЛИ»), NOT (отрицание, инверсия), XOR (строгая дизъюнкция, исключающее «ИЛИ», сложение по модулю `2`). В скобках указаны возможные названия данных операций в алгебре логики. Операнды этих операций должны быть логического типа. Результат вычислений также будет логический. При этом операции AND, OR, XOR имеют по два операнда, а операция NOT – всего один, который записывается справа от названия операции. Названия логических операций являются ключевыми словами языка. Приведём таблицы результатов логических операций для всех возможных значений операндов (в алгебре логики такие таблицы называются таблицами истинности):
| x | not x |
| false |
true |
|
true |
false |
|
x |
y | x and y |
x or y |
x xor y |
| false | false | false | false | false |
| false | true | false | true | true |
| true | false | false | true | true |
| true | true | true | true | false |
Логический результат даёт также стандартная функция odd(x), которая применяется к целочисленному аргументу `x`:
odd(x) = true, если `x` нечётно;
odd(x) = false, если `x` чётно.
Приоритет операций в логическом выражении следующий:
1) Операция NOT.
2) Операции группы умножения AND, *, / ,div, mod
3) Операции группы сложения OR, XOR, +, -
4) Операции сравнения >, <, >=, <=, =, <>
Операции одного приоритета выполняются слева направо. Операции в круглых скобках имеют более высокий приоритет, чем операции вне скобок.
Записать логическое выражение, истинное в случае, когда переменная `X` имеет значение из отрезков `[2,5]` или `[-1,1]`.
(X>=2) AND (X<=5) OR (abs(X)<=1).
