Главная страница
Финансы
Экономика
Математика
Начальные классы
Информатика
Биология
Медицина
Сельское хозяйство
Ветеринария
Вычислительная техника
Дошкольное образование
Логика
Этика
Религия
Философия
Воспитательная работа
История
Физика
Политология
Социология
Языкознание
Языки
Право
Юриспруденция
Русский язык и литература
Строительство
Промышленность
Энергетика
Другое
Доп
образование
Связь
Электротехника
Автоматика
Физкультура
Технология
Классному руководителю
Химия
Геология
Иностранные языки
Логопедия
Искусство
Экология
Культура
География
ИЗО, МХК
Казахский язык и лит
Директору, завучу
Школьному психологу
Обществознание
Социальному педагогу
Языки народов РФ
ОБЖ
Музыка
Механика
Украинский язык
Астрономия
Психология

Лекциям по курсу Информатика


Скачать 3.84 Mb.
НазваниеЛекциям по курсу Информатика
Анкорlekcii_shiryaevoy.pdf
Дата11.07.2018
Размер3.84 Mb.
Формат файлаpdf
Имя файлаlekcii_shiryaevoy.pdf
ТипЛекция
#19640
страница2 из 9
1   2   3   4   5   6   7   8   9
: Отыскать все корни функции f (x) ?
?

: Найти хотя бы один корень функции f (x) ?
Функция f (x) может вообще не иметь корней.
15

Функция может иметь единственный корень.
Функция может иметь конечное (> 1) количество корней.
16

Функция может иметь бесконечное количество корней.
Функция f (x) = sin x имеет изолированные корни.
Функция f (x) = |2−x|+|x−1|−1 также имеет бесконечное количество корней,
которые заполняют весь числовой промежуток [1; 2].
17

Глава 2
Основы алгоритмизации
Алгоритм
— это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных к искомому резуль- тату.
Алгоритм
— записанная на определенном языке конечная последователь- ность инструкций.
Исполнитель инструкций — ЭВМ, механ. устройство или человек.
Алгоритм управляет работой исполнителя с целью получения результата —
решения поставленной задачи.
Для задания алгоритма необходимо описать следующие его элементы:
• набор объектов, составляющих совокупность возможных исходных дан- ных, промежуточных и конечных результатов;
• правило начала;
• правило непосредственной переработки информации
(описание последовательности действий);
• правило окончания;
• правило извлечения результатов.
Качество алгоритма определяется его свойствами.
18

2.1
Свойства алгоритмов
1

. Массовость.
2

. Результативность.
3

. Определенность (детерминированность).
4

. Дискретность.
2.2
Способы описания алгоритмов
Словесный и словесно-формульный:
Вычислить x = x + c, где x =
a/2 − 3c, если a > b,
2b + 3c,
если a b,
a, b, c — заданные переменные целого типа.
1. Начало;
2.
Список данных:
a, b, c - целый;
x - вещественный;
3.
Ввод(a, b, c);
4.
Вывод(a, b, c);
5.
Если (a > b) то x := a/2 - 3c;
6.
иначе x := 2b + 3c;
7.
x := x + c;
8.
Вывод(x);
9. Конец.
Псевдокод
— язык описания алгоритмов, использующий ключевые слова языков программирования, но опускающий подробности и специфический синтаксис.
19

