§ 8. Использование условий для исполнителей

8.1. Понятие условия

Принятие решений зачастую зависит от различных условий. Если на улице идёт дождь, то нужно взять зонт; если хорошо подготовился к уроку, то получишь высокую отметку, иначе низкую и др. Рассмотрите примеры 8.1—8.3, показывающие использование условий в жизни человека.

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

Условием для исполнителя является понятное исполнителю высказывание, которое может быть истинным (соблюдаться) либо ложным (не соблюдаться).

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

В примере 8.4 приведены простые условия, в примере 8.5 составные условия. Условия под одинаковыми номерами относятся к одному исполнителю. Исполнителем для первого условия может быть текстовый редактор. Второе условие может быть понятно роботу, двигающемуся по лабиринту, или компьютерному исполнителю Робот, средой обитания которого является клеточное поле. Исполнителем для третьего условия может быть человек, понимающий математику и английский язык, или компьютер, выполняющий программу на языке Python.

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

Рассмотрите алгоритм с выбором действий в зависимости от значения условия (пример 8.7).

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

  • вычисли длину цепочки символов;
  • допиши символы в конце цепочки;
  • поменяй местами соседние символы (первый — со вторым, третий — с четвёртым, пятый — с шестым и т. д.);
  • проверь истинность условия «длина цепочки символов нечётная».

От значения условия зависит, будет повторяться выполнение действий или нет: действия будут выполняться пока условие истинно (ложно).

В примере 8.8 приведён алгоритм с повторением действий, пока истинно условие.
Исполнитель Вычислитель может выполнять следующие команды:

  • раздели натуральное число нацело на 10;
  • получи остаток от деления числа на 10;
  • выдай ответ: запись цифр исходного числа в обратном порядке;
  • проверь истинность условия «число не равно 0».

8.2. Условия для компьютерных исполнителей

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

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

Многие компьютерные исполнители используются для учебных целей. В прошлом году вы познакомились с компьютерным исполнителем Черепаха. Условия для этого исполнителя приведены в примере 8.10. Но есть ещё и другие учебные компьютерные исполнители: Чертёжник, Робот, Водолей, Кузнечик, Кенгурёнок и др. Условия могут входить в систему команд исполнителя как логические высказывания. Выполняя такую команду, исполнитель проверяет, истинно условие или ложно (пример 8.11).

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

  • кругом решаемых задач;
  • средой исполнителя;
  • системой команд;
  • режимами работы (непосредственный и программный).

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

  1. функциональные — предписания, направленные непосредственно на преобразование информации;
  2. логические — предписания, определяющие дальнейшее направление действий.

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

Пример 8.1. Условия в правилах дорожного движения: если горит зелёный свет, можно переходить улицу.

Пример 8.2. Условия в фольклоре: выбор пути сказочными героями.

Пример 8.3. Применение условия в математике.

Треугольник существует, если для большей стороны а выполняется неравенство:

a < b + c.

Пример 8.4. Простые условия.

  1. Символ скопирован.
  2. Клетка закрашена.
  3. а > Ь.

Пример 8.5. Составные условия.

  1. (Символ скопирован) ИЛИ (Символ вырезан).
  2. (Клетка закрашена) И НЕ (Справа стена).
  3. not (а > b) and (а > с).

Пример 8.6. Характеристики формальных и неформальных исполнителей.

Пример 8.7. Алгоритм для исполнителя Редактор.

  1. Вычисли длину цепочки.
  2. Если длина цепочки символов нечётна, то допиши в конце 0, иначе цепочка не изменяется.
  3. Поменяй символы местами.
  4. Допиши в конце 1.

Пусть исходная цепочка символов — АВС. Длина цепочки — 3.

  1. Условие истинно, поэтому преобразовываем цепочку символов: АВСО.
  2. Попарно меняем символы местами: ВАОС.
  3. Дописываем справа цифру 1: ВА0С1.

