Решение олимпиадных задач по информатике

Решение олимпиадных задач по информатике

2-е издание, исправленное

Ларина Э.С.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Решение олимпиадных задач по информатике/ Э.С. Ларина - М.: Национальный Открытый
Университет “ИНТУИТ”, 2016

Авторская программа предпрофильной подготовки учеников 6 или 7 классов. Главной целью
программы является развитие творческого потенциала школьников, их способностей к плодотворной
умственной деятельности.
<p>Важнейшей ролью математических кружков является индивидуальная работа с одаренными
школьниками, направленная на развитие их мыслительных способностей, настойчивости в
выполнении заданий, творческого подхода и навыков в решении нестандартных задач.</p>
<p>Необходимо расширить кругозор школьников, для этого в программу работы математического
кружка включаются темы, которые не входят в базовую программу или не получают там должного
внимания. Эти темы, с одной стороны, должны быть доступны обучаемым, с другой стороны,
позволять им успешно выступать на олимпиадах.</p> <p>Человеку нужна мотивация его
деятельности, участие в различных конкурсах и олимпиадах, и особенно победа в них побуждает
учащихся продолжать изучение данного предмета, дух соревнования поддерживает интерес.</p>
<p>С другой стороны, отсутствие “наказания” в виде оценок позволяет ребенку чувствовать себя
свободнее, чем на традиционных уроках, формирует умение высказывать гипотезы, опровергать или
доказывать их, искать ошибки и неточности в рассуждениях.</p> <p>Необходимо также заметить,
что участие в работе кружка математики создает необходимую базу для успешного изучения других
предметов естественнонаучного цикла, таких как информатика, физика, химия, астрономия. Поэтому
часто занятия математикой, несмотря на отсутствие видимых достижений в математических
соревнованиях, приводят к успехам в других дисциплинах.</p> <p>Содержание курса разбито на 5
модулей, каждый из которых содержит изучение теории и применение ее при решении задач.</p>

(c) ООО “ИНТУИТ.РУ”, 2012-2016
(c) Ларина Э.С., 2012-2016

3

Предисловие

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

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

Типы данных

Целые числа

Описатель типа Длина(байт) Минимальное число Максимальное число
Integer
2 (знак)
-32768
+32767

Shortint
1 (знак)
-128
+127

Longint
4 (знак)
-2147483648
+2147483647

Byte
1 (без зн.)
0
255

Word
2 (без зн.)
0
65535

Строковые переменные

Описатель типа Длина(байт) Количество значений Допустимые значения
Char
1
256
литера (символ)

Логические переменные

Описатель типа Длина(байт) Количество значений Допустимые значения
Boolean
1
2
true, false

Вещественные переменные

Описатель типа Длина(байт) Число значащих цифр Директива компилятора
Real
6
11
не требуется

Single
4
7
{$N+}

Double
8
15
{$N+}

Extended
10
19
{$N+}

Comp
8
19 (цел.число,64-bit)
{$N+}

Арифметические операции

4

целочисленное

деление

остаток от деления

(модуль)

двоичный сдвиг

влево

двоичный сдвиг

вправо

a
B
a div b
a
b
a mod b
a
b
a shl b
a
b
a shr b

10 20 0
10
20
10
10 2 40
10
1 5

40 15
2
40
15
10
32 1 64
32
2 8

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

операции булевой алгебры (высший приоритет)

Not
And
or
xor

A
not a
a
b
a and b
a
b
a or b
a
b
a xor b

False True
false false False
false false false
false false false

true
False false true
False
false true
true
false true
true

true
false False
true
false true
true
false true

true
true
true
true
true
true
true
true
false

операции отношения (низший

приоритет)

a = b равно
A <> b не равно
a < b меньше
A <= b меньше или равно (не больше)
a > b больше
A >= b больше или равно (не меньше)

Функции для обработки числовых переменных

Функция
Назначение
Пример вызова
Результат

Abs (число)
абс. значение числа
abs(-3.5)
+3.5

Arctan (тангенс-угла) арктангенс числа
arctan(0)
0

Cos (угол)
косинус угла(рад.)
cos(pi)
-1

Exp (число)
Экспонента
exp(1)
2.718281828…

Frac (число)
дробная часть числа frac(3.5)
0.5

Int (число)
целая часть числа
int(3.5)
3.0

Ln (число)
нат. Логарифм
ln(2.718281828) 1.0

Odd (число)
проверка нечетности odd(3)
True

pi
число пи
pi
3.141592…

Random (число)
“случайное” число
random(10)
Число в [0;9]

Sin (угол)
синус угла(рад.)
sin(pi)
0

Sqr (число)
квадрат числа
sqr(2.0)
4.0

Sqrt (число)
квадратный корень
sqrt(25.0)
5.0

Функции и процедуры для обработки строковых переменных

5

Функция
Значение
Пример вызова
Результат