Структурный или блок-схемный
— графический документ, дающий представление о порядке работы алгоритма.
С помощью граф-схем
Граф
— это совокупность объектов и связей между ними. Объекты — вер- шины (узлы) графа; связи — дуги (рёбра) графа.
С использованием специальных алгоритмических языков.
Вычисление площади треугольника (Pascal)
1
program Triangle;
2
var a, b, c, p, S : Real;
3
begin
4
Write(’Введите длины сторон треугольника [> ’);
5
ReadLn(a, b, c);
6
p := a + b + c;
7
WriteLn(’Периметр треугольника равен ’, p:5:2);
8
p := p / 2;
(* полупериметр треугольника *)
9
S := Sqrt(p * (p - a) * (p - b) * (p - c));
10
WriteLn(’Площадь треугольника равна ’, S:5:2);
11
ReadLn;
12
end.
20

Описание синтаксиса или структуры языка программирования называется грамматикой языка.
Метаязык
— язык, на котором ведется исследование некоторого другого языка, называемого предметным языком или языком-объектом.
Паскаль, Pascal (1968 г., Никлаус Вирт).
Никлаус Вирт (1934) — швейцарский учёный, специалист в области инфор- матики, один из известнейших теоретиков в области разработки языков про- граммирования, профессор компьютерных наук. Ведущий разработчик языков
Паскаль, Модула-2, Оберон.
Для определения синтаксиса языка Паскаль Н. Вирт использовал два разных метаязыка — БНФ-нотацию и синтаксические диаграммы.
21

2.3
Форма Бэкуса—Наура
Форма Бэкуса–Наура (БНФ)
— формальная система описания синтак- сиса, в которой одни синтаксические категории последовательно определя- ются через другие категории.
Расширенная форма Бэкуса–Наура (РБНФ)
отличается более «ём- кими» конструкциями, позволяющими сократить в объеме описание син- таксиса (предложена Н. Виртом).
Метасимволы — символы метаязыка.
Пример БНФ и РБНФ.
Определим идентификатор, как последователь- ность букв и цифр, начинающуюся с буквы:
Пример БНФ
<буква> :: = А|В|С|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|
W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
<цифра> :: = 0|1|2|3|4|5|6|7|8|9
<идентификатор> ::= <буква> | <идентификатор><буква> |
<идентификатор><цифра>
Пример РБНФ
буква = "A"|"B"|"C"|"D"|"E"|"F"|"G"|"H"|"I"|"J"|"K"|"L"|"M"|"N"|
"O"|"P"|"Q"|"R"|"S"|"T"|"U"|"V"|"W"|"X"|"Y"|"Z"|"a"|"b"|
"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|"l"|"m"|"n"|"o"|"p"|
"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z".
цифра = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".
идентификатор = буква {буква | цифра}.
2.3.1
Терминальные и нетерминальные символы
Терминальные символы
— минимальные элементы грамматики, не име- ющие собственной грамматической структуры — символы клавиатуры (ис- пользуемые в языке) и служебные слова.
Для РБНФ терминальные символы — это либо предопределенные иденти- фикатора, либо последовательности символов в кавычках и апострофах.
22

Нетерминальные символы
— элементы грамматики, имеющие собствен- ные имена и структуру.
Каждый нетерминальный символ состоит из одного и более терминальных и/или нетерминальных символов, сочетание которые определяется прави- лами грамматики.
Структура отдельного правила:
N ::= P
N — нетерминальный символ;
P — последовательность терминальных и нетерминальных символов;
::= — «есть по определению» (символ метаязыка). В РБНФ — символ =.
Полное описание грамматики представляет собой набор правил, который по- следовательно определяет все нетерминальные символы грамматики через ком- бинации терминальных символов.
В РБНФ конец правила обозначают точкой.
В БНФ нетерминальные символы пишутся внутри знаков разметки (угловых скобок):
<...>.
23

2.3.2
Выражения
Конкатенация.
Правило вида
A ::= BC
(A = BC)
обозначает, что нетерминал A состоит из двух символов — B и C.
Если соединяемые символы обозначаются более чем одним знаком, то они раз- деляются одним или более пробельными символами (пробелы, переводы строк,
табуляции). Например,
Присваивание ::= Переменная := Выражение или РБНФ
Присваивание = Переменная ":=" Выражение.
Выбор (альтернатива).
Правило вида
A ::= B|C|D
(РБНФ: A = B|C|D.)
обозначает, что нетерминал A может состоять либо из B, либо из C, либо из D.
Условное вхождение.
Правило
A ::= [B]
(РБНФ: A = [B].)
обозначает, что нетерминал A либо является пустым, либо состоит из B.
Повторение.
Правило
A ::= {B}
(РБНФ: A = {B}.)
обозначает конкатенацию любого числа символов B: либо B, либо BB, либо BBB
и т. д.
Правило
A ::= B{B}
(РБНФ: A = B{B}.)
используется, если требуется, чтобы A представлял собой либо B, либо произ- вольное число B, но не мог быть пустым.
24

Группировка элементов (РБНФ).
Круглые скобки применяются для группировки элементов при формировании сложных выражений. Например, правило
A = (B|C)(D|E).
обозначается, что A состоит из двух символов, первым из которых является либо B, либо C, вторым — D, либо E.
Записать все возможные последовательности, определенные правилами
A = (B|C)(D|E).;
A = (B|C|D)(E|F).;
Пример БНФ.
Определение синтаксической конструкции
<целое число>
без знака как последовательность цифр:
< целое число > ::=
< цифра > {< цифра >}
< цифра > ::= 0|1|2|3|4|5|6|7|8|9
Определение синтаксической конструкции <целое число> как целое без знака,
перед которым может стоять знак (плюс или минус):
< целое число > ::= [< знак >] < цифра > {< цифра >}
< знак > ::= +|-
25

2.4
Синтаксические диаграммы
Синтаксическая диаграмма
— графическое представление синтаксиса языка программирования.
Кружки — терминальные символы.
Прямоугольники — нетерминальные символы.
<цифра> и <буква>
<целое без знака>
Замечание:
о БНФ-нотации см. также «Лекции по курсу “Информатика”»
(автор Н. В. Петровская).
26

Глава 3
Алфавит и словарь языка Pascal
Алфавит
— набор допустимых символов языка программирования, кото- рые можно использовать для записи программы.
Язык Pascal оперирует со следующим набором символов:
а) буквы латинского алфавита (A..Z, a..z), при этом большие и малые бук- вы не различаются;
б) арабские цифры (0..9);
в) символ подчеркивания (_);
г) символы разделители:
пробелы, комментарии и концы строк.
Комментарии могут содержать любые символы, заключенные в ограничи- вающие скобки: (* *) или { }.
д) специальные символы:

