Мы рады приветствовать вас на курсе Информатики. Данный курс рассчитан на три года обучения. Ориентировочно, это девятый, десятый и одиннадцатый классы средней школы. Поэтому в ходе изложения будут использоваться соответствующие знания из курсов математики.
Данный курс состоит из трёх больших частей, которые будут чередоваться по заданиям. Первая часть курса – теоретическая. В ней будут рассматриваться общие знания, которые необходимы любому человеку, собирающемуся связать свою жизнь с техническими специальностями. В частности, будут рассматриваться особенности представления информации различного вида (числовая, текстовая, графическая и т. д.), алгебра логики, математическая теория информации, теория алгоритмов и многое другое.
Вторая часть курса – программистская. В этой части мы будем рассматривать основные концепции языков программирования и учиться писать полноценные программы. Вас ждёт большое множес-тво задач самого разного вида. По завершении курса вы сможете не просто писать программы на одном языке программирования, но уже будете обладать достаточными знаниями, чтобы самостоятельно легко изучать другие языки.
Третья часть курса – технологическая. Здесь будут рассматриваться информационно-коммуникационные технологии. В частности, компьютерные сети, обработка баз данных, работа с электронными таблицами и т. д.
На первом году обучения теоретических заданий не будет, а основная масса будет посвящена программистской части курса. Основная цель первого года обучения – овладеть языком программирования как инструментом для дальнейшего использования. В качестве учебного языка программирования мы выберем язык Pascal. Тому есть несколько причин. Во-первых, этот язык изначально создавался для обучения программированию, и в нём нет большого количества сложных тонкостей, для понимания которых требуются глубокие специальные знания (как, например, в языках C/C++). Во-вторых, концептуально Pascal является каноническим языком процедурной парадигмы программирования, и после него можно очень легко переходить на любые другие языки.
Также нам будет интересно не просто решить конкретную задачу, а овладеть стратегиями для решения больших классов задач. Нужно будет научиться видеть общие моменты в предлагаемых задачах и сформировать определённые шаблоны для быстрого написания программ. Кроме того, особое внимание мы будем уделять красоте и эффективности алгоритмов.
Для выполнения заданий программистской части курса вам будет необходимо установить себе среду программирования, либо воспользоваться online-компилятором. Имейте в виду, что даже для языка Pascal различные среды программирования могут серьёзно различаться (например, free pascal и Pascal ABC.NET). Мы будем обращать внимание на данные различия по ходу изложения материала.
В рамках первого задания мы будем изучать основы языка программирования и особенности выполнения арифметических операций.
Ввести значения $$ x$$ и $$ n$$. Вычислить сумму ряда $$ 1+x+{x}^{2}+{x}^{3}+\dots +{x}^{n}$$.
Сумма вычисляется накопительным путём: сначала вычисляется каждое слагаемое, а потом оно добавляется в сумму. Каждое слагаемое также вычисляется накопительным путём.
var x,n,i,s,a:integer;
begin
write('введите значения x и n');
readln(x,n);
S:=1; a:=1
for i:=1 to n do
begin
a:=a*x; s:=s+a
end;
writeln(s);
readln
end.
Заметим, что эту задачу можно решить, воспользовавшись формулой суммы первых `n` членов геометрической прогрессии, но наша цель не решить конкретную задачу, а понять принцип накапливания (суммы). Ибо далеко не любая последовательность чисел является геометрической или арифметической прогрессией.
Вводится последовательность натуральных чисел. Признак конца ввода – число `0`. Вывести среднее арифметическое чисел из последовательности (`0` не учитывается).
Эта задача относится к очень важному классу задач – обработка последовательностей с признаком конца и заранее неизвестным количеством элементов. В таких задачах нужно пользоваться операторами while и repeat. Причём, если оговаривается, что последовательность непустая, можно использовать repeat, а если этого не оговаривается, как в данной задаче, то нужно обязательно пользоваться циклом while, так как цикл repeat всегда выполняется, по крайней мере, один раз. Приведём полный текст решения. Переменная `s` подсчитывает сумму элементов последовательности, а переменная `k` – их количество.
var a,s,k:integer;
begin
s:=0; k:=0;
writeln('Введите последовательность натуральных чисел. Ноль – признак конца');
read(a);
while a<>0 do
begin s:=s+a; k:=k+1; read(a) end;
Writeln('среднее арифметическое=',s/k:0:4)
end.
Обратите внимание, что для ввода данных используется оператор read. Это позволяет набивать элементы в строчку через пробел. Если же использовать readln, то набивать значения придётся в столбик, что неудобно. Ещё одно важное замечание в этой задаче – оператор ввода внутри цикла должен быть последним, чтобы сразу попадать на проверку признака конца. Эти замечания относятся ко ВСЕМ задачам на обработку последовательностей с признаком конца.
Ввести целое число `n`. Вывести YES, если оно простое, и NO, если оно составное.
Эта задача демонстрирует сразу две важные вещи. Во-первых, как проверять делимость целых чисел, а во-вторых, технику флажков. Флажком называется переменная, которая имеет некоторое начальное значение и меняет его, если происходит определённое событие. Как правило, флажок имеет тип boolean.
В нашей задаче мы будем перебирать числа от `2` до квадратного корня из `n` и проверять, делится ли `n` на каждое из них. Изначально предположим, что `n` – простое, и присвоим флажку значение true, но если `n` поделится на какое-нибудь число, это будет значить, что оно составное, и, соответственно, флажок «упадёт» на значение false. Проверять на делимость нужно, сравнивая остаток от деления с нулём.
var n,i:integer;
f:boolean;
begin
Write('Введите значение n ');
Readln(n);
f:=true;
for i:=2 to round(sqrt(n)) do
if n mod i = 0 then f:=false else;
if f=true
then writeln('YES')
else writeln('NO');
Readln
end.
Зачастую в задаче нужно повторять одни и те же действия много раз. Повтор некоторого фрагмента программы несколько раз называется циклом. Рассмотрим следующий пример.
Вывести на экран квадраты чисел от `1` до `100`.
Очевидно, что для решения этой задачи нам придётся `100` раз выполнять команду вывода соответствующего числа на экран. Писать `100` операторов вывода как-то не хочется (слишком трудоёмко), поэтому будем знакомиться с операторами цикла. В языке Pascal существует три оператора цикла: for, while, repeat. Начнём с цикла for. Этот оператор цикла реализует следующую идею: «Повторять некоторую последовательность команд `N` раз, где `N` известно до начала повторения». Познакомимся с синтаксисом этого оператора.
for имя переменной := начальное значение to конечное значение do оператор
В этой конструкции переменная, стоящая после слова for, называется параметром или счётчиком цикла, а оператор, стоящий после слова do, называется телом цикла. Начальное и конечное значения, по сути, являются константами или выражениями одного типа со счётчиком.
Алгоритм выполнения цикла for следующий:
1) вычисляются начальное и конечное значения;
2) счётчику цикла присваивается начальное значение;
3) значение счётчика сравнивается с конечным. Если оно больше конечного, то выполнение цикла завершается и начинает выполняться следующий оператор программы, в противном случае переход к пункту 4;
4) выполняется тело цикла;
5) значение счётчика увеличивается на `1`;
6) переход к пункту 3.
В качестве примера рассмотрим решение задачи, поставленной выше. В качестве счётчика будем использовать переменную `i`.
var i:integer;
begin
for i:=1 to 100 do write(i*i,' ');
Readln
end.
Согласитесь, что решение фактически в одну строчку выглядит гораздо приятнее, чем в `100` строк (если не пользоваться оператором цикла).
Необходимо сделать несколько замечаний по поводу цикла for.
1) Типы счётчика начального и конечного значений должны совпадать, при этом в настоящий момент из известных нам типов можно использовать только integer и boolean. Вещественный тип использовать нельзя.
2) Начальное и конечное значения вычисляются один раз до начала цикла (и после не перевычисляются). Рассмотрим пример.
i:=1; for i:=i to i do writeln('HI');
Этот оператор цикла выполнится всего один раз, а не бесконечно много.
3) В теле цикла значение счётчика изменять нельзя. Так прописано в стандарте языка Pascal, и это требование поддерживается в системах семейства Delphi. Однако в системах семейства Borland Pascal значение счётчика изменять можно, что может приводить к непредсказуемым последствиям (поэтому будем считать, что независимо от системы значение счётчика изменять нельзя).
4) После завершения цикла значение счётчика не определено, то есть нельзя считать, что оно равно конечному значению или больше на единицу и пользоваться этим в дальнейшем алгоритме.
5) Тело цикла по грамматике должно состоять только из `1` оператора. Если же там по алгоритму должно быть несколько, нужно использовать составной оператор.
6) Можно слово to заменить на слово downto. В этом случае значение счётчика после каждого выполнения тела цикла будет уменьшаться на `1`, а выход из цикла произойдёт, когда значение счётчика окажется меньше, чем конечное.
Перейдём к знакомству с другими операторами цикла: while и repeat. Эти операторы реализуют следующие идеи: «Повторять некоторую последовательность команд пока выполняется некоторое условие» (цикл while) и «Повторять некоторую последовательность команд до тех пор, пока не выполнится некоторое условие» (цикл repeat). Познакомимся с синтаксисом оператора цикла while.
while условие do оператор.
После слова while должно быть логическое выражение (называемое условием), которое может принимать значение true или false. Оператор, стоящий после do, аналогично оператору for является телом цикла. Выполняется цикл while так:
1) вычисляется значение условия, если получилось true, то переход к пункту 2, иначе выход из цикла и переход на следующий оператор программы;
2) выполняется тело цикла;
3) переход к пункту 1.
Фактически оператор while является многократным применением оператора if с пустой веткой else. Аналогично оператору for, тело цикла должно состоять из `1` оператора. Однако в отличие от цикла for возможна ситуация, когда цикл будет выполняться бесконечное количество раз (зациклится). Например, while 2*2=4 do... . Что написать после do, совершенно не важно, важно, что оно будет выполняться, пока 2*2=4, а это всегда так и никогда не изменится. Значит, чтобы избегать зацикливания, параметры условия должны быть переменными, например while x*x=4 do ... . Хотя это тоже не гарантирует отсутствие зацикливания.
Осталось познакомиться с последним оператором цикла. Рассмотрим его синтаксис.
repeat
Оператор 1;
Оператор 2;
... .
Оператор N
until условие
Все операторы, написанные между repeat и until, являются телом цикла. Это выгодно отличает оператор repeat от других циклов – составной оператор здесь не требуется, а операторными скобками можно считать слова repeat и until. Работает этот оператор по следующему алгоритму:
1) выполняется тело цикла;
2) вычисляется значение условия. Если получилось true, то выход из цикла и переход к следующему оператору программы, в противном случае переход к пункту 1.
Отличительная особенность оператора цикла repeat заключается в том, что тело всегда выполняется, по крайней мере, один раз. Это нужно учитывать в задачах при выборе оператора цикла. Аналогично оператору while, цикл repeat может зациклиться, правда в случае, когда условие никогда не принимает значение true, например,
repeat...until 2*2=5.
В рассматриваемых ранее задачах процесс вычисления был линейным, то есть программа не должна была выполнять разные действия в зависимости от того, какие данные ей ввели. Теперь вспомним задачи с ветвящимся алгоритмом.
Ввести номер года. Вывести слово YES, если год високосный, и NO, если он – не високосный.
По условию очевидно, что в зависимости от входных данных программа должна будет выполнить один из двух операторов вывода: Writeln('YES') или Writeln('NO'). При этом написать в программе нам придётся оба, а вот выполняться должен будет только один из них. Для того чтобы реализовывать подобные ветвления алгоритма, в языке Pascal существует условный оператор. В общем виде он выглядит следующим образом:
if логическое выражение
then оператор
else оператор
В этой конструкции слова if, then и else являются служебными зарезервированными словами языка. Работает эта конструкция так: сначала вычисляется логическое выражение, стоящее после if. Если получилось значение true, то выполняется оператор, стоящий после слова then, а если получилось значение false, то выполняется оператор, стоящий после слова else.
Обратите внимание, что внутри условного оператора нет никаких точек с запятой, поскольку он является единой конструкцией, а точка с запятой – это разделитель между операторами. Для удобства чтения программ принято условие записывать на одной строке, а ветви then и else начинать с новой строки, однако это не является синтаксическим правилом языка.
В качестве примера условного оператора рассмотрим решение задачи, поставленной выше. Год считается високосным, если он делится нацело на `400`, или если он делится нацело на `4`, но не делится нацело на `100`. Приведём полный текст решения:
var y:integer;
begin
write('Введите номер года ');
readln(y);
if (y mod 400 = 0)or(y mod 4 = 0)and(y mod 100 <> 0)
then writeln('YES')
else writeln('NO');
end.
По грамматике языка после слов then и else должен стоять только один оператор языка. То есть запись if x>0 then x:=4; y:=0 else z:=9; является синтаксически неверной. А как быть, если всё-таки нужно выполнить более одного оператора? Для таких случаев в языке Pascal предусмотрен составной оператор, который позволяет превратить группу операторов в один. Выглядит он следующим образом: сначала записывается ключевое слово begin, далее – интересующая нас последовательность операторов через точку с запятой, а в конце пишется ключевое слово end. В отличие от конца программы, точка после этого слова не ставится. Слова begin и end называются операторными скобками. Запишем правильную версию условного оператора, приведённого выше: if x>0 then begin x:=4; y:=0 end else z:=9;
Обратите внимание на следующий тонкий момент: если требуется выполнить более одного оператора в ветке then, и при этом мы забудем написать операторные скобки, то это является синтаксической ошибкой, и программа просто не будет работать. Если же забыть написать операторные скобки в ветке else, то программа работать будет, но не так, как предполагалось. Рассмотрим пример: if x>0 then y:=9 else z:=8; c:=5;
В этом примере условный оператор заканчивается после z:=8; в то время как оператор c:=5; является следующим оператором программы и выполняется независимо от результата сравнения `x` с нулём. Если же написать операторные скобки, то присваивание в `c` числа `5` произойдёт только в случае x<=0.
Последнее замечание заключается в том, что в ветке else в качестве оператора может стоять и пустой оператор.
Рассмотрим следующий пример.
Вводятся `3` целых числа – `a`,`b`,`c`. Требуется в переменную `a` записать минимальное из этих чисел, в `b` – среднее и в `c` – максимальное.
Алгоритм решения этой задачи такой: сначала сравним значения переменных `a` и `b`, если значение `a` – больше, поменяем их местами. После этого сравним значения переменных `a` и `c`, и если значение `a` – больше, поменяем их местами. После этих двух сравнений в переменной `a` гарантированно окажется наименьшее из трёх чисел. Осталось сравнить переменные `b` и `c`, и в случае, когда в переменной `b` находится большее значение, поменять их местами.
Очевидно, что в этом алгоритме у нас три сравнения, следовательно, три последовательных условных оператора. При этом в каждом из них какие-то действия (поменять местами значения двух переменных) нужно выполнять только в ветке then, в ветке else (например, если в первом сравнении в переменной a находится уже более маленькое число, чем в переменной `b`) никаких действий выполнять не нужно. Но мы всё равно будем её записывать, чтобы избегать путаницы. Приведём полный текст решения, используя для обмена значений двух переменных дополнительную переменную `x`.
var a,b,c,x:integer;
begin
writeln('введите три целых числа ');
readln(a,b,c);
if a>b then begin x:=a; a:=b; b:=x end else;
if a>c then begin x:=a; a:=c; c:=x end else;
if b>c then begin x:=b; b:=c; c:=x end else;
writeln(a,b,c); readln
end.
В языке Pascal кроме уже изученных нами числовых типов ещё есть логический, который называется Boolean. Переменные этого типа занимают `1` байт оперативной памяти и могут принимать всего два значения – true и false (истина и ложь). Логическим переменным можно присваивать значения точно так же, как и числовым. Так же можно выводить их значения на экран, а вот вводить их с клавиатуры нельзя!
В языке Pascal определены `6` операций сравнения, результатом которых является логическое значение. Это операции: «больше» (>), «больше или равно» (>=), «меньше» (<), «меньше или равно» (<=), «равно» (=), и «не равно» (<>). Например, операция 5 > 2 выдаст значение true, а операция x<>3 выдаст значение true, если переменная `X` имеет любое значение, кроме `3`. Сравнивать можно не только числа (причём как целые, так и вещественные), но и логические значения. При этом считается, что значение true больше, чем значение false.
Помимо операций сравнения ещё существуют и логические операции: AND (конъюнкция, логическое умножение, операция «И»), OR (дизъюнкция, логическое сложение, операция «ИЛИ»), NOT (отрицание, инверсия), XOR (строгая дизъюнкция, исключающее «ИЛИ», сложение по модулю `2`). В скобках указаны возможные названия данных операций в алгебре логики. Операнды этих операций должны быть логического типа. Результат вычислений также будет логический. При этом операции AND, OR, XOR имеют по два операнда, а операция NOT – всего один, который записывается справа от названия операции. Названия логических операций являются ключевыми словами языка. Приведём таблицы результатов логических операций для всех возможных значений операндов (в алгебре логики такие таблицы называются таблицами истинности):
| x | not x |
| false |
true |
|
true |
false |
|
x |
y | x and y |
x or y |
x xor y |
| false | false | false | false | false |
| false | true | false | true | true |
| true | false | false | true | true |
| true | true | true | true | false |
Логический результат даёт также стандартная функция odd(x), которая применяется к целочисленному аргументу `x`:
odd(x) = true, если `x` нечётно;
odd(x) = false, если `x` чётно.
Приоритет операций в логическом выражении следующий:
1) Операция NOT.
2) Операции группы умножения AND, *, / ,div, mod
3) Операции группы сложения OR, XOR, +, -
4) Операции сравнения >, <, >=, <=, =, <>
Операции одного приоритета выполняются слева направо. Операции в круглых скобках имеют более высокий приоритет, чем операции вне скобок.
Записать логическое выражение, истинное в случае, когда переменная `X` имеет значение из отрезков `[2,5]` или `[-1,1]`.
(X>=2) AND (X<=5) OR (abs(X)<=1).
Теперь воспользуемся всеми полученными знаниями и рассмотрим примеры простейших программ. Условимся в примерах не различать заглавные и строчные буквы, а ключевые слова выделять жирным шрифтом.
Ввести координаты трёх вершин треугольника. Вывести его площадь. Гарантируется, что треугольник существует (ввод корректный).
Для решения этой задачи нам потребуется `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.
Идёт `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.
Вводится четырёхзначное число. Вывести произведение его цифр.
Эта задача показывает ещё одно применение операций 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.
Операторы read и readln предназначены для задания значений переменным путём ввода их с клавиатуры. Правило их применения одно и то же: после слова read или readln в скобках через запятую перечисляются имена переменных, значения которых мы хотим ввести (список ввода). Число этих имён не ограничено. Запятая служит разделителем между именами переменных:
readln(имя, имя, ..., имя)
При срабатывании оператора read или readln выполнение программы будет приостановлено до тех пор, пока пользователь не введёт соответствующее количество значений. Вводимые значения должны быть того же типа, что и переменные. Если в read или readln переменных несколько, то они могут быть набиты в одной строке, но одно число от другого должно отделяться пробелом или переводом строки.
Чтобы выполнить оператор read или readln после набивания значений с клавиатуры, нужно нажать клавишу «Enter». В результате переменные приобретут заданные вами значения. Между read и readln существует единственное различие: после выполнения readln курсор переходит на новую строку, игнорируя всю оставшуюся информацию в прежней строке, а после выполнения read курсор остаётся в той же строке, и новая набивка данных для read или readln будет проходить в той же строке. Но, так как после нажатия клавиши «Enter» курсор в любом случае переходит на новую строчку, для однократного ввода значений переменных разницу между операторами read и readln заметить невозможно. Тем не менее, в данном случае лучше использовать readln. Оператор readln можно использовать и без параметров вообще. Тогда программа просто будет находиться в режиме ожидания, пока пользователь не нажмёт клавишу «Enter». Такой оператор, например, удобно ставить самым последним оператором в программе. Тогда можно сразу посмотреть результат работы программы, а потом нажать «Enter», и только тогда работа программы завершится.
Перед вводом данных с клавиатуры рекомендуется выдавать на экран приглашение, например:
write('Введите число a => ');
readln(a);
