Системы счисления

Под системой счисления обычно понимают пару преобразований:

«запись» сопоставляет числу (обычно — целому неотрицательному) некий текст
«чтение» сопоставляет тексту (из некоторого множества, обычно меньшего, чем множество всевозможных текстов) число (обычно — целое неотрицательное)

Например, в традиционной десятичной системе счисления результатом записи числа сто двадцать три является текст «123». А результатом чтения текста «0042» является число сорок два.

А, например, в «римской» системе счисления результатом записи числа сто двадцать три является текст «CXXIII».

НЕ СЛЕДУЕТ ПУТАТЬ ЧИСЛА И ИХ ЗАПИСИ! Как говорят, это — различные типы объектов. Один и тот же текст может обозначать совершенно разные числа, а одно и то же число можно записать совершенно по-разному.

В заключение отметим, что многие системы счисления можно приспособить и для чтения/записи некоторых рациональных чисел. Но мы этой темы почти не коснёмся.

Позиционные системы счисления

Введение

Пусть \(d\) — целое положительное число, большее единицы.

Позиционной системой счисления с основанием \(d\) (или, как ещё говорят, \(d\)-ичной системой счисления) называется множество \(D\) (которое далее мы будем называть множеством цифр) и преобразование \(v:D\to\mathbb{N}\), сопоставляющее каждой цифре её числовое значение.

При этом \(v\) должно осуществлять биекцию между \(D\) и числами от \(0\) до \(d-1\). Это означает, что каждое число этого промежутка должно соответствовать ровно одной цифре.

Традиционно множество цифр состоит из знаков 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и букв латинского алфавита. Числовые значения «арабских» цифр стандартны. Числовые значения «латинских» цифр начинаются с десяти и идут в том же порядке, в котором идут латинские буквы. То есть, например, числовое значение буквы «z» равно тридцати пяти.

Под записью мы будем понимать преобразование

\[ W(n) = x_{k}x_{k-1} \ldots x_{0} \]

такое, что:

если \(n=0\), то \(k=0\) и \(v(x_0)=0\)
если \(n>0\), то \(x_{k}\ne0\) и выполнено равенство

\[ n = v(x_k) d^k + v(x_{k-1}) d^{k-1} + \ldots + v(x_0) d^0 \]

Например, \(W(42)=2a\) для шестнадцатиричной системы счисления (значком «42» на входе \(W\) обозначено число сорок два).

Чтение устроено чуть проще:

\[ R(x_{k}x_{k-1}\ldots x_{0}) = v(x_k) d^k + v(x_{k-1}) d^{k-1} + \ldots + v(x_0) d^0 \]

Нетрудно заметить, что \(R(W(x))=x\) (а вот с другим порядком \(R\) и \(W\) это неверно).

Если одновременно рассматривается несколько систем счисления, то обычно их помечают нижним индексом. Например, \(R_{3}\) — троичное чтение, а \(W_{2}\) — двоичная запись. Переводом из системы счисления с основанием \(a\) в систему счисления с основанием \(b\) называют последовательное применение \(R_{a}\) и \(W_{b}\)

Во избежание путаницы договоримся далее, что последовательности цифр внутри формул, не сопровождённые нижним индексом, в числовом контексте следует воспринимать как числа, десятично считанные с этих последовательностей. Последовательности цифр же, сопровождённые индексом \(d\), в числовом контексте следует воспринимать как числа, считанные \(d\)-ично.

Это означает, что формулу

\[ 27+14_5+1101_2 \]

следует интерпретировать как

\[ R_{10}(27) + R_{5}(14) + R_{2}(1101) \]

что, в свою очередь, равно сумме двадцати семи, девяти и тринадцати.

Считывание числа

Операция считывания достаточно примитивна: чтобы считать число, достаточно вычислить значение многочлена

\[ v(x_{k}) d^k + v(x_{k-1}) d^{k-1} + \ldots + v(x_{0}) d^0 \]

Единственное, о чём стоит напомнить: иногда многочлен проще вычислять при помощи так называемой схемы Горнера

\[ \sum_k x^k c_k = (\ldots((c_n x + c_{n-1}) x + c_{n-2}) x + \ldots) x + c_0 \]

Для тех, кому эта формула кажется нечитаемой, приведём аналогичный код (на языке Python):

def evaluate(p,x):
    n = degree(p)
    
    total = coeff(p,n)
    for i in range(n,0,-1):
        total = current * x + coeff(p,i-1)
    
    return total

Например, \(123_{7}\) можно считать по схеме Горнера так:

\[ 123_{7} = (1\cdot 7 + 2)\cdot 7 + 3 = 63 + 3 = 66 \]

Запись числа

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

Сейчас мы приведём два эквивалентных способа записи числа. Первый из них вычисляет цифры, начиная с самой младшей, второй — наоборот, начиная с самой старшей.

Способ первый

Пусть \(N = \sum_k d^k v(a_k)\). Требуется найти цифры \(a_i\) (или хотя бы их числовые значения; будем считать операцию восстановления цифры по числовому значению тривиальной).

Младшую цифру легко определить, если заметить, что

\[ v(a_0) = v(a_0)\bmod d = \left(\sum_k d^k v(a_k)\right)\bmod d \]

Правое из этих двух равенств очевидно, а левое следует из неравенств \(0\leqslant v(a_0) < d\).

Вычтя \(v(a_0)\) из левой и правой частей равенства

\[ N = \sum_k d^k v(a_k) \]

и разделив их на \(d\), получаем такую же по виду задачу для числа \((N-v(a_0))/d\).