/
+

:= .
, ;
:
= <> @ $
< <= > >=
(
) [ ] .. {
}
#
Составные спецзнаки типа <= (не больше) и <> (не равно) трактуются компилятором как один спецзнак.
С помощью перечисленных символов формируются:
— идентификаторы;
— числа;
— выражения;
— строки символов;
— метки.
27

3.1
Идентификаторы
Последовательность букв, знаков подчеркивания и цифр, начинающаяся с буквы или со знака подчеркивания, называется идентификатором
Индентификаторы бывают стандартные и определенные пользователем.
К идентификаторам, определенным пользователем, относятся имена, которые применяются для обозначения различных конструкций языка: констант, пере- менных, типов, границ, процедур и функций.
Длина имени может быть любой, но сравнение имен производится по первым
63 символам. Не допускается использования для написания имен специальных символов и символов разделителей.
Правильные имена a alpha10
x1x2 x_2 _x
Ошибочные имена
R-3 10a 4 label. x 2
Имена переменных используются для обозначения исходных данных и ре- зультатов вычислений. Соответствующее исходное данное или результат вы- числения называется значением переменной.
(об именах идентификаторов). Для обозначения констант, переменных и массивов рекомендуется использовать короткие названия, состоящие из 4–6
букв. Применение коротких имен позволит избежать синтаксических ошибок при последующем написании программы. Имя должно нести смысловую на- грузку, что позволяет улучшить читаемость алгоритма, например:
Radius,
Vysota и т. п.
вместо x,
y.
Возьмите себе за правило использовать буквы i, j, k для обозначения парамет- ров цикла, а буквы m, n — для обозначения интервалов изменения параметра цикла for i
:=1 to n
do Readln(a[
i
]);
Некоторые стандартные идентификаторы представляют собой имена предопределенных операций, например ReadLn (Read Line — читать строку) или
WriteLn (Write Line — вывести строку). Другие являются именами предопре- деленных типов данных, например Real (действительное число). Стандартные
28
идентификаторы могут быть переопределены и использованы программистом для иных целей, однако, делать этого не рекомендуется. Если переопределить стандартный идентификатор, Pascal больше не сможет использовать его по пер- воначальному назначению. Пример стандартных идентификаторов:
Abs
Sin
Cos
Exp
Delete
ReadLn
Зарезервированные
(ключевые, служебные)
слова
— это некоторое мно- жество имен, зарезервированных в языке для написания операторов и дру- гих конструкций.


