Решение олимпиадных задач по информатике
Покупка
Новинка
Тематика:
Общая информатика
Издательство:
ИНТУИТ
Автор:
Ларина Элла Семеновна
Год издания: 2016
Кол-во страниц: 128
Дополнительно
Авторская программа предпрофильной подготовки учеников 6 или 7 классов. Главной целью программы является развитие творческого потенциала школьников, их способностей к плодотворной умственной деятельности.
<p>Важнейшей ролью математических кружков является индивидуальная работа с одаренными школьниками, направленная на развитие их мыслительных способностей, настойчивости в выполнении заданий, творческого подхода и навыков в решении нестандартных задач.</p>
<p>Необходимо расширить кругозор школьников, для этого в программу работы математического кружка включаются темы, которые не входят в базовую программу или не получают там должного внимания. Эти темы, с одной стороны, должны быть доступны обучаемым, с другой стороны, позволять им успешно выступать на олимпиадах.</p> <p>Человеку нужна мотивация его деятельности, участие в различных конкурсах и олимпиадах, и особенно победа в них побуждает учащихся продолжать изучение данного предмета, дух соревнования поддерживает интерес.</p>
<p>С другой стороны, отсутствие "наказания” в виде оценок позволяет ребенку чувствовать себя свободнее, чем на традиционных уроках, формирует умение высказывать гипотезы, опровергать или доказывать их, искать ошибки и неточности в рассуждениях.</p> <p>Необходимо также заметить, что участие в работе кружка математики создает необходимую базу для успешного изучения других предметов естественнонаучного цикла, таких как информатика, физика, химия, астрономия. Поэтому часто занятия математикой, несмотря на отсутствие видимых достижений в математических соревнованиях, приводят к успехам в других дисциплинах.</p> <p>Содержание курса разбито на 5
модулей, каждый из которых содержит изучение теории и применение ее при решении задач.</p>
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 00.03.03: Информатика
- ВО - Специалитет
- 00.05.03: Информатика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
Решение олимпиадных задач по информатике 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