Пример

Для того, чтобы записать число \(42\) в троичной системе счисления, можно сделать следующее.

Найдём нулевую цифру: \(v(a_0) = 42 \bmod 3 = 0\).

Далее имеем \(v(a_1) + 3v(a_2) + \ldots = (42-0)/3 = 14\).

Найдём первую цифру: \(v(a_1)=14\bmod 3 = 2\).

Далее имеем \(v(a_2) + 3v(a_3) + \ldots = (14-2)/3 = 4\).

Найдём вторую цифру: \(v(a_2)=4\bmod 3 = 1\).

Далее имеем \(v(a_3) = (4-1)/3 = 1\).

То есть \(W_3(42)=1120\).

Способ второй

Старшую цифру числа \(N\) можно найти так: ищем максимальное \(m\), для которого \(d^m\leqslant N\). Далее ищем максимальное \(c\), для которого \(c d^m\leqslant N\). Это \(c\) и будет числовым значением старшей цифры. Осталось таким же образом найти цифры числа \(N-c d^m\).

Пример

Поскольку \(3^3=27\) «умещается» ровно один раз в числе \(42\), старшая троичная цифра этого числа равна 1.

Остаётся \(42-27=15\). \(3^2=9\) «умещается» в \(15\) тоже один раз. Поэтому следующая троичная цифра числа \(42\) тоже равна 1.

Остаётся \(15-9=6\). \(3^1=3\) «умещается» в \(6\) два раза. Поэтому следующая троичная цифра числа \(42\) равна 2.

Остаётся \(0\), в котором \(3^0=1\) умещается ноль раз. Поэтому последняя цифра троичной записи \(42\) равна 0, а вся запись: 1120.

Быстрый перевод

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

Например, восьмеричных цифр столько же, сколько и троек двоичных. Отсюда следует (поймите, почему!), что число можно перевести из восьмеричной в двоичную, просто заменив каждую цифру на тройку двоичных с тем же значением.

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

Например, переведём 12321 из четверичной системы счисления в восьмеричную:

каждая четверичная цифра соответствует паре двоичных: 0 — паре 00, 1 — паре 01, 2 — паре 10, 3 — паре 11
значит, \(12321_{4} = 0110111001_{2}\)
теперь нужно сгруппировать цифры по три (начиная с самой младшей!): 0 110 111 001
осталось, наконец, записать соответствующие восьмеричные цифры (отбросив ведущий ноль): 671

Кодировка чисел в памяти ЭВМ

Целые числа

К настоящему моменту почти любая ЭВМ использует память, подразделяющуюся на байты — восьмёрки бит. Каждый бит может принимать одно из двух значений (будем их обозначать 0 и 1). Соответственно, каждый байт может принимать одно из двухсот пятидесяти шести значений. Для записи этих значений обычно используют пары шестнадцатиричных цифр: 00, 01, 02, … ff.

Соответственно, для записи целых чисел в память ЭВМ обычно используют 256-ричную систему счисления. При этом различают несколько форматов записи. У каждого формата есть:

порядок цифр (байт): Little Endian (от младших цифр к старшим) и Big Endian (от старших цифр к младшим)
количество байт: обычно 1, 2, 4, 8 или 16
диапазон: «без знака» (от \(0\) до \(N-1\)) или «со знаком» (от \(-N/2\) до \(N/2 - 1\)), где \(N\) — общее количество комбинаций используемых байт

При этом для записи чисел диапазона «без знака» используется обычная 256-ричная система счисления, а числа диапазона «со знаком» записываются так же, как их остатки по модулю \(N\) в формате «без знака».

Например, в 2-байтовом LE-формате без знака число \(1234\) имеет вид d2 04.

А в 1-байтовом формате со знаком число \((-123)\) записывается так же, как и \(256-123=133\) без знака: 85.

Числа с плавающей точкой

Для записи рациональных чисел обычно используется формат с плавающей точкой. Устроен он так: все биты кода (который обычно имеет ширину 16 бит, 32 бита или же 64 бита) делятся на три части:

самый старший бит называется знаком
следующие несколько бит называются экспонентой (или степенью)
оставшиеся биты называются мантиссой (или значащей частью)

Для стандартных форматов используются следующие размеры экспонент:

16 бит («половинная» точность) — 5-битная экспонента
32 бита («одинарная» точность) — 8-битная экспонента
64 бита («двойная» точность) — 11-битная экспонента

Знак задаёт луч, на котором находится число. Знак 0 — неотрицательные числа, знак 1 — неположительные.

Луч (будем все его точки обозначать расстоянием до нуля) разбивается на отрезки:

нулевой — от \(0\) до \(2^{-N}\) для некоторого \(N\)
первый — от \(2^{-N}\) до \(2^{-N+1}\)
каждый следующий получается из предыдущего умножением на два

При этом отрезок от \(1\) до \(2\) имеет номер вида \(01\ldots1\) (здесь 4, 7 или 10 единиц).

Экспонента (кроме экспоненты \(1\ldots 1\), которая зарезервирована) — (записанный двоично) номер такого отрезка. Числа с нулевой экспонентой называются денормализованными.

Далее каждый отрезок разбивается на одинаковые части (количеством, равным количеству всевозможных значений мантиссы). Мантисса — порядковый номер левого деления такой части.

Итого, если знак равен \(s\), экспонента равна \(e\) и отлична от крайних значений, мантисса равна \(m\), ширина экспоненты равна \(E\) бит, а ширина мантиссы равна \(M\), то эти данные кодируют число