¨
©
Зарезервированные слова переопределять нельзя.
Например, ключевыми словами в Pascal являются and array begin end const for if while with.
(о стиле написания имен идентификаторов). Компилятор Turbo Pascal не различает строчных и прописных букв. Это означает, что зарезервированное слово const можно написать и как Const, и как CONST, или как CoNsT. Однако,
хорошим стилем программирования являются следующие правила:
— зарезервированные слова писать строчными буквами;
— пользовательские идентификаторы — прописными и строчными. Первая бук- ва каждого идентификатора всегда прописная. В идентификаторе, состоящем из двух или более слов (например, RadToDeg), первая буква каждого слова прописная.
. В редакторе Turbo Pascal зарезервированные слова и стандартные иденти- фикаторы окрашены в разные цвета. Как правило, белый цвет используется для зарезервированных слов и стандартных директив, а желтый — для стан- дартных идентификаторов.
Алфавит языка, ключевые слова, а также имена стандартных идентифи- каторов языка входят в словарь языка
29

3.2
Числа
Числа, обозначающие целые и вещественные значения, записываются в Pascal в десятичной системе счисления. Перед любым числом может стоять знак «+»
или «−». В вещественном числе целая часть от дробной отделается точкой.
Например,
• целые числа:
0
-5
• числа с фиксированной точкой:
0.13 3.1415
+1.88
-0.37
• числа с плавающей точкой:
5E-8 9.422E+08 1E10
Вещественные числа, содержащие десятичную точку, должны иметь перед ней и после нее по крайней мере по одной цифре.
Числа с плавающей точкой имеют мантиссу (число с фиксированной точ- кой) и масштабный множитель (порядок). Например, число 9.422E+08
означает, что число 9.422 надо умножить на 10 8
. Порядок — это целое двух- разрядное число со знаком. Пробелы внутри чисел недопустимы. Если порядок положительный, то знак «+» можно опускать.
Примеры написания чисел:
Неправильно
Тип ошибки
Правильно
0,2
запятая вместо точки
0.2 1 000
число содержит пробел
1000
E3
нет мантиссы перед E
1E3
.08
нет целой части
0.08 120.
нет дробной части
120.0 или 1.2E2 30

3.3
Выражения
Переменные и числа — простейшие частные случаи выражений. Более слож- ные выражения строятся из чисел и переменных с помощью знаков арифме- тических операций, а также с помощью круглых скобок и некоторых функ- ций.
Примеры выражений sin(x+Pi)
Sqrt(5/17)
(x+y)*(x+z)*(y+z)
Знак операции умножения «*» опускать или заменять точкой нельзя.
Нельзя размещать два знака операций рядом
1
:
Неправильно
Правильно
2*-2.5,
x1/-x2 2*(-2.5),
x1/(-x2)
При вычислении значений выражений действуют обычные правила старшин- ства операций (см. таблицу приоритетов на с.
51
).
В выражении могут быть использованы следующие функции (см. также п.
5.4
)
Математические функции
Имя функции
Возвращает
Abs(x)
|x|
Sqr(x)
x
2
Sqrt(x)

