Слайд 104/19/2020
Романькова Т.Л.
Лекция №2 по курсу «Информатика»
Основы алгоритмизации.
Типы алгоритмов. Основные
элементы языка программирования.
Слайд 204/19/2020
Романькова Т.Л.
Понятие и свойства алгоритма
Алгоритм – это набор точных предписаний,
последовательное выполнение которых однозначно приводит задачу к решению за конечное
число шагов.
Алгоритм обладает следующими свойствами:
Слайд 304/19/2020
Романькова Т.Л.
Детерминированность(определенность,точность) – четкость и ясность всех предписаний: исполнителю алгоритма
должно быть точно известно, какая команда алгоритма выполняется следующей («Уходя,
гасите свет»)
Результативность – способность алгоритма приводить к решению задачи за конечное число шагов
дискретность – предписание представляет собой последовательность четко выраженных отдельных команд, причем, выполнив одну команду, исполнитель выполняет другую команду, промежуточных состояний нет
массовость (универсальность) – применимость алгоритма к решению задач определенного класса, чем шире этот класс, тем ценнее алгоритм
Слайд 404/19/2020
Романькова Т.Л.
Существуют следующие способы записи алгоритмов:
словесно-формульная запись
графическая запись (схема алгоритма,
иначе, графическая схема алгоритма, блок-схема)
запись на конкретном языке программи-рования
Слайд 504/19/2020
Романькова Т.Л.
Словесный способ записи алгоритмов представляет собой описание последовательных этапов
обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Пример.
Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Евклида).
Слайд 604/19/2020
Романькова Т.Л.
Алгоритм может быть следующим:
задать два числа
если числа
равны, то взять любое из них в качестве ответа и
остановиться, в противном случае продолжить выполнение алгоритма;
определить большее из чисел;
заменить большее из чисел разностью большего и меньшего из чисел;
повторить алгоритм с шага 2.
Слайд 704/19/2020
Романькова Т.Л.
Графическая схема алгоритма состоит из отдельных блоков, связанных линиями
потоков
Каждый блок описывает конкретный шаг алгоритма
Схемы алгоритмов должны соответствовать действующим
стандартам на оформление схем алгоритмов, программ, данных и систем
[ГОСТ 19.701-90].
Ниже приводятся некоторые символы, определенные в стандарте и рекомендуемые к использованию в графических схемах алгоритмов.
Слайд 804/19/2020
Романькова Т.Л.
Процесс
Символ отображает функцию обработки данных любого вида.
Предопределенный процесс
Символ отображает
предопределенный процесс, состоящий из одной или нескольких операций или шагов
программы, которые определены в другом месте (в подпрограмме, модуле).
Слайд 904/19/2020
Романькова Т.Л.
Данные
Символ отображает данные, носитель данных не определен.
Решение
Символ
отображает решение или функцию переключательного типа, имеющую один вход и
ряд альтернативных выходов, один и из которых может быть активизирован после вычисления условий, определенных внутри этого символа.
Слайд 1004/19/2020
Романькова Т.Л.
Линия
Символ отображает поток данных или управления
Соединитель
Символ отображает
выход в часть схемы и вход из другой части этой
схемы и используется для обрыва линии и продолжения ее в другом месте. Соответствующие символы соединители должны содержать одно и то же уникальное обозначение.
Слайд 1104/19/2020
Романькова Т.Л.
Терминатор
Символ отображает начало или конец схемы программы, внешнее
использование и источник или пункт назначения данных.
Комментарий
Слайд 1204/19/2020
Романькова Т.Л.
Текст, описывающий функцию символа, следует располагать внутри данного символа.
Если текст не помещается внутри символа, следует использовать символ комментария.
При
необходимости блоки в схеме можно нумеровать (например, чтобы иметь возможность ссылаться на тот или иной символ) слева вверху в разъеме символа. Например,
Слайд 1304/19/2020
Романькова Т.Л.
Правила выполнения соединений:
Стандартное направление линий потока – слева направо
и сверху вниз
Если направление потока отличается от стандартного, это направление
указывается стрелками
В схемах следует избегать пересечения линий
Линии в схемах должны подходить к символу либо слева, либо сверху, а выходить либо справа, либо снизу.
Вход в блок и выход из блока следует размещать по центру символа
Слайд 1504/19/2020
Романькова Т.Л.
Типы алгоритмов
Теорема Дейкстра. Алгоритм любой сложности можно реализовать, используя
только три конструкции: следования (линейные), выбора (ветвления) и повторения (циклические).
Линейный - алгоритм, в котором все указанные действия выполняются один раз в том порядке, в котором они записаны.
В схеме линейный алгоритм представляется в виде типовой структуры следование:
Эдсгер Вибе Дейкстра
Слайд 1704/19/2020
Романькова Т.Л.
Например, алгоритм посадки дерева:
Выкопать в земле ямку;
Опустить в ямку
саженец;
Засыпать ямку с саженцем землей;
Полить саженец водой.
Слайд 1804/19/2020
Романькова Т.Л.
начало
Выкопать в земле ямку
Опустить в ямку саженец
Засыпать ямку с
саженцем землей
Полить саженец водой
конец
Слайд 1904/19/2020
Романькова Т.Л.
В схеме разветвляющийся алгоритм представляется в виде типовых структур
Ветвление и выбор
Разветвляющийся - алгоритм,
в котором некоторые действия выполняются один раз или не выполняются в зависимости от заданного условия.
Слайд 2004/19/2020
Романькова Т.Л.
Ветвление
и
выбор
Полная форма
Неполная форма
Слайд 2104/19/2020
Романькова Т.Л.
Если друг на день рожденья
Пригласил тебя к себе,
То оставь
подарок дома –
Пригодится самому…
Слайд 2304/19/2020
Романькова Т.Л.
Жена отправляет программиста в магазин.
Купи батон колбасы и если
будут яйца купи десяток.
Программист - продавцу.
- У вас яйца есть?
-
Есть!
- ОК. Мне 10 батонов колбасы.
Слайд 2404/19/2020
Романькова Т.Л.
В схеме циклический алгоритм представляется в виде типовой структуры
цикл:
Циклический - алгоритм, в котором некоторая последовательность действий может выполняться
несколько раз в зависимости от заданного условия.
Слайд 2604/19/2020
Романькова Т.Л.
Алгоритм поиска Золушки:
Слайд 2704/19/2020
Романькова Т.Л.
Итак, алгоритмы делятся на
линейные
разветвляющиеся
циклические
( можно также выделить в отдельный тип смешанные).
Слайд 2804/19/2020
Романькова Т.Л.
Алгоритмы могут классифицироваться и по другому направлению.
Комбинаторные алгоритмы:
Общие комбинаторные алгоритмы (например, генерация случайных чисел )
Алгоритмы
на графах
Алгоритмы поиска
Алгоритмы сортировки
Алгоритмы слияния
Алгоритмы работы со строками
Слайд 2904/19/2020
Романькова Т.Л.
Алгоритмы сжатия данных
Криптографические алгоритмы
Цифровая обработка
сигналов
И т.д.
Теоретико-числовые алгоритмы
Слайд 3004/19/2020
Романькова Т.Л.
Основные элементы языка программирования Delphi ( в версиях 1-6
– Object Pascal)
Паскаль был создан …
Object Pascal — результат
развития языка Турбо Паскаль, который, в свою очередь, развился из языка Паскаль.
Слайд 3104/19/2020
Романькова Т.Л.
Внимание, вопрос:
Кто был автором языка программирования
Pascal?
Блез Паскаль
Билл Гейтс
Слава КПСС
Никлаус Вирт
Леди Ада Лавлейс
Леди Гага
Слайд 3204/19/2020
Романькова Т.Л.
Язык Паскаль был создан Никлаусом Виртом в 1968-69 годах.
Назван в
честь выдающегося французского математика, физика, литератора и философа Блеза Паскаля, который
создал первую в мире механическую машину, складывающую два числа.
Слайд 3304/19/2020
Романькова Т.Л.
Имя «Дельфи» (Delphi) возникло как тестовое имя для отдельного
полусамостоятельного проекта Borland - визуальной среды разработки для Windows, написанной
на языке программирования Borland Object Pascal. Это имя родилось в середине 1993.
Было принято решение сделать средства для соединения и работы с базами данных центральной частью нового Pascal-продукта.
Есть такая СУБД – Oracle Database. У разработчиков возникла ассоциация «Дельфийский оракул» . И было предложено название Delphi.
Дельфы — древнегреческий город (латинское написание — Delphi).
Оракул - предсказатель будущего, а также человек, все суждения которого признаются непреложной истиной, откровением.
Слайд 3404/19/2020
Романькова Т.Л.
Почему 10 декабря названо Днем программиста ?
Августа Ада Лавлейс
– первый программист - родилась 10 декабря 1815 года. Она
была единственной дочерью великого английского поэта Джорджа Гордона Байрона (1788 — 1824) и Аннабеллы Байрон, урождённой Милбэнк (1792 — 1860).
Слайд 3504/19/2020
Романькова Т.Л.
Алфавит языка.
Алфавит – совокупность допустимых символов:
буквы – буквы латинского
алфавита, а также знак подчеркивания ( _ );
цифры 0..9;
шестнадцатеричные цифры;
разделители:
исп-ся для отделения др. от друга идентификаторов, чисел, зарезервированных слов.
Можно исп-ть пробел, любой управляющий символ (коды 0.. 31), комментарий;
Слайд 3604/19/2020
Романькова Т.Л.
специальные символы:
знаки пунктуации ({}, =,:=,’ и т.д.);
знаки операций (+, * и т.д. );
зарезервированные слова (
напр., begin, end и др.).
Идентификатор – имя любого объекта программы (переменной, константы, процедуры и др.).
Слайд 3704/19/2020
Романькова Т.Л.
Идентификатор может включать буквы латинского алфавита, цифры и символ
подчеркивания.
Идентификатор не может начинаться с цифры.
Прописные и строчные буквы
в идентификаторах не различаются.
Т.е. напр., Vasja1, VASJA1 и VaSjA1 – это один и тот же идентификатор
Слайд 3804/19/2020
Романькова Т.Л.
Структура программы в консольном приложении.
Консоль — это монитор и
клавиатура, рассматриваемые как единое устройство. Консольное приложение — программа, предназначенная
для работы в операционной системе MS-DOS (или в окне DOS), для которой устройством ввода является клавиатура, а устройством вывода — монитор, работающий в режиме отображения символьной информации (буквы, цифры и специальные знаки).
Консольные приложения удобны как иллюстрации при рассмотрении общих вопросов программирования, когда надо сосредоточиться на сути проблемы,
Слайд 3904/19/2020
Романькова Т.Л.
В программе могут быть следующие разделы:
заголовок программы
раздел объявления используемых
модулей
раздел объявления меток
раздел описаний
раздел объявления констант
раздел объявления типов
раздел объявления переменных
раздел
объявления процедур и функций
тело программы или раздел операторов
( обязательный раздел ).
раздел описаний
Слайд 4004/19/2020
Романькова Т.Л.
Заголовок состоит из зарезервированного слова Program и имени программы,
завершается точкой с запятой. Имя программы может включать буквы, цифры
и символ подчеркивания и не может начинаться с цифры.
Порядок размещения разделов произвольный, но
! в любом месте программы можно использовать лишь элементы , которые были определены ранее по тексту программы или являются стандартными элементами языка.
Слайд 4104/19/2020
Романькова Т.Л.
Тело программы начинается словом Begin и заканчивается словом End
с точкой, которая является признаком конца программы.
В любом месте программы
могут располагаться комментарии. Комментарии заключаются в скобки {} или в скобки вида (* *) и могут занимать произвольное число строк. Они игнорируются компилятором и служат для пояснения текста программы.
Слайд 42Пример.
Программа, вычисляющая произведение двух чисел.
Program Primer;
{Заголовок программы}
uses SysUtils, math; {раздел объявления используемых модулей}
{$Apptype console}
var {раздел объявления переменных}
x,y,p:real;
Write(′Введите два числа′); readln(x,y);
Begin {тело программы}
p:=x*y;
writeln(′ Произведение чисел равно ′,p)
End.
Слайд 4304/19/2020
Романькова Т.Л.
Под типом данных понимается множество допустимых значений этих данных,
а также совокупность операций над ними.
Типы данных.
Раздел объявления типов начинается
зарезервированным словом type, после которого определяются вводимые типы.
Type
<имя типа1>=<определение типа1>;
<имя типа2>=<определение типа2>;
и т.д.
Слайд 4404/19/2020
Романькова Т.Л.
В Object Pascal можно выделить следующие типы данных:
простые;
структурированные;
указатели;
процедурные типы;
объекты.
Слайд 4504/19/2020
Романькова Т.Л.
К простым типам относятся :
целые;
логический;
символьный;
перечисляемый;
тип-диапазон;
вещественные типы.
Слайд 4704/19/2020
Романькова Т.Л.
Вещественные
Слайд 4804/19/2020
Романькова Т.Л.
Для размещения данных типа char требуется 1байт.
Символьный тип.
Обозначается словом Char.
Значениями данных символьного типа могут являться любые символы
из расширенного набора символов для ПЭВМ.
(Каждому символу приписывается целое число или код в диапазоне 0..255. Первая половина символов соответствует стандарту ASCII / American Standart Code for Information Interchange – американский стандартный код для обмена информацией/. Вторая половина символов с кодами 128..255 может меняться на ПЭВМ разных типов).
Слайд 4904/19/2020
Романькова Т.Л.
Тип Boolean представляет собой тип данных, любой элемент которого
может принимать только два значения: True (истина) или False (ложь).
Логический тип.
Для размещения данных типа Boolean требуется 1 байт памяти
Слайд 5004/19/2020
Романькова Т.Л.
Существует 2 способа использования констант:
непосредственное использование значения константы;
использование идентификатора
(имени) константы.
Задание констант именами осуществляется в разделе объявления констант, который
начинается словом Const.
Константы.
Константами называются параметры программы, значения которых не меняются в процессе ее выполнения.
Слайд 5104/19/2020
Романькова Т.Л.
Const
=;
=
2>; и т.д.
Имя константы формируется согласно основному правилу формирования идентификаторов(см.
выше).
Напр., Const Max=1345;
x_2=10.5;
35r, f-47 , вася – недопустимые имена констант.
Слайд 5204/19/2020
Романькова Т.Л.
Константы могут быть целого, вещественного, символьного, логического и строкового
типа.
Целые. В изображении целых к. только знак и цифры. (-45, 509, +35)
Вещественные. В своем изображении могут содержать знак, цифры, десятичную точку, показатель степени - символ Е или е.
Сущ. две формы записи вещ. констант:
а) естественная 10.6 -0.001
б) экспоненциальная 0.107Е+02 -0.1е-02
Слайд 5304/19/2020
Романькова Т.Л.
Строковые и символьные константы.
Строка символов(или строковая константа) – это
последовательность любого, в том числе и равного нулю, количества символов
из стандартного набора символов ПЭВМ, расположенных на одной строке и заключенного в апострофы. Значимое кол-во символов 126.
Строка, состоящая из одного символа, называется символьной константой.
Напр. ' '
' студент группы ТМ-11 '
' f= '
' h '
Слайд 5404/19/2020
Романькова Т.Л.
Переменные.
Переменные — элементы программы, значения которых могут изменяться в
процессе ее выполнения.
Имя переменной придумывает программист.
Слайд 5504/19/2020
Романькова Т.Л.
Имя переменной формируется согласно основному правилу формирования идентификаторов (см.
выше).
Желательно, чтобы имя переменной несло смысловую нагрузку.
Все используемые в
программе переменные должны быть определены с указанием их типов.
Слайд 5604/19/2020
Романькова Т.Л.
Раздел объявления переменных выглядит сл. образом:
Var
:
1>;
:; и т.д.
Напр.
var
x,summa:real;
priznak:boolean;
Переменные размещаются в оперативной памяти ЭВМ и имеют размер в соответствии с объявленным типом.
Слайд 5704/19/2020
Романькова Т.Л.
Операции.
В Object Pascal сущ. след. операции:
арифметические, логические, операции со
строками, операции отношения, операция с битами информации, адресная операция @.
Арифметические
операции (АО) применимы только к величинам целых и вещественных типов.
Слайд 5804/19/2020
Романькова Т.Л.
Существуют следующие Арифметические операции (расположим их в порядке убывания
приоритета):
/ и *
div (целочисленное деление )
mod (остаток от деления целых
чисел )
+ и -
Слайд 5904/19/2020
Романькова Т.Л.
Стандартные функции.
В языке П. существует ряд заранее разработанных подпрограмм-функций,
которые можно использовать как готовые объекты.
Слайд 6004/19/2020
Романькова Т.Л.
Аргумент функции всегда заключается в круглые скобки !
Аргумент ф-й
sin и cos указывается в радианах.
Слайд 6204/19/2020
Романькова Т.Л.
В Паскале нет операции возведения в степень. Поэтому, если
степень простая, то можно поступать, исходя из определения степени. Напр.,
В более сложных случаях для x>0 можно воспользоваться формулой
Слайд 6304/19/2020
Романькова Т.Л.
Если к программе подключить модуль Math, добавив в нее
строку программы
Uses math;
можно использовать следующие функции из этого модуля:
Слайд 6404/19/2020
Романькова Т.Л.
Выражения.
Выражение – это синтаксическая единица языка, определяющая способ вычисления
некоторого значения. Выражения формируются из констант, переменных, функций, знаков операций
и круглых скобок.
Слайд 6504/19/2020
Романькова Т.Л.
Примеры арифметических выражений:
3.5+sqrt(x*x-2) / (ln(x) * ln(x)-b)
( 2 *
sqr(cos(x))-2.5 ) / abs( sin(x*x*x*x) / cos(x*x*x*x)-1.2 ) +
exp(2.3 * ln(fi))
Слайд 6604/19/2020
Романькова Т.Л.
или при подключенном модуле Math
( 2*sqr(cos(x))-2.5 )/abs( tan(x*x*x*x)-1.2 )+power(fi,2.3)