\[ (-1)^s \cdot 2^{1 + e - 2^{E-1}} \cdot (1 + m\cdot 2^{-M}) \]

В конце концов биты разбиваются на байты и записываются в LE- или BE-порядке.

Пример

Чтобы закодировать число \((-23.75\) в LE-формат половинной точности, проведём следующие действия.

Знак равен 1 (т.к. число отрицательное).

Подберём экспоненту:

01111 соответствует отрезку от 1 до 2
10000 соответствует отрезку от 2 до 4
10001 соответствует отрезку от 4 до 8
10010 соответствует отрезку от 8 до 16
10011 соответствует отрезку от 16 до 32

Последний отрезок нам и нужен.

Теперь будем определять мантиссу:

мантиссы с началом 0 кодируют числа отрезка от 16 до 24
мантиссы с началом 01 кодируют числа отрезка от 20 до 24
мантиссы с началом 011 кодируют числа отрезка от 22 до 24
мантиссы с началом 0111 кодируют числа отрезка от 23 до 24
мантиссы с началом 01111 кодируют числа отрезка от 23.5 до 24
мантиссы с началом 011111 кодируют числа отрезка от 23.75 до 24

Нам как раз нужно начальное число последнего отрезка. Поэтому наша мантисса имеет вид 0111110000.

Итого биты нашего числа: 1 10011 0111110000. Их 256-ричная запись: cd f0.

Осталось записать эти два байта в формате LE: f0 cd.

Алгебра логики

Для закрепления материала настоятельно советуется ресурс NAND Game, который демонстрирует способ построения нетривиальной ЭВМ на основе одной логической операции (штриха Шеффера, о котором кратко повествуют следующие разделы).

Основные операции и законы

Основные операции

Общепринятым для цифровой электроники стандартом является использование двух элементарных сигналов: условно \(0\) и \(1\). В связи с этим наиболее простой моделью такой электроники является отображение \(\mathbf{2}^m\to \mathbf{2}^n\), имеющее, грубо говоря, \(m\) двоичных входов и \(n\) двоичных выходов (символом \(\mathbf{2}\) здесь обозначено множество \({0,1}\)).

Отображения \(\mathbf{2}^n\to \mathbf{2}\) мы будем называть логическими операциями арности \(n\) или \(n\)-арными операциями. Элементарные величины \(0\) и \(1\) можно считать операциями арности \(0\). Всего \(n\)-арных операций, как нетрудно вычислить, \(2^{2^n}\). В частности, есть четыре унарных операции и шестнадцать бинарных. Наиболее интересны следующие:

Отрицание: \(\lnot 0 = 1\) и \(\lnot 1 = 0\).

Альтернативные обозначения: \(\lnot x = \overline{x} = \,!x\).

Конъюнкция: \(x\land y = 1\) тогда и только тогда, когда \(x=1\) и \(y=1\).

Альтернативные обозначения: \(x\land y = x\cdot y = x\times y = xy = x \& y\).

Дизъюнкция: \(x\lor y = 1\) тогда и только тогда, когда хотя бы кто-то из \(x\) или \(y\) равен \(1\).

Альтернативные обозначения: \(x\lor y = x\,|\,y = x+y\).

Сложение (или XOR от eXclusive OR): \(x\oplus y = (x+y)\bmod 2\).

Альтернативные обозначения: \(x\oplus y = x+y\).

Импликация: \(x\Rightarrow y = \overline{x} \lor y\).

Штрих Шеффера (или NAND от Not AND): \(x\,|\,y = \lnot(xy)\).

Стрелка Пирса (или NOR от Not OR): \(x\downarrow y = \lnot(x\lor y)\).

Как можно заметить, некоторые обозначения используются сразу для нескольких операций. Поэтому мы остановимся на некоторой единой системе обозначений: \(\lnot x\) и \(\overline{x}\) — для отрицания, \(xy\) и \(x\land y\) — для конъюнкции, \(x\lor y\) — для дизъюнкции, \(x + y\) — для сложения.

Алгебраические свойства

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

Законы де Моргана: \(\overline{x\land y} = \overline{x}\lor\overline{y}\) и \(\overline{x\lor y} = \overline{x}\land\overline{y}\).

Снятие двойного отрицания: \(\lnot\lnot x = x\).

Третьего не дано: \(x\lor\overline{x} = 1\).

Коммутативность: \(xy=yx\) (выполняется также для \(\lor\) и \(+\)).

Ассоциативность: \(x(yz)=x(yz)\) (выполняется также для \(\lor\) и \(+\)).

Дистрибутивность: \(x(y+z)=xy+xz\) (выполняется также для \(\lor,\land\) и \(\land,\lor\)).

Идемпотентность: если \(n\geqslant 1\), то \(x^n=x\).

СДНФ и СКНФ

Нормальные формы

Начнём с пары терминов. Предположим, что есть некий набор правил преобразования формул. Например:

\(\lnot\lnot x\) разрешается заменить на \(x\)
\(\lnot(x\land y)\) разрешается заменить на \(x\lor y\)
\(\lnot(x\lor y)\) разрешается заменить на \(x\land y\)

Нормализацией формулы при помощи набора правил называется последовательное применение этих правил к подформулам этой формулы.

Нормальной формой называется формула, ни к одной подформуле которой нельзя применить ни одно из правил набора.

Например, формула \(x\land\lnot y\) является нормальной формой относительно вышеприведённого набора правил.

А вот формула \(\lnot(x\land\lnot y)\) не является. При этом её можно нормализовать, получив нормальную форму \(\lnot x\lor y\).

Отметим несколько важных моментов:

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

Совершенная дизъюнктивная нормальная форма

Рассмотрим следующую задачу: имея некий набор операций, научиться выражать произвольную операцию в виде комбинации имеющихся. Оказывается, для набора \(\land,\lor,\lnot\) эта задача решается особенно легко: если \(f(x) = 1\) только для \(x=(x_1,x_2,\ldots,x_n)=(a_1,a_2,\ldots,a_n)\), то

\[ f(x_1,x_2,\ldots,x_n)= (\lnot^{\lnot a_1} x_1)(\lnot^{\lnot a_2} x_2)\ldots (\lnot^{\lnot a_n} x_n) \]

В общем случае достаточно взять дизъюнкцию таких выражений для всех \(a\), для которых \(f(a)=1\).

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

Результатом такой манипуляции является штуковина (дизъюнкция конъюнкций), называемая совершенной дизъюнктивной нормальной формой (коротко СДНФ) операции \(f\). Например, импликация имеет СДНФ

\[ x\Rightarrow y = \overline{x}\,\overline{y}\lor \overline{x}y\lor xy \]

Нетрудно заметить, что СДНФ определена с точностью до перестановки конъюнктов внутри дизъюнктов и перестановки самих дизъюнктов.

Совершенная конъюнктивная нормальная форма

Аналогичным образом можно построить «двойственный» объект — СКНФ.

Для этого нужно рассмотреть все наборы входов, на которых рассматриваемая операция имеет нулевое значение, и для каждого написать дизъюнкцию входов и/или их отрицаний, дающую 0 только на этом наборе.

Написанные дизъюнкции следует соединить операциями конъюнкции.

Например, для XOR СКНФ имеет вид

\[ x\oplus y = (\overline{x}\lor\overline{y})\land (x\lor y) \]

А для импликации СКНФ следует запомнить наизусть:

\[ x\Rightarrow y = \overline{x}\lor y \]

И опять NAND

Наличие СДНФ и СКНФ у произвольной зависимости показывает, что любую зависимость можно реализовать лишь комбинируя дизъюнкции с отрицаниями (или конъюнкции с отрицаниями).

Тем не менее, при некотором желании можно обойтись и одной операцией. К таким универсальным операциям относятся, например, NAND (и заодно его двойственная операция — NOR).

Это следует из (тривиально проверяемых) соотношений

\(\lnot x = x\,|\,x\)
\(x\land y = \lnot(x\,|\,y) = (x\,|\,y)\,|\,(x\,|\,y)\)

Элементы программирования

Немного об языке Си

Средства разработки

У языка Си есть три основных реализации:

Первые две — наборы утилит командной строки. Третья — полноценная среда разработки (но утилиты командной строки тоже есть).

Также возможность запустить программу на языке Си предоставляют сервисы типа repl.it и ideone.

Отметим, что использование среды разработки при программировании на Си не даёт почти никаких преимуществ перед использованием обычного текстового редактора. Единственное полезное свойство текстового редактора, действительно влияющее на удобство использования: (хотя бы минимальная) подсветка синтаксиса.

Литература

Есть классическая книга The C Programming Language под авторством Brian Kernighan и Dennis Ritchie (второй из них по совместительству является одним из создателей языка Си). У неё есть переводы на русский язык.

Наиболее актуальный справочник по современному Си — сайт cppreference.com.

Тривиальная программа

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

int main(void) {
    return 0;
}

Стандартный способ запуска (в POSIX-окружениях) следующий:

сохранить текст программы в файл с суффиксом .c (например, trivial.c)
запустить компилятор с правильными аргументами (например, gcc trivial.c -o trivial)
запустить полученный исполняемый файл (./trivial)

Структура программы

Программа на языке Си представляет собой последовательность определений. Каждое из них определяет хотя бы одно из:

глобальную переменную
тип данных
подпрограмму

В частности, вышеприведённая тривиальная программа состоит из одного определения, определяющего подпрограмму с названием main.

Подпрограммы задаются последовательностью команд (или, как их ещё называют, предложений). Вышеприведённая подпрограмма main состоит из одной команды return 0;, смысл которой «завершить работу текущей подпрограммы с результатом 0».

Часть int ...(void) определения этой подпрограммы задаёт её тип: ограничения на то, как эту подпрограмму можно использовать. Конкретно этот тип означает, что:

результатом подпрограммы main является нечто типа int
входов у этой подпрограммы нет

Для того, чтобы все эти слова приобрели какой-нибудь осязаемый смысл, приведём пример нетривиальной программы.

Игра «угадай число»

Замысел следующий: программа загадывает случайное число в пределах от 1 до 100 и предлагает его отгадать. Если игрок вводит неправильное число, программа сообщает, больше или меньше это число, чем загаданное. Если же игрок вводит загаданное число, программа поздравляет его и завершает свою работу.

Весь код разместим в одном файле, который назовём guess.c (это название никакой роли не играет).

Начнём со следующего:

#include <stdio.h>

int main(void) {
    printf("Угадай число!\n");

    int number;

    while (1) {
        int items_read = scanf("%d", &number);

        if (items_read == 0) { getchar(); continue; }
        if (items_read == 1) { break; }
    
        printf("Произошла ошибка чтения\n");
        return 1;
    }

    printf("Вы ввели число %d\n", number);

    return 0;
}

Разберём эту программу построчно.

Директивы препроцессора

Первая же строчка

#include <stdio.h>

технически вообще не относится к языку Си. Это — так называемая директива препроцессора. Препроцессор — специальная программа, которая предобрабатывает текст программы в соответствии со встреченными в нём директивами.

В частности, директива #include предписывает вставить вместо неё содержимое указанного текстового файла (в данном случае stdio.h).

В POSIX-окружениях вывод препроцессора можно увидеть, запустив команду cpp guess.c.

В файле stdio.h (который размещён в специальном месте, известном компилятору) содержатся определения подпрограмм printf, scanf и getchar, которые мы использовали для ввода-вывода. Впрочем, с очень большой вероятностью, посмотрев на выхлоп cpp guess.c, Вы увидите там частичные определения вида

int getchar(void);

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

Формулы

Далее идёт определение подпрограммы main, тело которой начинается с команды

printf("Угадай число!\n");

Результатом исполнения этой команды является появление в терминале фразы «Угадай число!»: в этом нет ничего неожиданного. А вот синтаксическая структура здесь весьма интересна: эта команда относится к классу «вычислить значение формулы» и имеет синтаксис ФОРМУЛА ; (пробелы в языке Си несущественны и необходимы лишь там, где они разделяют, например, тип и название переменной/подпрограммы).

Формулы (или, как их ещё называют, выражения) — особая грамматическая категория. Формулы встречаются в составе большинства команд. Они составляются из идентификаторов, литералов и операторов. В частности, рассматриваемая нами формула составлена из:

идентификатора printf
текстового литерала "Угадай число!\n"
оператора ...(...)

Набор операторов в языке Си фиксирован: это всякие +, -, *, / и прочее.

Литералы бывают текстовые ("Hello"), символьные ('H'), числовые (42) и составные (о последних мы сейчас говорить не будем). Они используются для обозначения объектов с заранее известным значением. При желании можно считать литералы просто операторами арности 0 (то есть с нулём входов) со специальным синтаксисом.

Идентификаторы используются для обозначения объектов, процедура вычисления которых описана в программе (переменные и подпрограммы). Также идентификаторы используются для обозначения типов данных.

У (почти) любой формулы есть значение. В частности, значением формулы printf("Hello!") является число 6 (длина напечатанного текста в байтах) типа int. Само же появление текста на экране является побочным эффектом вычисления. Многие побочные эффекты невозможно использовать в дальнейших вычислениях (например, очень непросто, а иногда даже и невозможно обратно достать с экрана напечатанный туда текст).

Значение большинства формул вычисляется по следующему алгоритму:

сначала вычисляются значения всех подформул
затем эти значения используются для вычисления значений формулы

Исключений в языке Си ровно четыре: формулы, составленные при помощи логических операторов &&, || и ? : (эти операторы мы рассмотрим в рамках соответствующего раздела) и формулы, составленные при помощи унарного & (о нём — ниже).

Переменные

Затем следует определение переменной number:

int number;

Определение переменной в простейшем случае выглядит как ТИП ИДЕНТИФИКАТОР;. Переменную можно рассматривать как именованную область памяти.

Чтобы считать текущее значение переменной, достаточно просто в формуле использовать её название.

Чтобы записать в переменную какое-то значение, используется команда присваивания. Например, команда

number = 2+3;

вычисляет значение формулы 2+3 и записывает в переменную number.

Обратите внимание на то, что допустимы на первый взгляд цикличные команды вида

number = number + 1;

Работают они только засчёт того, что команда присваивания:

сначала вычисляет значение «правой части»
только затем записывает его в переменную

Тип переменной — средство ограничения набора корректных программ. У каждой формулы есть не только значение (определяемое значениями подформул), но и тип (определяемый типами подформул). В переменную типа X можно записывать только значения формул, имеющих тип X или же тип, который неявно преобразуется к типу X (в частности, все числовые типы в языке Си могут быть неявно преобразованы друг к другу).

Что интересно, почти все типы (за исключением т.н. структур и объединений) в языке Си являются числовыми. Это — один из основных источников трудноуловимых ошибок.

В частности, тип int — целое число в пределах от \(-2^N\) до \(2^N - 1\) для некоторого \(N\) (обычно 15 или 31).

Управляющие конструкции

Далее в программе идёт цикл while:

while (1) {
    ...
}

У него следующий синтаксис: while (УСЛОВИЕ) ПРЕДЛОЖЕНИЕ. Он повторяет выполнение предложения до тех пор, пока условие не станет ложным.

Заметим две важные вещи:

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

Про составные предложения полезно понимать следующее:

переменные, определённые внутри составного предложения, можно использовать только внутри него
определение подпрограммы состоит из типа подпрограммы, её названия и (обязательно) составного предложения

Указатели

Первая же строчка внутри цикла

int items_read = scanf("%d", &number);

содержит определение переменной с начальным значением. Значение переменной обязательно задавать перед первым же чтением (но программа соберётся, даже если его не задать — а вот поведение такой программы будет весьма непредсказуемым).

Если внимательно посмотреть на правую часть определения, то в нём подпрограмма scanf применяется к формулам "%d" (это — самый обычный текстовый литерал, содержимое которого релевантно для scanf) и &number (а вот это — пример применения вышеупомянутого оператора &).

Подформулой унарного & может быть одно из двух:

имя переменной или подпрограммы
формула, внешней операцией которой является унарный *

Тот же класс формул (за исключением имён подпрограмм) допускается в качестве левых частей команды присваивания.

Сейчас мы не будем обсуждать второй класс подформул. Ограничимся лишь формулами вида &foo, где foo — имя переменной (или подпрограммы).

Значением такой формулы является «адрес переменной» — нечто, позволяющее получить полный доступ к этой переменной (на чтение и на изменение).

В частности,

scanf("%d", &number)

пытается считать целое число и, если считывание произошло успешно, записывает это число в переменную number.

В языке Си, в отличие, например, от Паскаля или Си++, нет возможности передать в подпрограмму именно переменную: правила вычисления значения формул едины для всех формул. Большинство современных языков программирования пошли именно по этому пути: тот факт, что переменная не может измениться без явного & или =, облегчает понимание программы.

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

Ещё немного управляющих конструкций

После чтения числа идёт следующий код:

if (items_read == 0) { getchar(); continue; }
if (items_read == 1) { break; }
    
printf("Произошла ошибка чтения\n");
return 1;

Результатом scanf является:

либо количество успешно считанных и распознанных единиц данных
либо специальное число EOF при ошибке чтения (именно чтения, а не распознавания)

При ошибке распознавания scanf просто останавливается (из входного потока при этом изымаются все символы до того который вызвал ошибку распознавания, не включая ошибочный символ).

Команды continue; и break; управляют текущим циклом: первая — переходит к следующей его итерации, вторая — переходит к его концу.

Подпрограмма getchar считывает ровно один байт со стандартного входа.

Команда return 1; приводит к завершению текущей подпрограммы (то есть, в нашем случае — int main(void)). После return может стоять любая формула. Значение этой формулы станет значением завершаемой подпрограммы.

Для main используется следующая договорённость:

значение 0 означает, что выполнение всей программы прошло без ошибок
любое другое значение означает, что программа завершила работу в результате какой-то ошибки

Интерпретация этого значения остаётся на совести операционной системы.

Соответственно, в зависимости от результата scanf мы делаем одно из:

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

Ветвление осуществляется при помощи конструкции if с тем же синтаксисом, что и у while.

Ввод-вывод

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

Например, printf в шаблоне "Вы ввели число %d\n" находит специальную последовательность %d и заменяет её на целое число (переданное printf вторым входом). Подробнее про синтаксис шаблонов printf можно почитать в описании этой подпрограммы.

Аналогичен синтаксис шаблонов подпрограммы ввода scanf. Стоит лишь отметить, что scanf игнорирует пробелы (то есть %d%d — два целых числа, отделённые друг от друга пробельными символами).

Следует следить, чтобы количество дополнительных входов и типы этих входов соответствовали спецпоследовательностям. Компилятор, конечно, выдаёт предупреждения о несоответствии, но не любой и не всегда.

В заключение отметим, что \n — это не спецпоследовательность форматированного ввода-вывода, а часть синтаксиса текстовых литералов. Называются такие штуки «экранирующими последовательностями». Чаще всего можно встретить:

\n — переход на следующую строчку
\r — возврат «каретки» в начало строчки
\\ — обратная косая черта
\" — двойная кавычка

Выделяем кусок программы в подпрограмму

Теперь рассмотрим следующую модификацию вышеприведённой программы:

#include <stdio.h>

int read_number(int *number) {
    while (1) {
        int items_read = scanf("%d", number); // здесь пропал &

        if (items_read == 0) { getchar(); continue; }
        if (items_read == 1) { return 0; } // а здесь теперь return вместо break

        return 1;
    }
}

// двумя косыми чёртами выделяется комментарий: он полностью игнорируется компилятором

/* Ещё
бывают многострочные
комментарии. */

int main(void) {
    printf("Угадай число!\n");

    int number;

    if (read_number(&number)) { 
        printf("Произошла ошибка чтения\n");
        return 1;
    }

    printf("Вы ввели число %d\n", number);

    return 0;
}

Нам необходимо будет многократно просить ввести число, а писать нетривиальный цикл внутри нетривиального цикла — сомнительной полезности действие (результат становится малочитаемым).

Поэтому часть программы, считывающую число, мы изолировали в отдельную подпрограмму read_number.

У определения подпрограмм синтаксис приблизительно следующий:

ТИП_РЕЗУЛЬТАТА имя(ТИП_ВХОДА1 имя_входа1, ТИП_ВХОДА2 имя_входа2, ...) {
    ТЕЛО_ПОДПРОГРАММЫ
}

Есть одно исключение: если у подпрограммы нет входов, вместо списка входов нужно написать слово void. То же слово нужно написать вместо типа результата, если у подпрограммы нет результата (а используется она только ради побочных эффектов).

Обратите внимание на то, что (в отличие от Си++) пустой список входов означает не отсутствие входов, а произвольное их количество!

В заключение скажем, что определение

int read_number(int *number) {
  ...
}

не попадает под вышеописанную схему: int *number (говорящая, что number — это указатель на данные типа int) — это конструкция, более сложная, чем ТИП имя. Подробнее про такие конструкции, опять же, — в соответствующем разделе.

Загадываем число

Теперь, наконец, можно уже давать много попыток угадать число:

#include <stdio.h>

int read_number(int *number) {
    while (1) {
        int items_read = scanf("%d", number);

        if (items_read == 0) { getchar(); continue; }
        if (items_read == 1) { return 0; }

        return 1;
    }
}

int main(void) {
    printf("Угадай число!\n");

    int to_guess = 42;  // пока загаданное число "зашито" в коде

    int number;

    while (!read_number(&number)) { 
        printf("Вы ввели число %d", number);

        if (number > to_guess) {
            printf(": ваше число больше загаданного!\n");
        } else if (number < to_guess) {
            printf(": ваше число меньше загаданного!\n");
        } else {
            printf(" и угадали!\n");
            return 0;
        }
    }

    printf("Произошла ошибка чтения\n");
    return 1;
}

В этой программе из нового лишь «гребёнка» вида

if (...) { ... }
else if (...) { ... }
else if (...) { ... }
  ...
else if (...) { ... }
else { ... }

Формально с точки зрения грамматики это — нагромождение предложений вида

if (ФОРМУЛА) ПРЕДЛОЖЕНИЕ1 else ПРЕДЛОЖЕНИЕ2

Семантика подобных предложений банальна:

вычисляется значение формулы
если оно истинно, выполняется ПРЕДЛОЖЕНИЕ1
в противном случае выполняется ПРЕДЛОЖЕНИЕ2

Теперь нам осталось загадывать случайное число вместо 42.

По-настоящему загадываем число

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int read_number(int *number) {
    while (1) {
        int items_read = scanf("%d", number);

        if (items_read == 0) { getchar(); continue; }
        if (items_read == 1) { return 0; }

        return 1;
    }
}

int main(void) {
    srand(time(0));

    printf("Угадай число от 1 до 100!\n");

    int to_guess = 1 + (rand() % 100);

    int number;

    while (!read_number(&number)) { 
        printf("Вы ввели число %d", number);

        if (number > to_guess) {
            printf(": ваше число больше загаданного!\n");
        } else if (number < to_guess) {
            printf(": ваше число меньше загаданного!\n");
        } else {
            printf(" и угадали!\n");
            return 0;
        }
    }

    printf("Произошла ошибка чтения\n");
    return 1;
}

Здесь используется классическая идиома. Один раз в начале программы инициализируется генератор псевдослучайных чисел текущим временем:

srand(time(0));

После этого случайное целое неотрицательное число можно получить подпрограммой rand. В нашем случае мы берём его по модулю 100:

rand() % 100

Отметим, что a % b является остатком a по модулю b только при неотрицательных значениях a. При отрицательных значениях a результатом является разность этого остатка и абсолютной величины b.

Разбиваем программу на файлы

В конце этого раздела продемонстрируем, как разбить программу на несколько файлов. Для этого сделаем три файла.

Файл guess.c:

// файлы, которые следует искать в служебной папке компилятора, обрамляются уголками:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// файлы, которые следует искать в той же папке, обрамляются кавычками:
#include "util.h"  

int main(void) {
    srand(time(0));

    printf("Угадай число от 1 до 100!\n");

    int to_guess = 1 + (rand() % 100);

    int number;

    while (!read_number(&number)) { 
        printf("Вы ввели число %d", number);

        if (number > to_guess) {
            printf(": ваше число больше загаданного!\n");
        } else if (number < to_guess) {
            printf(": ваше число меньше загаданного!\n");
        } else {
            printf(" и угадали!\n");
            return 0;
        }
    }

    printf("Произошла ошибка чтения\n");
    return 1;
}

Файл util.c:

#include <stdio.h>

int read_number(int *number) {
    while (1) {
        int items_read = scanf("%d", number);

        if (items_read == 0) { getchar(); continue; }
        if (items_read == 1) { break; }

        return 1;
    }

    return 0;
}

Наконец, файл util.h:

#ifndef UTIL_H
#define UTIL_H

int read_number(int *number);

#endif

По сути, мы сделали три вещи:

вынесли подпрограмму read_number в отдельный файл util.c
в main.c добавили строчку int read_number(int *number);
вынесли эту строчку в отдельный файл util.h, обрамив непонятной на первый взгляд конструкцией препроцессора #ifndef ... #define ... #endif

Чтобы понять, зачем так сделано, полезно знать традиционную процедуру сборки программы на Си:

каждый файл программы (guess.c и util.c) независимо от остальных файлов «компилируется» в некий промежуточный формат (обычно промежуточные файлы имеют названия, заканчивающиеся на .o)
из нескольких промежуточных файлов «собирается» единая программа

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

Для объявления типа функции используется т.н. прототип:

ТИП_РЕЗУЛЬТАТА имя_функции(...);  // тут точка-с-запятой вместо тела

Для объявления типа глобальной переменной используется конструкция

extern ТИП_ПЕРЕМЕННОЙ имя_переменной;

Отметим также, что прототипы встречаются и в случае циклических зависимостей внутри одного файла:

int is_odd(int n); // прототип is_odd

int is_even(int n) {
  if (n == 0) { return 1; }
  return is_odd(n-1); 
  // программа читается сверху вниз _один раз_, поэтому к этому моменту 
  // должен быть объявлен тип подпрограмммы is_odd
}

int is_odd(int n) {
  if (n == 0) { return 0; }
  return is_even(n-1);
}

Осталось поговорить об util.h. Традиционно вместе с библиотекой подпрограмм (файлом, предназначенном для «компиляции») поставляется файл с прототипами. Сделано это по двум причинам:

Чтобы пользователь библиотеки не копипастил эти прототипы из исходника.
Часто библиотеки поставляются даже не в виде исходника, а сразу в промежуточном формате.

В начале util.h есть строчки

#ifndef UTIL_H
#define UTIL_H

А в конце стоит

#endif

Директива #define определяет макрос — идентификатор, все вхождения которого в программу заменяются на указанный текст.

Например, вместо printf("%d\n", 2 + 3); можно написать

#define PRINT printf(
#define NUMBER "%d\n",
#define END );

PRINT NUMBER 2 + 3 END

При помощи #ifdef или #ifndef можно проверить наличие/отсутствие определённого макроса с указанным названием. Если такое условие не выполняется, то весь кусок файла между #ifdef или #ifndef и #endif удаляется.

Поэтому #ifndef ... #define ... #endif гарантирует, что содержимое файла попадёт в компилируемый файл не более одного раза, независимо от того, сколько раз util.h был вставлен при помощи #include.

Конечно, если в таком .h-файле находятся только прототипы, множественные включения особо не вредят (но злоупотребление может привести к тому, что во время компиляции закончится оперативная память компьютера). А вот если там есть что-то ещё (определения переменных или функций), множественное включение приведёт к ошибке компиляции.

Собираем программу

Для сборки программы следует поместить все три файла (guess.c, util.c, util.h) в одну и ту же папку, сделать её «текущей рабочей» и вызвать компилятор.

Для компилятора gcc (и clang) синтаксис следующий:

gcc -o имя_исполняемого_файла guess.c util.c

Промежуточные файлы при этом создаются во временной папке (а не в текущей), а разделение на этап «компиляции» и этап «сборки» скрыто.

Отметим, что сервис repl.it автоматически собирает программу из всех .c-файлов проекта.

Алгоритмические конструкции языка Си

Предисловие

Этот раздел — почти точная копия соответствующей краткой справки из первого блока упражнений в тестирующей системе.

Составная команда

{ команда_1 команда_2 ... команда_n }

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

Пример

int sum = 0;
{   
    // Внутри составной команды принято делать отступ, 
    // единый для всех подкоманд этой команды. 
    int temp = 0;
    scanf("%d", &temp); sum += temp;
    scanf("%d", &temp); sum += temp;
}

printf("Сумма введённых чисел равна %d\n", sum);
// А вот переменной temp здесь уже нет!

Ветвление

if (формула) команда1

или

if (формула) команда1 else команда2

Вычисляет формулу, значением которой должно быть число. Если получился результат, отличный от 0, то выполняется команда1. В противном случае выполняется команда2.

Вариант

if (A) B

эквивалентен

if (A) B else {}

Настоятельно рекомендуется с if (и прочими подобными конструкциями) использовать только составные команды: это позволяет избежать многих трудноуловимых ошибок.

Пример

if      (x > 5) { printf("Очень много!\n"); }
else if (x > 3) { printf("Больше тройки!\n"); }
else if (x > 0) { printf("Чуть-чуть...\n"); }
else            { printf("Ноль или меньше.\n"); }

Прыжки

Перед большей частью команд (за исключением определений переменных) можно поставить метку: слово, за которым идёт двоеточие (не обязательно слитно).

Перейти к исполнению команды, следующей за меткой, можно при помощи команды

goto имя_метки;

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

Пример

int main(void) {
    int status = 0;

    FILE *file = fopen("words.txt", "w");
    if (!file) {
        // не удалось открыть файл на запись
        return 1;  // (число 1 было выбрано произвольно: это не стандарт)
    }

    if (0 > fprintf(file, "Вася ест грибы...\n")) {
        // произошла ошибка записи в файл
        status = 2; // (число 2 было выбрано произвольно: это не стандарт)
        goto close_file;
    }

    fseek(file, 0, SEEK_SET);
    if (0 > fprintf(file, "Петя")) { status = 2; goto close_file; }

    printf("Теперь грибы ест Петя!\n");

close_file:
    fclose(file);

    return status;
}

Цикл while

Конструкция

while (A) команда

эквивалентна

метка: if (A) { команда goto метка; }

Пример

int A = a;
int B = b;

while (b != 0) {
    int rem = a % b;
    a = b;
    b = rem;
}

if (a < 0) { a = -a; }

printf("НОД чисел %d и %d равен %d\n", A, B, a);

Цикл for

В языке Си и подобных ему цикл for устроен весьма непросто. Поэтому, если с ним возникают сложности, лучше временно от него отказаться и использовать while.

Конструкция

for(A; B; C) D

эквивалентна

{ A; while(B) { D C; } }

Пример

int sum = 0;

for (int i = 1; i < 10; i += 1) {
    sum += i;
}

printf("Сумма чисел от 1 до 9 равна %d\n", sum);

Управление циклами

Внутри циклов допустимы команды continue; и break;. Первая прыгает к концу тела цикла, а вторая — за его пределы.

Говоря более формально, рассмотрим два цикла с метками:

while(...) { ... A: ; } B: ;

for(...) { ... A: ; } B: ;

Команда continue; эквивалентна goto A;, а команда break; эквивалентна goto B;.

Арифметика

В заключение приведём список полезных арифметических операторов:

+, -, * — сумма, разность, произведение
/, % — частное (для целых чисел — неполное) и остаток (при неотрицательной левой части)
==, >, <, >=, <= — равно, больше, меньше, больше-или-равно, меньше-или-равно
&, |, ^, ~ — поразрядные конъюнкция, дизъюнкция, xor и отрицание
! — отрицание (превращает неноль в ноль, а ноль — в единицу)
&& — ленивая конъюнкция; вычисляет свою правую подформулу тогда и только тогда, когда значение левой отлично от нуля
|| — ленивая дизъюнкция; вычисляет свою правую подформулу тогда и только тогда, когда значение левой равно нулю

Также к большинству арифметических операторов есть соответствующая разновидность оператора присваивания. Например:

foo += bar; baz |= quuz;

эквивалентно

foo = foo + bar; baz = baz | quuz;

Пример

В примере продемонстрируем, насколько полезной бывает ленивая логика:

if (b != 0 && a % b == 0) {
    //        ^^^^^^^^^^  нельзя вычислять, не убедившись ПРЕДВАРИТЕЛЬНО
    //                    в том, что b не ноль: это приведёт к ошибке
    printf("Число %a делится на число %b\n", a, b);
}

Материалы 8М 2020/2021