В прошлом задании мы работали с числовыми типами переменных и учили арифметику, теперь познакомимся с логическим типом переменных, который называется 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, в случае выполнения указанного условия.
Целое число `n` делится на `13`.
n mod 13 = 0
Надо проверять, что остаток от деления на `13` является нулём.
Целое число `n` делится на `13` и `7`.
(n mod 13 = 0) and (n mod 7 = 0)
Здесь надо проверить одновременное выполнение двух условий.
Переменная `x` имеет значение из отрезков `[2,5]` или `[-1,1]`.
(x>=2) and (x<=5) or (abs(x)<=1)
Из чисел `x`, `y`, `z` хотя бы два равны между собой.
(x = y) or (x = z) or (y = z)
Числа `x`, `y`, `z` равны между собой.
(x = y) and (x = z)
Обратите внимание, что согласно таблице приоритетов, операции сравнения имеют самый низкий приоритет. Однако, как правило, в сложных выражениях нужно сначала выполнить сравнения, а потом группировать их результаты при помощи логических операций. Поэтому не нужно забывать брать операции сравнения в скобки, чтобы не получить неправильный порядок действий.
В рассматриваемых ранее задачах на программирование процесс вычисления был линейным, то есть программа не должна была выполнять разные действия в зависимости от того, какие данные ей ввели. Теперь рассмотрим задачи с ветвящимся алгоритмом.
Ввести номер года. Вывести слово 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;
При написании программ с ветвлениями очень часто возникает ситуация, когда ветвей становится слишком много. Поэтому приходится задумываться о том, как ничего не упустить из рассмотрения, как не рассматривать несущественные случаи и как обеспечить выполнение ровно одной ветви при разборе случаев.
Начнём с ответа на последний вопрос. Для того, чтобы обеспечить выполнение ровно одной ветви алгоритма, необходимо записывать весь разбор случаев в виде одного условного оператора. Конечно же, он будет сложный, с вложенными многоуровневыми проверками. Однако, если в итоге условный оператор, реализующий разбор случаев, один (а не несколько, записанных через точку с запятой), то это гарантирует нам, что в итоге выполнится ровно одна ветвь алгоритма.
Для того, чтобы не упустить из рассмотрения никаких случаев и не рассматривать несущественные случаи, нужно перебирать их не в случайном порядке, а по какой-либо стратегии. Сейчас мы рассмотрим одну из стратегий разбора случаев, которую условно можно назвать «Естественное возникновение». Её суть заключается в следующем: Изначально, мы решаем задачу так, будто бы никакого деления на случаи нет, а появляется оно лишь тогда, когда выполнить основной сценарий невозможно.
Рассмотрим следующий пример задачи:
Решить в целых числах линейное уравнение `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.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. Примеры задач
Рассмотрим несколько примеров задач на оператор цикла.
Дано целое число, не меньшее `2`. Выведите его наименьший натуральный делитель, отличный от `1`.
Для решения этой задачи нам необходимо перебирать натуральные числа, начиная с двух и проверять каждое из них, не является ли оно делителем исходного числа. Процесс завершается, когда делитель найден. Очевидно, что процесс завершится всегда, поскольку в худшем случае число разделится само на себя. Приведём код программы.
var i,n:integer;
begin
readln(n);
i:=2;
while n mod i <> 0 do
i:=i+1;
end;
writeln (i);
end.
В первый день спортсмен пробежал `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.
Дано натуральное число `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.
Ввести целое число `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.
