Все статьи » ЗФТШ Информатика

Статьи , страница 5

  • §2. Структура программы

    Рассмотрим общую структуру программы на языке Pascal. Программа состоит из двух частей: разделов описаний и раздела действий (команд, операторов). Раздел операторов представляет собой некую последовательность команд (операторов), которые должен выполнить компьютер. Другими словами, раздел действий – это собственно программа. В разделах описаний программист сообщает компьютеру, какие объекты он будет использовать в своей программе, сколько памяти под них нужно выделить и т. д.
    Из всего перечисленного выше обязательным для каждой программы является лишь раздел действий. Разделов описания в программе может и не быть (хотя в содержательных задачах они будут). Раздел действий начинается с ключевого слова begin, далее записывается список операторов (собственно программа) и в конце пишется ключевое слово end и ставится точка. Внутри списка все операторы отделяются друг от друга специальным символом – точкой с запятой. В этом задании мы познакомимся со следующими операторами:

    1) пустой оператор;

    2) составной оператор;

    3) оператор присваивания;

    4) условный оператор;

    5) операторы цикла;

    6) операторы вывода;

    7) операторы ввода.

    Начнём с пустого оператора. В языке Pascal пустой оператор – это просто ничего. Он не содержит никаких символов и не выполняет никакого действия. Рассмотрим пример программы состоящей из одного пустого оператора:

    Пример 

         Begin
      End

    Эта программа начинается и сразу же заканчивается, не выполняя никаких содержательных действий. Рассмотрим другой пример:

    Пример 

        Begin
      ; ; ;
      End

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

  • §1. Алфавит языка Pascal

    Изучение любого нового языка всегда начинается с алфавита. В алфавит языка Pascal входят следующие элементы:     

    1) Заглавные и строчные латинские буквы, символ подчёркивания (по грамматике языка символ подчёркивания считается буквой): _, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z.

    2) Цифры: `1, 2, 3, 4, 5, 6, 7, 8, 9, 0`.

    3) Знаки операций: + (плюс), (минус), * (умножить), / (разделить), < (меньше), > (больше), <= (меньше или равно), > = (больше или равно), = (равно), <> (не равно). Последний знак состоит из знаков «меньше» и «больше», записанных без пробелов.

    4) Знаки пунктуации, специальные символы:


     { } или (* *) Скобки комментариев
    [] Выделение индексов массивов, элементов множеств
    '   ' Выделение символа или строковой константы
    (   ) Выделение выражений, списков параметров

    := 

    Знак оператора присваивания

    ; Разделение операторов и объявлений
    : Отделение переменной или константы от типа.
    Отделение метки от оператора

    =

    Отделение имени типа от описания типа.
    Отделение константы от её значения
    , Запятая для разделения элементов в списке
    .. Разделение границ диапазона
    . Конец программы, отделение целой части
    от дробной
    # Обозначение символа по его коду

    В таблице приведены не все знаки пунктуации, а лишь те, которые будут использоваться при дальнейшем изложении.

    5) Служебные зарезервированные слова.

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

    and, array, begin, case, const, div, do, downto, end, for, if, mod, not, of, or, program, repeat, string, then, to, type, until, var, while, xor.

  • § 13. Пример задачи на сочетание оператора цикла и условного оператора
    задача 4

    Требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.

    Решение

    Одним из простейших алгоритмов нахождения наибольшего общего делителя является Алгоритм Евклида. Идея этого алгоритма основана на том свойстве, что если `M>N`, то  `"НОД"(M, N)="НОД"(M-N, N)`.

    Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.

    var M, N: integer;
    begin
         writeln('Введите М и N');
         readln(M, N);
         while M<>N do
              begin
                   if M>N
                   then M:=M-N
                   else N:=N-M
         end;
         write('Н0Д=',М)
    end.


  • § 1. Введение в алгебру логики

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

    Термин «дискретный» в русском языке имеет следующие значения:

    1) Состоящий из отдельных частей.

    2) Изменяющийся между несколькими стабильными состояниями.

    3) Существующий лишь в отдельных точках.

    Для того, чтобы лучше понять этот термин, рассмотрим следующий пример. Мы знаем, что график некоторой функции (например, `y=x^2`)  является непрерывной линией (параболой), если аргумент функции принимает все значения из множества действительных чисел. А теперь представим, что `x` может принимать только значения из множества целых чисел. В этом случае график будет представлять собой бесконечное количество отдельных точек, располагающихся на координатной плоскости в определённом порядке. В расположении точек будет угадываться парабола, но непрерывной линии мы не увидим. Вместо неё мы увидим дискретную структуру.

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

    Определение 1

    Высказывание – это повествовательное предложение, в отношении которого можно судить о его истинности либо ложности.

    Например, предложение: «Я – твой друг» является высказыванием, а предложение: «Положи это сюда!» высказыванием не является, поскольку не является повествовательным предложением.

    Истинность или ложность каждого высказывания зависит от трактовки его содержания. Например, высказывание: «Город Москва – столица России» является истинным, а высказывание: «Город Санкт-Петербург стоит на реке Лене» является ложным.

    Определение 2

    Высказывание называется простым, если никакая его часть сама по себе не является высказыванием.

    Высказывание: «Эта шляпа – красная» является простым, в то время как высказывание: «Если прямая пересекает одну из двух параллельных прямых, то она пересекает и вторую» является примером сложного высказывания, которое, по сути, состоит из трёх простых: «две прямые параллельны», «прямая пересекает одну из двух прямых», «прямая пересекает другую прямую». В сложном высказывании простые высказывания соединяются при помощи логических связок. В рассмотренном выше примере логической связкой является союз «если то».

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

    В прошлом задании при изучении основ программирования мы столкнулись с понятиями констант и переменных. Константа – это некоторое конкретное значение, а переменная – это объект, который может менять свои значения и которому можно присваивать различные значения. Этими же понятиями пользуется и алгебра логики, чтобы абстрагироваться от конкретных содержаний высказываний. Будем считать, что любое простое высказывание – это есть константа. И введём понятие переменной в алгебре логики.

    Определение 3

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

    В отличие от языков программирования в алгебре логики нет ограничений при именовании переменных. Переменные могут иметь абсолютно любые имена, но чаще всего их обозначают заглавными или строчными латинскими буквами (`A, B, C, x, y, z, s`), либо последовательностью, состоящей из заглавной или строчной латинской буквы и целого числа (`A1, A2, A4, A10000000`). Ещё одно отличие от языков программирования заключается в том, что после присвоения переменной высказывания можно говорить об её истинности либо ложности. То есть существует два понятия «значение логической переменной». С одной стороны – это конкретное высказывание, а с другой стороны – это истина, либо ложь.

    Определение 4

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

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

    Для того чтобы определить операцию, необходимо указать количество операндов (объектов, над которыми выполняется операция) их тип и результат выполнения операции. Логические операции чаще всего имеют два операнда, как и математические. Однако мы также будем изучать операции, которые имеют всего один операнд. Независимо от количества операнды должны быть логического типа, то есть иметь значение истина, либо ложь. Результатом логической операции также является логическое значение – истина или ложь. Для того чтобы немного сократить запись, условимся в дальнейшем логическое значение «истина» обозначать единичкой `(1)`, а логическое значение – «ложь» – нулём `(0)`.

    Очевидно, что если у операции два операнда, и значением каждого является `0` или `1`, то существует всего четыре набора значений операндов `(00, 01, 10, 11)`. Для каждого из наборов необходимо определить значение логической операции. Удобно это представлять в виде таблицы. Таблицы соответствия значений логических операций набору значений операндов называются таблицами истинности.

  • § 2. Логические операции. Формализация высказываний

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

    Названия операции

    Возможные обозначения

    Отрицание, инверсия.

    `-, ~|, not`

    Конъюнкция, логическое умножение, операция И, операция AND.

    `&, ^^, *,` по аналогии с алгебраическим умножением может никак не обозначаться

     

    Дизъюнкция, нестрогая дизъюнкция, логическое сложение, операция ИЛИ, операция OR.

    `|``, vv, +`

    Строгая дизъюнкция, разделительная дизъюнкция, исключающее ИЛИ, сложение по модулю `2`.

    `o+, Delta`

    Эквивалентность, эквиваленция, равенство, равнозначность.

    `iff, -=`

    Импликация, следование, следствие

    `=>, ->`


    Теперь для того чтобы строго определить эти логические операции, нам нужно для каждой из них выписать таблицу истинности. Все перечисленные операции кроме отрицания имеют два операнда. Знак операции в выражениях пишется между операндами (как в алгебре чисел). Операция отрицания имеет один операнд и в выражениях записывается либо в виде черты над операндом, либо в виде символа «приставка» слева от операнда.

    Для того, чтобы не путаться и гарантированно перебрать все возможные комбинации значений операндов, принято записывать их в лексикографическом порядке (условно считается, что «ложь» `<` «истина»).

    Таблица истинности для конъюнкции

    Первый операнд

    Второй операнд

    Значение операции

    `0`

    `0`

    `bb0`

    `0`

    `1`

    `bb0`

    `1`

    `0`

    `bb0`

    `1`

    `1`

    `bb1`

     

    Таблица истинности для дизъюнкции

    Первый операнд

    Второй операнд

    Значение операции

    `0`

    `0`

    `bb0`

    `0`

    `1`

    `bb1`

    `1`

    `0`

    `bb1`

    `1`

    `1`

    `bb1`

     

    Таблица истинности для строгой дизъюнкции

    Первый операнд

    Второй операнд

    Значение операции

    `0`

    `0`

    `bb0`

    `0`

    `1`

    `bb1`

    `1`

    `0`

    `bb1`

    `1`

    `1`

    `bb0`


    Таблица истинности для эквивалентности

    Первый операнд

    Второй операнд

    Значение операции

    `0`

    `0`

    `bb1`

    `0`

    `1`

    `bb0`

    `1`

    `0`

    `bb0`

    `1`

    `1`

    `bb1`

     

    Таблица истинности для импликации

    Первый операнд

    Второй операнд

    Значение операции

    `0`

    `0`

    `bb1`

    `0`

    `1`

    `bb1`

    `1`

    `0`

    `bb0`

    `1`

    `1`

    `bb1`

                     

    Таблица истинности для отрицания

    Значение операнда

    Значение операции

    `0`

    `bb1`

    `1`

    `bb0`

    Теперь осталось лишь установить соответствие между логическими операциями и логическими связками в русском языке.

    Логическая операция

    Логические связки в русском языке

    Отрицание

    Неверно что…

    Конъюнкция

    и, а, но,  а также, при этом,

    одновременно с этим, хотя

    Дизъюнкция

    Или

    Строгая дизъюнкция

    или, либо

    Эквивалентность

    Тогда и только тогда когда,

    необходимо и достаточно чтобы

    Импликация

    если то, необходимо чтобы, достаточно чтобы

    Обратите внимание, что союз ИЛИ может означать, как строгую, так и нестрогую дизъюнкцию. Его интерпретация зависит от содержания (!!!) высказывания.

    Пример 1

     Рассмотрим высказывание: «Мы идём в кино в субботу или в воскресение». Здесь два простых высказывания: «Мы идём в кино в субботу» и «Мы идём в кино в воскресение». Между ними стоит союз ИЛИ, который можно интерпретировать двояко. В данном случае очевидно, что мы можем пойти в кино и в субботу, и в воскресение, поэтому дизъюнкция будет нестрогая. Возьмём две логические переменные – `p` и `q` и присвоим им простые высказывания. Тогда исходное высказывание в формализованном виде будет выглядеть, как `bb(pvvq)`.

    Пример 2

    Рассмотрим высказывание: «Я сейчас на севере Москвы или на юго-западе Москвы». Здесь тоже два простых высказывания, которые связаны союзом ИЛИ. Но в этом случае союз ИЛИ интерпретируется, как строгая дизъюнкция, поскольку нельзя одновременно находиться в двух местах. Таким образом, если снова взять логические переменные `p` и `q`, то получится следующая логическая формула: `bb(p"o+q)`.


    Пример 3

    Рассмотрим высказывание: «Для того чтобы четырёхугольник был квадратом, необходимо, чтобы все его стороны были равны». Здесь два простых высказывания: «Четырёхугольник является квадратом» и «Все стороны четырёхугольника равны». Присвоим их соответственно логическим переменным `p` и `q`. Логическая связка «необходимо, чтобы» - это импликация. Весь вопрос в том, что из чего следует. (Какая запись правильная: `bbp -> bbq` или `bbq ->bbp`?)  Импликация ложна только в единственном случае: когда левый операнд имеет значение «истина», а правый – «ложь». Рассмотрим все возможные значения операндов и проанализируем, какая из ситуаций невозможна.

    1) `p` и `q` ложны. Это значит, что четырёхугольник не является квадратом и его стороны не равны. Это возможная ситуация.

    2) `p` – ложно, `q` – истинно. Это значит, что четырёхугольник не является квадратом, но стороны у него равны. Это возможно (ромб).

    3) `p` – истинно, `q` – истинно. Это значит, что четырёхугольник является квадратом и стороны у него равны. Это возможная ситуация.

    4) `p` – истинно, `q` – ложно. Это значит, что четырёхугольник является квадратом, но стороны у него не равны. Это невозможная ситуация.

    Анализ ситуаций показывает, что левым операндом импликации должна быть переменная `p`. Таким образом, в формализованном виде исходное высказывание выглядит как `bb(p -> q)`.

    Очень часто вместо «присвоим логическим переменным эти высказывания» говорят «обозначим высказывания следующим образом». В дальнейшем мы тоже будем использовать этот речевой оборот.

  • § 3. Законы алгебры логики

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

    Определение 5

    Логические выражения, зависящие от одних и тех же логических переменных, называются равносильными, если на любом наборе значений переменных они принимают одинаковое значение (`0` или `1`). В дальнейшем для обозначения равносильности логических выражений мы будем использовать знак равенства.<

    Законы алгебры логики

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

    1) Законы поглощения констант

      x `vv` 0 = x,  x & 1 = x;

     2) Законы поглощения переменных

      x `vv` 1 = 1,  x & 0 = 0;

     3) Законы идемпотентности

      x & x = х,  x `vv` x = х;

     4) Закон двойного отрицания

     $$ \stackrel{=}{\mathrm{x}}$$ = x;

     5) Закон противоречия

      x & $$ \stackrel{-}{\mathrm{x}}$$ = 0;

     6) Закон исключённого третьего

      x `vv` $$ \stackrel{-}{\mathrm{x}}$$ = 1;

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

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

    7) Законы коммутативности 

    x & y = y & x,

    x `vv` y = y `vv` x;

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

    8) Законы ассоциативности

      (x & y) & z = x & (y & z),

     (x`vv`y) `vv` z = x `vv` (y `vv` z);

    9) Законы дистрибутивности

      x & (y `vv` z) = (x & y) `vv` (x & z),
     x `vv` (y & z) = (x `vv` y) & (x `vv` z);

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

    Кроме аксиом и алгебраических свойств операций ещё существуют особые законы алгебры логики.

    особые законы алгебры логики.

    10) Законы де Моргана

    $$\style{font-family:'Courier New'}{\overline{\mathrm x\&\mathrm y}=\overline{\mathrm x}\vee\overline{\mathrm y},}$$

    $$\style{font-family:'Courier New'}{\overline{\mathrm x\vee\mathrm y}=\overline{\mathrm x}\;\&\;\overline{\mathrm y};}$$

    11) Загоны поглощения (не путать с аксиомами поглощения переменных нулём или единицей)

      x `vv` (x & y) = x;

      x & (x `vv` y) = x.

    Рассмотрим пример доказательства первого закона де Моргана при помощи построения таблицы истинности.

    `x`

    `Y`

    `x&y`

     `bar(x&y)`

    `barx` `bary`

    `barx vv bary`

    `0`

    `0`

    `0`

    `1`

    `1`

    `1`

    `1`

    `0`

    `1`

    `0`

    `1`

    `1`

    `0`

    `1`

    `1`

    `0`

    `0`

    `1`

    `0`

    `1`

    `1`

    `1`

    `1`

    `1`

    `0`

    `0`

    `0`

    `0`

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

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

    Наше начальное выражение: x `vv` (x & y). Выносим `x` за скобки и получаем следующее выражение:

    x &(1 `vv` y). Используем закон поглощения переменной константой `1` и получаем следующее выражение: x & 1. И теперь используем закон поглощения константы и получаем просто x.

    В заключение, следует сказать несколько слов об операции импликации. Как уже отмечалось выше, импликация не обладает свойством коммутативности. Её операнды неравноправны, поэтому каждый из них имеет уникальное название. Левый операнд импликации называется посылкой, а правый – следствием. Из таблицы истинности импликации следует, что она истинна, когда истинно следствие, либо ложна посылка. Единственный случай, когда импликация ложна – это случай истинной посылки и ложного следствия. Таким образом, мы подошли к последнему закону алгебры логики, который бывает полезен при упрощении выражений.

    12) Закон преобразования импликации

    `"x"  ->  "y" = bar("x")  vv  "y"`

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

    1) Отрицание

    2) Конъюнкция

    3) Дизъюнкция, строгая дизъюнкция, эквивалентность

    4) Импликация

  • § 4. Примеры задач на использование законов алгебры логики и формализацию высказываний
    Задача 1

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

    `bar C vv` (`A` & `С`) `vv`  (`bar(A vv C vv bar(B)`)

    Решение

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

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

    1) Избавиться от операций импликации.

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

    После пункта 2 наступает относительная свобода действий. Можно использовать тождества поглощения или раскрывать скобки.

    В нашей задаче операция импликации отсутствует, поэтому первый пункт мы пропускаем. Переходим к пункту 2. Применяем два раза второй закон де Моргана (для дизъюнкции) и закон двойного отрицания к правой скобке и получаем следующее логическое выражение:

      `bar C vv ` (`A`  &  `C`) `vv` (`bar A` & `bar C` & `B`)

    Если теперь внимательно посмотреть на выражение, то очевидно, что к первому и третьему слагаемому  можно применить первый закон поглощения, так как отрицание переменной `C` является первым слагаемым и входит в третье в качестве множителя.

    Поскольку дизъюнкцию ещё называют логическим сложением, её операнды называют слагаемыми, аналогично конъюнкция – это логическое умножение, и её операнды называют множителями.

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

    `bar C` `vv` (`A` & `C`)

    Применим второй (нестандартный для алгебры) закон дистрибутивности. Получаем: 

    (`bar C vv A`) & (`bar C vv C`)

    Ко второй скобке применяем закон исключённого третьего, превращаем её в единицу, а затем применяем закон поглощения константы `1` и в итоге получаем выражение: `bar C vv A`, которое упростить уже нельзя.

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

    Обратите внимание, что исходное логическое выражение зависело от трёх переменных (`A, B, C`) , в то время как упрощённое в итоге зависит от двух логических переменных (`A` и `C`). При этом выражения всё равно остаются равносильными! Это происходит потому, что в процессе упрощения применялись законы поглощения. Аналогичный результат мог бы получиться, если в процессе упрощения выражения используются законы поглощения переменных константами. Исчезновение переменной при упрощении означает, что в исходном выражении она является несущественной.

    Задача 2

    Укажите значения переменных `K`, `L`, `M`, `N`, при которых логическое выражение `(L vv M) ^^ (¬ K -> M) ^^ ¬ N ^^ ¬ M`  истинно.

    Решение

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

          `(L vv M) ^^ ( K vv M) ^^ ¬ N ^^ ¬ M`

    Отрицание вглубь продвигать не надо. Теперь раскроем скобки. Для упрощения условимся операцию конъюнкции никак не обозначать (по аналогии с алгеброй чисел).

         `(LK vv LM vv MK vv M) ( ¬ N) ( ¬ M)`

    В первой скобке можно применить тождество поглощения, и «съесть» второе и третье слагаемое, которые содержат M в качестве множителя. Получается такое выражение: 

         `(LK vv M) ( ¬ N) ( ¬ M)`

    Выполнив оставшиеся операции умножения, получим следующий результат:

        ` LK¬ N¬ M`

    Получили одну конъюнкцию. Следовательно, существует всего один набор значений переменных, при котором получится значение «1»:  `L=1`, `K=1`, `N=0`, `M=0`.


    Задача 3

    Сколько решений имеет уравнение:

         `(((K¬L¬N) (¬L -> M))` \/ `((¬K` \/ `L` \/ `N) (¬L¬M)))  (K`\/`N)=1`

    Решение

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

         `(((K¬L¬N) (L`\/ `M))` \/ `((¬K` \/ `L` \/ `N) (¬L¬M)))  (K`\/`N) = 1`

    Теперь раскроем скобки. Для упрощения условимся не записывать слагаемые, куда одновременно входят некоторая переменная и её отрицание (они всё равно равны нулю):

         `(K¬L¬NM` \/ `¬K¬L¬M` \/ `N¬L¬M)  (K`\/`N) = 1`

    Продолжаем раскрытие скобок. Получаем:

         `K¬L¬NM` \/ `¬K¬L¬MN` \/ `KN¬L¬M` \/ `N¬L¬M  = 1`

    Ко второму, третьему и четвёртому слагаемому можно применить тождество поглощения. В итоге получится:

         `K¬L¬NM` \/ `N¬L¬M  = 1`

    На этом упрощение закончено, теперь будем анализировать. Дизъюнкция равна единице, если хотя бы одно из слагаемых равно единице. Первое слагаемое равно единице на единственном наборе переменных: (`K=1`, `L=0`, `N=0`, `M=1`). Второе слагаемое равно единице на двух наборах: (`N=1`, `L=0`, `M=0`, `K` – любое (или `0` или `1`)). Соответственно, уравнение имеет три различных решения.

    Задача 4

    В нарушении правил обмена валюты подозреваются четыре работника банка - Антипов    (`A`), Борисов (`B`), Цветков (`C`) и Дмитриев (`D`). Известно, что:

    1) Если `А` нарушил, то и `В` нарушил правила обмена валюты.

    2) Если `B` нарушил, то и `C` нарушил или `A` не нарушал.

    3) Если `D` не нарушил, то `A` нарушил, а `C` не нарушал.

    4) Если `D` нарушил, то и `A` нарушил.

    Кто из подозреваемых нарушил правила обмена валюты?

    Решение

    Чтобы решить эту задачу, необходимо провести процесс формализации условия, сформировать единое логическое выражение и провести его упрощение. Выделим из условия четыре простых высказывания: «`A` нарушил правила», «`B` нарушил правила», «`C` нарушил правила»,  и «`D` нарушил правила». Обозначим их соответственно буквами `A`, `B`, `C`, `D`. Тогда высказывания из условия формализуются следующим образом (конъюнкция не обозначается никак):

    1) `A -> B`;

    2) `B -> C` \/ `¬A`;

    3) `¬D -> A¬ C`;

    4) `D -> A`.

    Нам известно, что выполняются все 4 высказывания, следовательно, нужно объединить их знаками конъюнкции и найти наборы, при которых получившееся общее высказывание будет истинным. Эти наборы и покажут нам, какие возможны ситуации (правила обмена нарушил тот, у кого переменная в итоговом наборе имеет значение «1»).

    Итак, строим логическое выражение:

          `(A -> B)( B -> C` \/ `¬A)( ¬D -> A¬C)( D -> A)`.

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

         `(¬A` \/ `B)( ¬B` \/ `C` \/ `¬A)( D` \/  `A¬C)( ¬D` \/  `A)`.

    Раскрываем скобки. Первую перемножаем со второй, а третью с четвёртой.

         `(¬A¬B`  \/ `¬AC` \/ `¬A` \/ `BC` \/ `B¬A) ( DA` \/ `A¬C¬D` \/  `A¬C)`.

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

         `( ¬A` \/ `BC ) ( DA` \/ `A¬C)`.

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

    Ответ

    Правила обмена валюты нарушили все.

    Задача 5

    Известно, что обе надписи на дверях либо истинны, либо ложны одновременно. Надпись на первой двери – "Клад за другой дверью", на второй двери – "Клада за этой дверью нет, а за другой  – есть". Где находится клад?

    Решение

    По сути нас интересуют два простых высказывания: «Клад есть за первой дверью» и «Клад есть за второй дверью». Обозначим первое из них буквой `A`, а второе буквой `B`. Тогда изначальные предположения формализуются следующим образом: 

    1) `B`;

    2)  `¬BA`.

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

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

         `¬B ¬(¬BA)`.

    Упрощаем его по алгоритму: отрицание продвигаем вглубь, применяя тождество Де Моргана. Получаем:

         `¬B (B` \/ `¬A)`.

    Раскроем скобки. Первое слагаемое сокращается, а второе выглядит следующим образом: `¬B¬A`.

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

    Ответ

    Клада нет ни за одной дверью.

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

    схема решения текстовых логических задач

    1) Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.

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

    3) Составить единое логическое выражение для всех требований задачи (возможно не одно).

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

    5)  Выбрать решение — набор значений простых высказываний, при котором построенное логическое выражение является истинным;

    6) Проверить, удовлетворяет ли полученное решение условию задачи.

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

    задача 6

    Найдите количество решений системы уравнений:

    `(x2-=x1)+x2&x3+ not x2& not x3=1`

    `(x3-=x1)+x3&x4+ not x3& not x4=1`

    `…`

    `(x9-=x1)+x9 & x10+ not x9 & not x10=1`

    `(x10 & x1)=0`

    где `x1 … x10` - неизвестные логические величины

    Решение

    Упростим исходные уравнения, заметив, что, `(x2&x3+ not x2& notx3=(x2-=x3)`. Исходную систему запишем в виде:

    `(x2-=x1)+(x2-=x3)=1`

    `(x3-=x1)+(x3-=x4)=1`

    `…`

    `(x9-=x1)+(x9-=x10)=1`

    `(x10&x1)=0`

    В первом уравнении используются три переменных `x1`, `x2` и `x3`. Значения `x1` и `x2` могут быть выбраны произвольно четырьмя способами:

    `bb(x1)`

    `bb(x2)`

    `bb(x3)`

    `0`

    `0`

    `0`

    `0`

    `0`

    `1`

    `0`

    `1`

    `1`

    `1`

    `0`

    `0`

    `1`

    `1`

    `0`

    `1`

    `1`

    `1`

    Если `x2=x1`, то значение `x3` может быть любое (эти строки выделены серым цветом), а при `x2!=x1` получаем только один вариант: `x3=x2`.

    Таким образом, при подключении первого уравнения число решений увеличивается на количество строк в таблице, для которых значения `x1` и `x2` (последней рассмотренной переменной) равны. В данном случае таких строк две, получаем 6 решений. Более того, в новой таблице снова осталось всего две строки (верхняя и нижняя), где `x3=x1`. Как следует из второго уравнения, именно эти (и только эти) строки на следующем шаге “раздваиваются”, дают по два решения. Таким образом, при подключении к системе очередного уравнения число решений увеличивается на `2`. Для двух уравнений получим 8 решений, для трёх - 10, а для восьми - 20 решений.

    Остается учесть последнее (особое) уравнение, `(x10-=x1)=0`. Это означает, что `x10!=1`. Из анализа таблицы видно, что есть всего две строки (верхняя и нижняя), где первая и последняя переменные равны. Поэтому из полученных 20 решений нужно отбросить эти два, не удовлетворяющие последнему уравнению. В итоге исходная система имеет 18 решений.

    ответ
    Система имеет 18 решений.
    задача 7

    Найдите количество решений системы уравнений:

    `not x1+x2=1`

    `not x2+x3=1`

    `…`

    `not x9+x10=1`

    где `x1 … x10` - неизвестные логические величины

    Решение
    Здесь `10` переменных, поэтому при решении системы через таблицу истинности нужно заполнить `2^(10)=1024` строки, поэтому перебор всех возможных вариантов является не эффективным способом решения. Поскольку все правые части равны `1`, можно легко свести систему к одному уравнению:

    `(not x1 + x2)&( not x2 + x3) &…&(not x9 + x10)=1`

    однако это не упрощает решения.

    Можно заметить, что первое уравнение зависит только от `x1` и `x2`, а каждое новое уравнение добавляет по одной новой переменной. Поэтому можно решать систему последовательно с помощью построения таблицы. Первое уравнение, `not x1+x2=1`, обращается в истинное равенство в трех случаях:

    `bb(x1)` `bb(x2)`
    `0` `0`
    `0` `1`
    `1` `1`

    Подключив второе уравнение, `not x2+x3=1`, заметим, что допустимые значения `x3` зависят от ранее выбранного значения `x2`: если `x2=0`, то `x3` может принимать любое значение  (`0` или `1`),  а  если `x2=1`, то `x3=1`. Соответствующая таблица выглядят так:

     

    `bb(x1)`

    `bb(x2)`

    `bb(x3)`

    `0`

    `0`

    `0`

    `1`

    `0`

    `1`

    `1`

    `1`

    `1`

    `1`

     

    Легко заметить, что при добавлении очередного уравнения верхняя строка таблицы дает два решения (они выделены серы м цветом), а остальные строки - по одному. Поэтому количество решений увеличивается на `1`. Таким образом, система из трёх уравнений имеет 5 решений, из четырех - 6, а исходная система из девяти уравнений - 11 решений.

    ответ

    11 решений.

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

  • § 5. Логический тип данных в языке программирования Паскаль

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

    В прошлом задании мы работали с числовыми типами переменных и учили арифметику, теперь познакомимся с логическим типом переменных, который называется Boolean. Переменные этого типа имеют всего два значения – true и false (соответственно, «истина» и «ложь»). Подобно числовым переменным им можно присваивать значения при помощи оператора присваивания. При этом необходимо строго соблюдать правило совместимости типов. То есть логическим переменным нельзя присваивать числовые значения, а числовым – логические.

    В языке Паскаль помимо арифметических операций ещё существует `6` операций сравнения: больше» `(>)`, «больше или равно» `(> =)`, «меньше» `(<)`, «меньше или равно» `(< =)`, «равно» `(=)`, и «не равно» `(<>)`. Операция «не равно» записывается, как последовательность знаков «меньше» и «больше».  Результатом каждой из этих операций является логическое значение true или false. Например, операция `5 > 2` выдаст значение true, а операция `x<>3` выдаст значение true, если переменная `X` имеет любое значение, кроме `3`. Сравнивать можно не только числа (причём как целые, так и вещественные), но и логические значения. При этом считается, что значение true больше, чем значение false. При сравнении обязательно соблюдать правило совместимости типов, то есть можно сравнивать числа между собой (причём в отличие от оператора присваивания, здесь никаких ограничений нет). Можно сравнивать между собой логические значения. Но нельзя сравнивать логическое значение с числом любого типа.

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

    1) Операция AND (в алгебре логики – «конъюнкция»)

    2) Операция OR (в алгебре логики – «дизъюнкция»)

    3) Операция XOR (в алгебре логики – «строгая дизъюнкция»)

    4) Операция NOT (в алгебре логики – «отрицание»)

    Все операнды этих операций должны быть логического типа, а никак не числового. Причём, операции AND, OR и XOR имеют по `2` операнда, а операция NOT – один операнд, который записывается справа от названия операции (аналогично обозначению операции NOT при помощи `¬` в алгебре логики)

    Теперь у нас есть достаточно много операций и нужно расставить их по приоритету выполнения. В Паскале есть четыре приоритета операций:

    1) Операция not;

    2) Операции группы умножения: *, /, div, mod, and;

    3) Операции группы сложения: +, – , or, xor;

    4) Операции группы сравнения: >, <, <=, >=, =, <>.

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

    Теперь рассмотрим несколько примеров задач на использование логического типа.

    Общая Задача

    Записать на Паскале логическое выражение истинное при выполнении указанного условия и ложное в противном случае. Результат вычисления данного выражения присвоить переменной F.

    Условие 1

    Числовая  переменная  X  имеет  значение  на  отрезке [–1,1].

    Решение

     F:=abs(X)<=1;

    Условие 2

    Числовая переменная X имеет значение на отрезке [2,7].

    Решение

    F:=(X>=2)and(X<=7).

    Обратите внимание на скобки. Они обязательны, поскольку операции сравнения имеют более низкий приоритет, чем операция and.

    Условие 3

    Числовая переменная X имеет значение на одном из 2 отрезков: [–10, 3] или [10, 20].

    Решение

    F:=(X>=-10)and(X<=3)or(X>=10)and(X<=20).

    Условие 4

    Логические переменные A и B имеют различные значения.

    Решение

    F:=A<>B.

    Условие 5

    По крайней мере 2 из логических переменных A, B и C имеют значение true.

    Решение

    F:=A and B or A and C or B and C.



    :

       

  • §1. Логический тип переменных. Логические выражения

    В прошлом задании мы работали с числовыми типами переменных и учили арифметику, теперь познакомимся с логическим типом переменных, который называется Boolean. Переменные этого типа имеют всего два значения - true и false (соответственно, «истина» и «ложь»). Подобно числовым переменным им можно присваивать значения при помощи оператора присваивания. При этом необходимо строго соблюдать правило совместимости типов. То есть, логическим переменным нельзя присваивать числовые значения, а числовым - логические. Так же можно выводить значения логических переменных на экран, а вот вводить их с клавиатуры нельзя! 

    В языке Pascal определены `6` операций сравнения, результатом которых является логическое значение:

    1) «больше» (>)

    2) «больше или равно» (>=)

    3) «меньше» (<)

    4) «меньше или равно» (<=)

    5) «равно» (=)

    6) «не равно» (<>).

    Например, операция `5>2` всегда выдаст значение true, а операция `x<>3` выдаст значение true, если переменная `x` имеет любое значение, кроме `3`.

    Сравнивать можно не только числа (причём как целые, так и вещественные), но и логические значения. При этом считается, что значение true больше, чем значение false.

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

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

    1) and (конъюнкция, логическое умножение, операция «И»)

    2) or (дизъюнкция, логическое сложение, операция «ИЛИ»)

    3) not (отрицание, инверсия)

    4) 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), которая применяется к целочисленному аргументу х:

    odd(x) = true, если `x` нечётно;

    odd(x) = false, если `x` чётно.

    Приоритет операций в сложном выражении (содержащем в себе все виды операций, изученных нами) следующий:

    1) Операция not.

    2) Операции группы умножения and, *, /, div, mod

    3) Операции группы сложения or, xor, +, -

    4) Операции сравнения >, <, >=, <=, =, <>

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

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

    Пример 1

    Целое число `n` делится на `13`.

    Решение

    n mod 13 = 0

    Надо проверять, что остаток от деления на `13` является нулём. 

    Пример 2

    Целое число `n` делится на `13` и `7`.

    Решение

    (n mod 13 = 0) and (n mod 7 = 0)

    Здесь надо проверить одновременное выполнение двух условий.

    Пример 3

    Переменная `x` имеет значение из отрезков `[2,5]` или `[-1,1]`.

    Решение

    (x>=2) and (x<=5) or (abs(x)<=1)

    Пример 4

    Из чисел `x`, `y`, `z` хотя бы два равны между собой.

    Решение

    (x = y) or (x = z) or (y = z)

    Пример 5

    Числа `x`, `y`, `z` равны между собой.

    Решение

    (x = y) and (x = z)

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

  • §2. Условный оператор

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

    Пример задачи

    Ввести номер года. Вывести слово 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` и `с`, и если значение `a` - больше, поменяем их местами. После этих двух сравнений в переменной `a` гарантированно окажется наименьшее из трёх чисел. Осталось сравнить переменные `b` и `c`, и в случае, когда в переменной `b` находится большее значение, поменять их местами.

    Очевидно, что в этом алгоритме у нас три сравнения, следовательно, три последовательных условных оператора. При этом в каждом из них какие-то действия (поменять местами значения двух переменных) нужно выполнять только в ветке then, в ветке else (например, если в первом сравнении в переменной a находится уже более маленькое число, чем в переменной `b`) никаких действий выполнять не нужно. Рассмортим код программы: В этом случае, грамматика языка программирования позволяет вообще не записывать даже слово else. Такая конструкция называется сокращённой формой условного оператора.

    var a,b,c,x:integer;

    begin

      writeln('введите три целых числа ');

      readln(a,b,c);

      if a>b then begin x:=a; a:=b; b:=x end;

      if a>c then begin x:=a; a:=c; c:=x end;

      if b>c then begin x:=b; b:=c; c:=x end;

      writeln(a,b,c);

      readln

    end.

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

    Использование сокращённой формы условного оператора порождает проблему неоднозначности интерпретации логики действий программы в случае вложенных условных операторов. Рассмотрим следующий пример:

    if x>0

     then if y>0

       then z:=0

     else c:=7;

    Вопрос состоит в том, какой из двух условных операторов является полным, а какой - сокращённым. К сожалению, ответ на этот вопрос существует только в виде дополнительного семантического правила языка программирования. Принято, что ветка else всегда относится к ближайшему if без else (по принципу правильной скобочной системы). То есть, в нашем случае внутренний условный оператор является полным, а внешний - сокращённым. Если же мы хотим добиться обратной логики действий (чтобы внешний условный оператор был полным), нам необходимо заключить внутренний условный оператор в операторные скобки. Выглядеть это будет следующим образом:

    if x>0

     then begin

      if y>0

       then z:=0

      end

     else c:=7;

        

        

         

        

  • §3. Разбор случаев

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

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

    Для того, чтобы не упустить из рассмотрения никаких случаев и не рассматривать несущественные случаи, нужно перебирать их не в случайном порядке, а по какой-либо стратегии. Сейчас мы рассмотрим одну из стратегий разбора случаев, которую условно можно назвать «Естественное возникновение». Её суть заключается в следующем: Изначально, мы решаем задачу так, будто бы никакого деления на случаи нет, а появляется оно лишь тогда, когда выполнить основной сценарий невозможно.

    Рассмотрим  следующий  пример  задачи:

    Пример задачи

    Решить  в  целых  числах линейное уравнение `ax=b`.

    Решение

    На вход программе здесь будут подаваться коэффициенты уравнения, а программа должна будет либо вычислить корень, либо вывести сообщение об особой ситуации (нет корней, бесконечно много корней и т. д.). Будем разбирать случаи согласно нашей стратегии. Сначала посмотрим, как мы в принципе решаем подобное уравнение. Для нахождения значения `x` нужно коэффициент `b` разделить на коэффициент `a`. Очевидно, что это невозможно сделать, если `a=0`. Поэтому первая проверка, которая делит всё множество случаев на две принципиально разные ветки: верно ли, что `a=0`? Если это так, то у нас получается уравнение `0x=b`, существование решений которого зависит от значения `b`. Если `b=0`, то решений бесконечно много, если же это не так, то решений нет вообще. Вернёмся к проверке коэффициента `a`. Если он не равен нулю, то это означает, что уравнение имеет единственное решение. Вопрос теперь в том, целое оно или нет. Поэтому здесь нужно будет проверить, что `b` нацело делится на `a` (остаток от деления должен быть равен нулю). Если это так, то находится единственное решение, если же нет, то целых решений у уравнения нет. Запишем теперь все наши рассуждения в виде программы:

    var a,b:integer;

    begin

     readln(a,b);

     if a=0

      then if b=0

       then writeln('many solutions')

       else writeln('no solution')  

      else if b mod a = 0

       then writeln( b div a)

       else writeln('no solution')

    end.

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

    Теперь вам будут предложены контрольные вопросы и задачи. За каждый правильный ответ будут ставиться баллы. Максимальное количество баллов за задание указано в скобках после его номера. Если задание стоит более одного балла, то возможно получить частичный балл за частично верное решение. Имейте в виду, что более объёмные и сложные задания стоят дороже. Итоговая оценка будет определяться по сумме набранных баллов. Желаем успеха!      

  • §1. Алгоритмическая конструкция «Цикл». Операторы цикла While и Repeat

    1.1 Алгоритмическая конструкция «Цикл»

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

    Очевидно, что для решения этой задачи нам придётся `100` раз выполнять команду вывода соответствующего числа на экран. Писать `100` операторов вывода как-то не хочется (слишком трудоёмко),  поэтому будем знакомиться с алгоритмической конструкцией, которая называется «цикл».

    Циклом

    называется повторение фрагмента алгоритма несколько раз с возвратом в более раннюю точку исполнения алгоритма. Повторяемый при этом фрагмент алгоритма называется телом цикла.

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

    В зависимости от положения точки ветвления выделяются циклы с предусловием (точка ветвления располагается перед телом цикла) и с постусловием (точка ветвления располагается после тела цикла).

    1.2. Оператор while

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

    Первый оператор цикла называется While и реализует алгоритмическую конструкцию с предусловием. В общем виде он записывается следующим образом:

    while условие do оператор

    Слова while и do являются служебными зарезервированными словами языка. Под условием (аналогично оператору if) понимается выражение, результат вычисления которого имеет тип boolean. Работает этот оператор следующим образом. Сначала вычисляется условие. Если в результате получилось true, то мы заходим в цикл, то есть выполняем тело цикла и возвращаемся вновь к вычислению условия. Если же получилось false, то происходит переход к следующему оператору в программы, и входа в цикл не будет. Фактически оператор while является многократным применением оператора if с пустой веткой else. Аналогично оператору if, тело цикла должно состоять из `1` оператора. Если нужно исполнить несколько, то следует использовать операторные скобки (begin end).

    Возможна ситуация, когда цикл будет выполняться бесконечное количество раз (зациклится). Например, while 2*2=4 do… Что написать после do, совершенно не важно, важно, что оно будет выполняться, пока 2*2=4, а это всегда так, и никогда не изменится. Значит, чтобы избегать зацикливания, параметры условия должны быть переменными, например while x*x=4 do … Хотя это тоже не гарантирует отсутствие зацикливания. Поэтому при написании программ нужно всегда внимательно следить за тем, какие условия мы пишем в операторе цикла, чтобы не случилось ситуации зацикливания.

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

    1.3. Примеры задач

    Рассмотрим несколько примеров задач на оператор цикла.

    Задача 1

    Дано целое число, не меньшее `2`. Выведите его наименьший натуральный делитель, отличный от `1`.

    Решение

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

    var i,n:integer;

    begin

      readln(n);

      i:=2; 

      while n mod i <> 0 do

        i:=i+1;

      end;

      writeln (i);

    end.

    Задача 2

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

    Решение

    В этой задаче нам нужно реализовать постепенное увеличение пробега. То есть, на каждом шаге цикла мы будем сохранять значение пробега в соответствующий день в одной переменной, а номер этого дня – в другой. Завершение, когда значение первой переменной станет не меньшим чем `y`. Приведём код программы. Все переменные, отвечающие за километры, имеют  тип real (из условия).

    var x,y:real; i:integer;

    begin

      readln(x,y);

      i:=1;

      while x<y do begin

        x:=x/100*10+x;

        i:=i+1;

      end;

      writeln(i);

    end.

    Задача 3

    Дано натуральное число `N`. Вычислите его сумму цифр.

    Решение

    Для решения этой задачи на каждом шаге цикла нужно изменять наше число: при помощи операции mod можно выделить последнюю цифру из числа и прибавить её к сумме, а затем её надо выбросить из числа при помощи операции div. Делить нужно, естественно, на `10`. Критерий завершения – когда число станет равным нулю, ибо это будет означать, что мы уже рассмотрели все цифры и поделили на `10` однозначное число (по свойствам операции целочисленного деления известно, что при делении меньшего числа на большее получается ноль). Приведём код программы.

    var a,n,s:integer;

    begin

      readln(n);

      s:=0;

      while n>0 do begin

        a:=n mod 10;

        s:=s+a;

        n:=n div 10;

      end;

      writeln(s);

    end.

    Задача 4

    Ввести целое число `n`. Вывести `"YES"`, если оно простое, и `"NO"`, если оно составное.

    Решение

    Эта задача демонстрирует сразу две важные вещи. Во-первых, как проверять делимость целых чисел, а во-вторых, технику флажков. Флажком называется переменная, которая имеет некоторое начальное значение и меняет его, если происходит определённое событие. Как правило, флажок имеет тип boolean.

    В нашей задаче мы будем перебирать числа от `2` до квадратного корня из `n` и проверять, делится ли `n` на каждое из них. Изначально предположим, что `n` - простое, и присвоим флажку значение true, но если `n` поделится на какое-нибудь число, это будет значить, что оно составное, и, соответственно, флажок «упадёт» на значение false. Проверять на делимость нужно, сравнивая остаток от деления с нулём.

    var n,i:integer;

            f:boolean;

     begin

      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');

    end.

    1.4  Оператор repeat

    Теперь познакомимся с другим оператором цикла, который реализует алгоритмическую конструкцию цикла с постусловием. Рассмотрим его синтаксис.

    repeat

      Оператор 1;

      Оператор 2;

    ….

      Оператор N

    until условие

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

    1) выполняется тело цикла;

    2) вычисляется значение условия. Если получилось true, то выход из цикла и переход к следующему оператору программы, в противном случае переход к пункту 1.

    Отличительная особенность оператора цикла repeat заключается в том, что тело  всегда выполняется, по крайней мере, один раз. Это нужно учитывать в задачах при выборе оператора цикла. Аналогично оператору while, цикл repeat может зациклиться, правда в случае, когда условие никогда не принимает значение true, например,  repeat…until 2*2=5.

  • §2. Оператор цикла 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,' ');

    end.

    Согласитесь, что решение фактически в одну строчку выглядит гораздо приятнее, чем в `100` строк (если не пользоваться оператором цикла).

    Необходимо сделать несколько замечаний по поводу цикла for.

    замечания

    1) Типы счётчика начального и конечного значений должны совпадать, при этом в настоящий момент из известных нам типов можно использовать только integer и boolean. Вещественный тип использовать нельзя.

    2) Начальное и конечное значения вычисляются один раз до начала цикла (и после не перевычисляются). Рассмотрим пример.

    i:=1; for i:=i to i do writeln('HI');

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

    3)  В теле цикла значение счётчика изменять нельзя. Так прописано в стандарте языка Pascal, и это требование поддерживается в системах семейства Delphi и PascalABC. Однако в системах семейства Borland Pascal значение счётчика изменять можно, что может приводить к непредсказуемым последствиям (поэтому будем считать, что независимо от системы значение счётчика изменять нельзя).

    4)  После завершения цикла значение счётчика не определено, то есть нельзя считать, что оно равно конечному значению или больше на единицу и пользоваться этим в дальнейшем алгоритме.

    5) Тело цикла по грамматике должно состоять только из `1` оператора. Если же там по алгоритму должно быть несколько, нужно использовать составной оператор. В этом смысле оператор for солидарен с операторами if и while.

    6) Можно слово to заменить на слово downto. В этом случае значение счётчика после каждого выполнения тела цикла будет уменьшаться на `1`, а выход из цикла произойдёт, когда значение счётчика окажется меньше, чем конечное.

    Выполнение любого оператора цикла можно завершить досрочно, если использовать процедуру break. На данном этапе она особенно актуальна, если надо досрочно прервать цикл for. Выполнение этой процедуры передаст управление на оператор, который следует за прерываемым оператором цикла.

    Проиллюстрируем её работу следующим примером:

    вводится натуральное число `x` `(2 <= x <= 30000)`. Выведите наименьший делитель числа `x`, отличный от `1`.

    Мы уже разбирали алгоритм решения этой задачи выше. Продемонстрируем его с использованием цикла for.

    var a,i: integer;

    begin

      readln(a);

      for i := 2 to a do

        if a mod i = 0 then

        begin

          writeln(i);

          break;

        end;

    end.



  • §3. Класс задач «Обработка последовательностей»

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

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

    Рассмотрим стандартные шаблоны решения задач данного класса:

    шаблон Тип 1:

     Количество элементов в последовательности известно заранее (`N`).

            readln(N);

         for j:=1 to N do begin

           read(a);

          {Содержательна обработка}

         end;

    Обращаем внимание, что внутрь оператора цикла обязательно помещается оператор read, а не readln. Дело в том, что, как правило, числа будут вводиться в строчку и оператор ввода будет на каждом шаге забирать из буфера по `1` числу. Оператор  readln при этом ещё удаляет из буфера всё лишнее до конца строки, поэтому числа прочитаны не будут. Количество элементов последовательности, как правило, задаётся отдельным числом в первой строке, поэтому его логичнее читать оператором readln.

    Рассмотрим примеры задач данного класса.

    Задача 1

    Вводится натуральное число `N`, а затем `N` натуральных чисел, сумму которых необходимо вычислить.

    Решение

    var i,N,a,s:integer;

    begin

      readln(N);

           s:=0;

      for i:=1 to N do begin

             read(a);

        s:=s+a;

           end;

      writeln(s)

    end.

    Задача 2

    Вводится натуральное число `N`, а затем `N` целых чисел. Выведите `"YES"`, если среди введенных чисел есть хотя бы один ноль, или `"NO"` в противном случае.

    Решение

    var n,i,k,a,s:integer;

    begin

      s:=0;

      readln(n);

      for i:=1 to n do begin

        read(a);

        if a=0 then k:=k+1;

      end;

    if k<>0

      then writeln('YES')

      else writeln('NO')

    end.

    Теперь рассмотрим второй тип задач из класса «Обработка последовательностей», когда количество элементов неизвестно заранее, но известен признак конца.

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

    1) Считывание

    2) Проверка на признак конца

    3) Содержательная обработка

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

    Шаблон для типа 2:

      read(a);

         while a<>0 do begin

           {содержательная обработка};

           read(a)

         end;         

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

    Задача 3

    Программа получает на вход последовательность целых неотрицательных чисел. Ноль - признак конца. Вывести количество членов последовательности (не считая завершающего числа `0`).

    Решение

    var a,k:integer;

    begin

      read(a);

      k:=0;

      while a<>0 do begin

        k:=k+1;

        read(a);

      end;

      writeln(k);

    end.

    Задача 4

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

    Решение

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

    var a,pr,k:integer;

    begin

      read(a);

      pr:=a;

      k:=0;

      while a<>0 do begin

        if (a > pr) then k:=k+1;

        pr:=a;

        read(a);

      end;

      writeln(k);

    end.

    Задача 5

    Вводится последовательность натуральных чисел. Ноль - признак конца. Вывести значение максимального элемента.

    Решение

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

    var a,m:integer;

    begin

      read(a);

      m:=a;

      while a<>0 do begin

        if (a > m) then m:=a;

        read(a);

      end;

      writeln(m);

    end.

    При решении этой задачи ещё остался вопрос корректной инициализации. В общем случае есть два способа.

    Первый вариант - в качестве начального значения максимума брать «минус бесконечность» (для минимума - плюс бесконечность). Под «минус бесконечностью» в данном случае понимается некое число, которое гарантированно меньше чем любой элемент, который может нам встретиться. Инициализация бесконечностью допустима, если мы заранее знаем диапазон элементов последовательности. Это её недостаток, зато она пишется в один оператор присваивания.

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

    Задача 6

    Найти максимальный чётный элемент последовательности в предположении, что он существует.

    Решение

    var a,m:integer;

    begin

      read(a);

      while (a<>0)and(a mod 2 <> 0) do read(a);

      m:=a;

      while a<>0 do begin

        if (a mod 2 = 0)and(a>m) then m:=a;

        read(a);

      end;

      writeln(m);

    end.



  • Введение

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

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

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

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

    На первом году обучения теоретических заданий не будет, а основная масса будет посвящена программистской части курса. Основная цель первого года обучения – овладеть языком программирования как инструментом для дальнейшего использования. В качестве учебного языка программирования мы выберем язык Pascal. Тому есть несколько причин. Во-первых, этот язык изначально создавался для обучения программированию, и в нём нет большого количества сложных тонкостей, для понимания которых требуются глубокие специальные знания (как, например, в языках C/C++). Во-вторых, концептуально Pascal является каноническим языком процедурной парадигмы программирования, и после него можно очень легко переходить на любые другие языки.

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

    Для выполнения заданий программистской части курса вам будет необходимо установить себе среду программирования, либо воспользоваться online-компилятором. Имейте в виду, что даже для языка Pascal различные среды программирования могут серьёзно различаться (например,  free pascal и Pascal ABC.NET). Мы будем обращать внимание на данные различия по ходу изложения материала.

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

  • §12. Примеры задач на операторы цикла
    задача 1

    Ввести значения $$ 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` членов геометрической прогрессии, но наша цель не решить конкретную задачу, а понять принцип накапливания (суммы). Ибо далеко не любая последовательность чисел является геометрической или арифметической прогрессией.

    задача 2

    Вводится последовательность натуральных чисел. Признак конца ввода – число `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, то набивать значения придётся в столбик, что неудобно. Ещё одно важное замечание в этой задаче – оператор ввода внутри цикла должен быть последним, чтобы сразу попадать на проверку признака конца. Эти замечания относятся ко ВСЕМ задачам на обработку последовательностей с признаком конца.

    задача 3

    Ввести целое число `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. 

  • §11. Операторы цикла

    Зачастую в задаче нужно повторять одни и те же действия много раз. Повтор некоторого фрагмента программы несколько раз называется циклом. Рассмотрим следующий пример.

    Пример 9

    Вывести на экран квадраты чисел от `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.

        

  • §10. Условный оператор

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

    Пример 7

    Ввести номер года. Вывести слово 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 в качестве оператора может стоять и пустой оператор.

    Рассмотрим следующий пример.

    Пример 8

    Вводятся `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.


      

        

  • §9. Логический тип переменных

    В языке 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) Операции сравнения >, <, >=, <=, =, <>

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

    Пример 6

    Записать логическое выражение, истинное в случае, когда переменная `X` имеет значение из отрезков `[2,5]` или `[-1,1]`.

    Решение

    (X>=2) AND (X<=5) OR (abs(X)<=1).


         

  • §8. Примеры простейших программ

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

    Пример 3

    Ввести координаты трёх вершин треугольника. Вывести его площадь. Гарантируется, что треугольник существует (ввод корректный).

    Решение

    Для решения этой задачи нам потребуется `6` переменных, в которые будут введены значения координат `(x1, y1, x2, y2, x3, y3)`. Можно сделать их целыми для простоты, а можно вещественными, чтобы решать задачу в более общем случае. Так же потребуются переменные, в которые мы запишем длины сторон треугольника `(a, b, c)` и площадь `(S)`. Эти переменные однозначно должны быть вещественными, так как при вычислении расстояния между точками нам придётся извлекать квадратный корень, и, соответственно, результат получится вещественным. И ещё предлагается ввести вещественную переменную `p`, в которой будет храниться полупериметр треугольника, так как площадь будет вычисляться по формуле Герона. Приведём полный текст программы:

       var x1,y1,x2,y2,x3,y3:integer; a,b,c,p,S:real;
          begin
             Write('Введите координаты вершин треугольника ');
             Readln(x1,y1,x2,y2,x3,y3);
             a:=sqrt(sqr(x1-x2)+sqr(y1-y2));
             b:=sqrt(sqr(x1-x3)+sqr(y1-y3));
             c:=sqrt(sqr(x2-x3)+sqr(y2-y3));
             p:=(a+b+c)/2;
             S:=sqrt(p*(p-a)*(p-b)*(p-c));
             Writeln('Площадь треугольника равна ',S:5:2);
             Readln;
          end.

    Пример 4

    Идёт `k`-ая секунда суток (`k` вводится). Вывести, сколько полных часов `h` и полных минут `m` прошло с начала суток.

    Решение

    В этой задаче все параметры целые. Решается она с помощью операций div и mod. Эти операции можно использовать для «срезания периодов» при переводе мелких единиц измерения в более крупные (например, секунд в минуты). Операция div нам выдаст количество полных периодов (сколько полных минут содержится в большом количестве секунд), а операция mod – количество единиц в последнем неполном периоде (сколько секунд не укладывается в полное количество минут). Приведём полный текст решения.

       var k,h,m:integer;
          begin
             Write('Введите номер секунды в сутках');
             Readln(k);
             h:=k div 3600;
             m:=k mod 3600 div 60;
             writeln('С начала суток прошло ',h,' часов и ',m,' минут');
             readln;
          end.

    Пример 5

    Вводится четырёхзначное число. Вывести произведение его цифр.

    Решение

    Эта задача показывает ещё одно применение операций div и mod – выделение цифр из целого числа. Описанное ниже решение работает только для случая, когда количество цифр в числе заранее известно. В противном случае придётся использовать циклический алгоритм. Приведём текст решения.

       var N,c1,c2,c3,c4:integer;
          begin
             Write('Введите целое четырёхзначное число');
             Readln(N);
             c1:=N div 1000;
             c2:=N div 100 mod 10;
             c3:=N div 10 mod 10;
             c4:=N mod 10;
             Writeln('Произведение цифр вашего числа равно',c1*c2*c3*c4);
             Readln;
          end.