Рассмотрим другую цепочку символов: ABCD, длина цепочки — 4.

  1. Условие ложно, поэтому цепочку не преобразовываем.
  2. Попарно меняем символы местами: BADC.
  3. Дописываем справа цифру 1: BADC1.

Пример 8.8. Алгоритм для исполнителя Вычислитель.

  1. Если число не равно нулю, перейди к шагу 2, иначе перейди к шагу 5.
  2. Раздели число на 10.
  3. Получи остаток от деления на 10.
  4. Перейди к шагу 1.
  5. Запиши ответ.

Работа алгоритма для числа 1024

Ответ: 4201.

Алгоритм работал, пока условие было истинным. Условие стало ложным после того, как команды алгоритма (1-4) выполнились четыре раза.

Работа алгоритма для числа 0

Ответ: 0.

Алгоритм прекратил работу сразу после проверки условия, поскольку оно являлось ложным. Команды 2 -4 не выполнились ни разу.

Пример 8.9. Игра «Сокобан»

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

Пример 8.10. Исполнитель Черепаха.

В систему условий, истинность которых может проверять Черепаха, входят следующие:

Также для Черепахи возможна проверка условия нахождения в начале координат:

position() == home()

Условие можно прочитать так: текущая позиция Черепахи совпадает с её «домом» — началом координат.

Пример 8.11. Исполнитель Кенгурёнок.

Исполнитель Кенгурёнок — простой компьютерный исполнитель, создающий рисунки из линий на прямоугольном поле. Система команд: «шаг», «прыжок», «поворот», «впереди край», «впереди не край». Последние две команды — условия, принимающие значения «истина» или «ложь».

Российский академик Андрей Андреевич Марков (младший) (1903-1979 гг.) — исследователь в области математики и теории алгоритмов.

 

 

 
1. Что понимают под условием?
2. Какими могут быть условия?
3. Чем составные условия отличаются от простых?
4. Для чего могут использоваться условия в алгоритмах?

Упражнения

1. Наберите предложения в текстовом редакторе и выделите в них условия цветом (жёлтым — простые, зелёным — составные). Определите, все ли высказывания будут истинными.

  1. Если ты хочешь покататься на велосипеде или на самокате, то нужно сделать уроки.
  2. Я сегодня пойду на тренировку, если не будет дождя.
  3. Деньги служат тебе, если умеешь ими пользоваться, если же не умеешь, властвуют над тобой.
  4. Я помогу ей с задачей по математике, если она попросит меня об этом и не будет со мной спорить.

2. Откройте файл. Дополните условиями предложения в файле.

  1. Бактерии быстро размножаются и образуют группы (колонии), … .
  2. Будешь уважать традиции своих предков и гордиться их поступками и достижениями, … .
  3. Вероятность ошибок при письме снижается, … .
  4. В корне жог/жёг пишется буква о, … .

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

  1. Начать набор нового абзаца текста в текстовом редакторе.
  2. Увидеть результат работы программы для исполнителя Черепаха.
  3. Определить, какая из двух точек, заданных координатами, находится ближе к центру координат.
  4. Определить, есть ли среди цифр натурального трёхзначного числа одинаковые.

4. Исполнитель Попрыгунчик обитает в следующей обстановке.

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

  1. Номера клеток, в которых может находиться Попрыгунчик, чтобы совершить один прыжок в определённом направлении. Например, вверх — A l, В1, … .
  2. Условия, при которых Попрыгунчик может прыгать в определённом направлении.
  3. Номера клеток начальных положений Попрыгунчика и условие, при котором Попрыгунчик, находясь в этих клетках, сможет совершить три прыжка влево.

5*. Поле шахматной доски может быть указано парой натуральных чисел, каждое из которых не превосходит 8: первое число — это номер по вертикали, второе — по горизонтали. Даны натуральные числа k, l, m, n. Запишите простое условие, которое будет истинным тогда и только тогда, когда поля (k, l) и (m, n) являются полями одного цвета.