x, где x > 0,0
Sin(x), Cos(x) sin x, cos x
(аргумент — радианная мера угла)
ArcTan(x)
arctg x
(аргумент — радианная мера угла)
Exp(x)
e x
, где e = 2,71828 . . .
Ln(x)
ln x, где x > 0,0
Pi значение числа π
Аргумент любой функции всегда заключается в скобки.
Напомним, что arctg x — угол в радианах, удовлетворяющий условию x = tg y,
где −π/2 < y < π/2.
Функция Sqr(x) используется для сокращения записи квадратов громоздких выражений. Например выражение (x−

2+2,17)
2
на Pascal удобнее записывать
1
В Turbo Pascal 7.0 можно размещать два знака операций рядом, но лучше этого не делать.
31
в виде
Sqr(x - Sqrt(a) + 2.17)
вместо
(x - Sqrt(a) + 2.17) * (x - Sqrt(a) + 2.17)
Совет. Не стоит использовать функцию Sqr для вычисления простых выраже- ний, например, a
2
. Во-первых, это более громоздко и добавляет новых скобок в выражение, во-вторых, можно легко перепутать с функцией Sqrt.
Выражение
Pascal
Символов Скобок a
2
a*a;
2 0
Sqr(a);
6 0
π(a
2
+ b
2
) cos a
2
Pi*(a*a+b*b)*cos(a*a)
22 2 пары
Pi*(Sqr(a)+Sqr(b)*cos(Sqr(a))
30 5 пар
В языке Pascal нет операции возведения в произвольную степень, по- этому, например, x
3
можно записать в виде x * x * x или Sqr(x) * x и т.д.
Для изображения произвольной степени n положительного числа x исполь- зуют экспоненциально-логарифмическую запись. Например, x n
записывается следующим образом x
n
: e n ln x или
Exp(n * Ln(x)).
. Прямое вычисление степеней высоких порядков в языках программирова- ния используется редко. Обычно в этих целях применяют рекуррентные соот- ношения, т. е. формулы, в которых каждый следующий член выражается через предыдущий. Например,
x n
= x n−1
x.
3.4
Строка символов
Строка символов
— это последовательность символов, заключенная в апо- строфы. Например,
’*’
’Begin’
’Котик’
’54’
32

3.5
Комментарии
Комментарий
— любая последовательность символов, заключенная меж- ду знаками «{» и «}» (или «(*» «*)»).
Комментарий может занимать несколько строк программы. Ограничений на его длину нет. Комментарии включаются в программу, чтобы сделать ее более доступной для понимания и модификации. Компилятор игнорирует все ком- ментарии, поэтому их наличие не уменьшает эффективности программы.
Примеры видов комментариев
{ это комментарий }
(* это комментарий *)
{ один комментарий (* внутри другого *) комментария }
// однострочный комментарий в Delphi
Пример 5.1. Хорошим стилем программирования является присутствие в про- грамме некоторой «шапки», содержащей информацию, например, в виде
— имя автора программы;
— дата текущей версии;
— краткое описание того, что делает данная программа.
Пример «шапки» программы program Triangle;
{ Иван Иванов - 01.09.2010
Программа вычисляет площадь треугольника по формуле Герона }
Пример 5.2. Комментарии удобно вставлять и при описании переменных.
Пример комментариев var a, b, c : Real; (* длины сторон треугольника *)
STrg
: Real; (* площадь треугольника *)
Ограничение.
Первым символом комментария не может быть знак доллара «$»
,
так как конструкция «{$» или «(*$» будет восприниматься Pascal как начало директивы, которую программист передает компилятору.
33

Глава 4
Типы данных языка Pascal
Тип данных определяет множество значений, которые может принимать та или иная переменная (Число различных значений, входящих в тип T, называется мощностью T. [?, с. 24]), и множество операций, которые можно к ним приме- нить.
Три группы типов данных
(Turbo Pascal 7.0):
— простые (скалярные) типы;
— структурированные типы — типы, которые базируются на скалярных ти- пах (запись, массив, множество, файл);
— ссылочные — данные этих типов создаются во время выполнения програм- мы, причем их размер и вид могут изменяться (списки, очереди, деревья и проч.).
Статическая типизация
— приём, при котором переменная, параметр подпрограммы, возвращаемое значение функции связывается с типом в мо- мент объявления и тип не может быть изменён позже.
Статически типизированные языки: Ада, Си++, Паскаль.
Динамическая типизация
— приём, при котором переменная связыва- ется с типом в момент присваивания значения, а не в момент объявления переменной. В различных участках программы одна и та же переменная может принимать значения разных типов.
Динамически типизированные языки:
Smalltalk, Python, Руби, PHP, JavaScript, Perl.
34

4.1
Простые типы данных
Целочисленный, вещественный, символьный,
логический, интервальный, перечисляемый.
4.1.1
Порядковые типы
Конечное число возможных значений, которые можно каким-либо образом упо- рядочить (а значит можно, каждому из них можно сопоставить некоторое целое число — порядковый номер значения).
Порядковые операции:
Ord порядковый номер элемента
Succ следующий элемент
Pred предшествующий элемент inc увеличить на единицу dec уменьшить на единицу
Low возвращают наименьшее значение величин данного типа
High возвращают наибольшее значение величин данного типа
Порядковые типы (ordinal): целочисленный, символьный, логический, пе- речисляемый и интервальный.
4.1.2
Вещественные типы
Большое (бесконечное) количество возможных значений не позволяет каждому из вещественным чисел сопоставить целое число — порядковый номер.
1.5 1.51 1.511 1.512 . . .
35

Операции сравнения
(применимы ко всем порядковым и вещественным типам)
Операция
Действие
Тип результата
=
равенство логический
<>
неравенство логический
<
меньше логический
>
больше логический
<=
меньше или равно логический
>=
больше или равно логический
4.1.3
Целочисленные типы
Целые числа
— это натуральные числа, числа, противоположные нату- ральным и число 0.
35.0 — неправильно
;
35 — правильно
Значение предопределенной константы
MaxInt соответствует наибольшему зна- чению Integer . Самое маленькое значение Integer будет равно -MaxInt - 1.
Целочисленные типы Turbo Pascal 7.0
Тип
Допустимые значения
Формат
ShortInt
(короткое целое) −128..127 1 байт со знаком
Integer
(целое)
−32 768..32 767 2 байта со знаком
LongInt
(длинное целое)
−2 147 483 648..2 147 483 647 4 байта со знаком
Byte
(длиной в байт)
0..255 1 байт без знака
Word
(длиной в слово)
0..65 535 2 байта без знака
36

4.1.4
Операции над целыми числами
Вывод на печать (Write). Ввод с клавиатуры (Read)
Операции сравнения (>
<
=. . . )
+
-
*
/
div mod
7 div 2 = 3,
8 div 2 = 4,
1 div 5 = 0.
7 mod 2 = 1,
8 mod 2 = 0,
1 mod 5 = 1.
Результаты операций a div 0
и a mod 0
считаются неопределенными.
Пример.
a mod b = 0.
a mod 2 = 0
Odd(a)
(function Odd(a: Longint): Boolean).
Выражение Результат
15 / 3 5.0 15 div 3 5
Пример.
17 2
16 8 ← 17 div 2 1 ← 17 mod 2 4.1.5
Вещественные типы Turbo Pascal 7.0
Тип
Допустимые значения
Точность
Формат
Real
±(2.9 · 10
−39
..1.7 · 10
+38
)
11–12 знаков 6 байтов
Single
±(1.5 · 10
−45
..3.4 · 10
+38
)
7–8 знаков
4 байта
Double
±(5.0 · 10
−324
..1.7 · 10
+308
)
15–16 знаков 8 байтов
Extended
±(3.4 · 10
−4932
..1.1 · 10
+4932
)
19–20 знаков 10 байтов
37

4.1.6
Операции над вещественными числами
Вывод на печать. Ввод с клавиатуры
Операции сравнения
Вещественные числа x и y равны с точностью ε, если |x − y|
ε.
Пример 1.
Сравним два числа x = 0,05; y = 0.0501. Обратим внимание, что из разность |x − y| = 0.0001.
Сравнение вещественных чисел
1
var x, y: Real;
2
begin
3
x := 0.05;
y := 0.0501;
4
Writeln(x:4:2, ’ = ’, y:6:4, ’? ’);
5
Writeln(x = y);
6
Writeln(’0.001
’, abs(x - y) <= 0.001);
7
Writeln(’0.0001 ’, abs(x - y) <= 0.0001);
8
Writeln(’0.00001 ’, abs(x - y) <= 0.00001);
9
Writeln(’|x - y| = ’, abs(x - y));
10
end.
Результат в Borland Pascal 7.0:

1   2   3   4   5   6   7   8   9
написать администратору сайта