chr(номерсимвола-n)
Символ номер n (#n)
chr(33)
‘!’

ord (величина) номер величины (код)
ord(‘!’)
33

succ (величина) Следующее значение в

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

succ(‘y’)
‘z’

pred (величина) Предыдущее значение в

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

pred(‘y’)
‘x’

copy(s,p,n)
Выделить n символов из строки s
начиная с позиции p

copy(‘роза’,3,2)
‘за’

concat(s1,s2,…
sn)
Соединить строки (литеры) в одну
строку (конкатенация)

concat(‘г’,’роза’) ‘гроза’

length (строка) Длина строки [символ.]
length(‘роза’)
4

pos(s1,s2)
номер позиции строки s1 внутри
строки s2 (если не найдена, 0)

pos(‘за’,’роза’)
3

Процедура
Назначение
Пример вызова
Результат

delete(s,p,n)
удалить n символов из строки s с
позиции p

delete(‘роза’,1,2)
‘за’

insert(s1,s2,p) вставить строку (литеру) s1 в строку

s2 с позиции p

insert(‘г’,’роза’,1) ‘гроза’

Процедура
(функция)
Назначение
Пример вызова
Результат

round (число)
округлить число
n := round(3.5) 4

trunc (число)
отсечь дробную часть
n := trunc(3.5) 3

str(n:p:q,s)
преобразовать число n в строку
s

str(3.5:3,s)
s = ‘3.5’

val(s,n,p)
преобразовать строку s
(литеру) в число n

val(‘+3.5’,n,p) n = 3.5; p = 0

p=место ошибки

Основы машинной графики

Пример: uses graph, crt;

Основные процедуры и функции

Процедура (функция)
Назначение
Пример вызова
Примечания

d := detect
Определить тип
графического
режима (номер
драйвера)

d := detect
d = драйвер
экрана
(bgi)
(integer)

initgraph(d, m, путь-bgi) Установить

графический режим
экрана

initgraph(d, m,
‘c:\bgi‘)

m = режим
экрана
(vga)
(integer)

cleardevice
Очистить экран и
отменить установки
цвета

cleardevice

6

setcolor (цвет)
Установить цвет
линии (рисунка)

setcolor(magenta)

setbkcolor (цвет)
Установить цвет
фона (очистки)

setbkcolor(0)

putpixel(x,y,цвет)
Точка (x,y)
putpixel(5, 5, red)

line(x1,y1,x2,y2)
Линия (x1,y1)(x2,y2)

line(10,10,20,200)

lineto(x,y)
Чертить линию в
(x,y)

lineto(100,200)

moveto(x,y)
Вести перо в (x,y)
moveto(nx, ny)

circle(x,y,радиус)
Окружность
(x,y,r)

circle(x, y, 20)

arc(x,y,угл1,угл2,радиус) Дуга окружности

(x,y,r) от угла1 до
угла2 (радиан)

arc(10,10,0,pi,5)

setfillstyle(s,цветзаливки)
Установить стиль и
цвет заливки

setfillstyle(1,green)

floodfill(x,y,цветграницы) Залить область с

границей (цвет)
цветом заливки

floodfill(p,q, 10)

rectangle(x1,y1,x2,y2)
Прямоугольник
(x1,y1)-(x2,y2)

rectangle(2,2,5,10)

bar(x1,y1,x2,y2)
Прямоугольник
(x1,y1)-(x2,y2) с
заливкой цвета

bar(2, 2, m, n)

closegraph
Закрыть
графический режим
экрана

closegraph

7

Базовые формулы (зависимости) и задачи, решаемые с их
помощью

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

Очень часто в решениях задач необходимо использовать ту или иную зависимость,
применить формулу. Не стоит сейчас рассматривать большой круг математических
формул, которые когда-либо использовались в решении задач по программированию
(их достаточно много). А вот на некоторых из них, так называемых “базовых”, стоит
остановиться:

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

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

Зависимость уменьшающейся переменной X в теле цикла от
увеличивающегося значения счетчика цикла i

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

Таблица 1.1.

1 5
2 4
3 3
4 2
5 1
Итого

Фрагменты программ, в котором реализована эта зависимость:

Бейсик:
Паскаль:

 …
for i=1 to n 
x=n-i+1 

…
for i:=1 to n do
x:=n-i+1;

8

next
…

…

Разбор задачи, приведенной ниже позволит закрепить полученные знания.

Задача “Палиндром”: Определить, палиндром ли слово, введенное с клавиатуры
(палиндром читается одинаково слева направо и справа налево).

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

Обратите внимание, что тело цикла выполняется n/2 раз (за один проход сравниваются
2 символа).

Программа на Бейсике:

input "введите слово"; a$
n=len (a$)
for i=1 to n/2
 if mid$ (a$,i,1)<> mid$ (a$,n-i+1,1) then k=1
next
if k=0 then print "палиндром" else print "не палиндром"

Программа на Паскале:

var a:string;
 k,n,i: integer;
begin
 writeln ('введите слово');
 readln (a);
 k:=0;
 n:=length(a);
 for i:=1 to (n div 2) do
  if copy(a,i,1) <> copy(a,n-i+1,1) then k:=1;
 if k=0 then writeln ('палиндром')
 else writeln ('не палиндром');
end.

Тест:

Дано:
Ротор

Результат палиндром

Длина отрезка

9

Для нахождения длины отрезка, заданного координатами своих концов (см. рис. 1.1)
воспользуемся теоремой Пифагора:

Рис. 1.1. 

Арифметическое выражение для вычисления длины отрезка на Бейсике:

sqr ((x1-x2)^2+(y1-y2)^2)

Арифметическое выражения для вычисления длины отрезка на Паскале:

sqrt (sqr(x1-x2)+sqr(y1-y2))

Разбор решения задачи, приведенной ниже позволит закрепить полученные знания.

Задача: Найти периметр треугольника, координаты вершин которого вводятся с
клавиатуры (рис. 1.2).

Рис. 1.2. 

Идея решения: Для нахождения периметра треугольника необходимо найти длины его
сторон.

Программа на Бейсике:

input x1, y1
input x2, y2
input x3, y3

10