Презентация "Основы алгоритмизации. Типы алгоритмов. Основные элементы языка программирования"
Подписи к слайдам:
Основы алгоритмизации.
Типы алгоритмов. Основные элементы языка программирования.
- Лекция №2 по курсу «Информатика»
- Алгоритм – это набор точных предписаний, последовательное выполнение которых однозначно приводит задачу к решению за конечное число шагов.
- Алгоритм обладает следующими свойствами:
- Детерминированность(определенность,точность) – четкость и ясность всех предписаний: исполнителю алгоритма должно быть точно известно, какая команда алгоритма выполняется следующей («Уходя, гасите свет»)
- Результативность – способность алгоритма приводить к решению задачи за конечное число шагов
- дискретность – предписание представляет собой последовательность четко выраженных отдельных команд, причем, выполнив одну команду, исполнитель выполняет другую команду, промежуточных состояний нет
- массовость (универсальность) – применимость алгоритма к решению задач определенного класса, чем шире этот класс, тем ценнее алгоритм
- Существуют следующие способы записи алгоритмов:
- словесно-формульная запись
- графическая запись (схема алгоритма, иначе, графическая схема алгоритма, блок-схема)
- запись на конкретном языке программи-рования
- Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
- Пример.
- Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Евклида).
- Алгоритм может быть следующим:
- задать два числа
- если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
- определить большее из чисел;
- заменить большее из чисел разностью большего и меньшего из чисел;
- повторить алгоритм с шага 2.
- Графическая схема алгоритма состоит из отдельных блоков, связанных линиями потоков
- Каждый блок описывает конкретный шаг алгоритма
- Схемы алгоритмов должны соответствовать действующим стандартам на оформление схем алгоритмов, программ, данных и систем
- [ГОСТ 19.701-90].
- Ниже приводятся некоторые символы, определенные в стандарте и рекомендуемые к использованию в графических схемах алгоритмов.
- Процесс
- Символ отображает функцию обработки данных любого вида.
- Предопределенный процесс
- Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле).
- Данные
- Символ отображает данные, носитель данных не определен.
- Решение
- Символ отображает решение или функцию переключательного типа, имеющую один вход и ряд альтернативных выходов, один и из которых может быть активизирован после вычисления условий, определенных внутри этого символа.
- Линия
- Символ отображает поток данных или управления
- Соединитель
- Символ отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линии и продолжения ее в другом месте. Соответствующие символы соединители должны содержать одно и то же уникальное обозначение.
- Терминатор
- Символ отображает начало или конец схемы программы, внешнее использование и источник или пункт назначения данных.
- Комментарий
- Текст, описывающий функцию символа, следует располагать внутри данного символа.
- Если текст не помещается внутри символа, следует использовать символ комментария.
- При необходимости блоки в схеме можно нумеровать (например, чтобы иметь возможность ссылаться на тот или иной символ) слева вверху в разъеме символа. Например,
- 3
- Правила выполнения соединений:
- Стандартное направление линий потока – слева направо и сверху вниз
- Если направление потока отличается от стандартного, это направление указывается стрелками
- В схемах следует избегать пересечения линий
- Линии в схемах должны подходить к символу либо слева, либо сверху, а выходить либо справа, либо снизу.
- Вход в блок и выход из блока следует размещать по центру символа
- Теорема Дейкстра. Алгоритм любой сложности можно реализовать, используя только три конструкции: следования (линейные), выбора (ветвления) и повторения (циклические).
- действие
- действие
- действие
- Линейный - алгоритм, в котором все указанные действия выполняются один раз в том порядке, в котором они записаны.
- В схеме линейный алгоритм представляется в виде типовой структуры следование:
- Эдсгер Вибе Дейкстра
- Начало
- Конец
- Действие 1
- Действие n
- …
- Например, алгоритм посадки дерева:
- Выкопать в земле ямку;
- Опустить в ямку саженец;
- Засыпать ямку с саженцем землей;
- Полить саженец водой.
- начало
- Выкопать в земле ямку
- Опустить в ямку саженец
- Засыпать ямку с саженцем землей
- Полить саженец водой
- конец
- В схеме разветвляющийся алгоритм представляется в виде типовых структур
- Ветвление и выбор
- Разветвляющийся - алгоритм, в котором некоторые действия выполняются один раз или не выполняются в зависимости от заданного условия.
- Ветвление и выбор
- условие
- действие
- Действие 1
- Действие 2
- условие
- действие1
- действие2
- действие3
- ключ
- Полная форма
- Неполная форма
- Если друг на день рожденья Пригласил тебя к себе, То оставь подарок дома – Пригодится самому…
- Если пригласил друг
- Нет
- Да
- Оставь дома подарок
- Подъехал Иван Царевич к камню
- Направо пойдешь?
- Нет
- Да
- Голову сложишь
- Коня потеряешь
- Жена отправляет программиста в магазин.
- Купи батон колбасы и если будут яйца купи десяток.
- Яйца есть
- Купить 1 батон
- колбасы
- Купить 10
- нет
- да
- Программист - продавцу. - У вас яйца есть? - Есть! - ОК. Мне 10 батонов колбасы.
- В схеме циклический алгоритм представляется в виде типовой структуры цикл:
- Циклический - алгоритм, в котором некоторая последовательность действий может выполняться несколько раз в зависимости от заданного условия.
- Начало
- Встретить девушку
- Примерить ей туфельку
- Подошла?
- Золушка найдена!
- Конец
- Распрощаться с девушкой
- Нет
- Да
- Алгоритм поиска Золушки:
- Итак, алгоритмы делятся на
- линейные
- разветвляющиеся
- циклические
- ( можно также выделить в отдельный тип смешанные).
- Алгоритмы могут классифицироваться и по другому направлению.
- Комбинаторные алгоритмы:
- Общие комбинаторные алгоритмы (например, генерация случайных чисел )
- Алгоритмы на графах
- Алгоритмы поиска
- Алгоритмы сортировки
- Алгоритмы слияния
- Алгоритмы работы со строками
- Алгоритмы сжатия данных
- Криптографические алгоритмы
- Цифровая обработка сигналов
- И т.д.
- Теоретико-числовые алгоритмы
- Паскаль был создан …
- Object Pascal — результат развития языка Турбо Паскаль, который, в свою очередь, развился из языка Паскаль.
- Внимание, вопрос:
- Кто был автором языка программирования Pascal?
- Блез Паскаль
- Билл Гейтс
- Слава КПСС
- Никлаус Вирт
- Леди Ада Лавлейс
- Леди Гага
- Язык Паскаль был создан Никлаусом Виртом в 1968-69 годах.
- Назван в честь выдающегося французского математика, физика, литератора и философа Блеза Паскаля, который создал первую в мире механическую машину, складывающую два числа.
- Имя «Дельфи» (Delphi) возникло как тестовое имя для отдельного полусамостоятельного проекта Borland - визуальной среды разработки для Windows, написанной на языке программирования Borland Object Pascal. Это имя родилось в середине 1993.
- Было принято решение сделать средства для соединения и работы с базами данных центральной частью нового Pascal-продукта.
- Есть такая СУБД – Oracle Database. У разработчиков возникла ассоциация «Дельфийский оракул» . И было предложено название Delphi.
- Дельфы — древнегреческий город (латинское написание — Delphi).
- Оракул - предсказатель будущего, а также человек, все суждения которого признаются непреложной истиной, откровением.
- Почему 10 декабря названо Днем программиста ?
- Августа Ада Лавлейс – первый программист - родилась 10 декабря 1815 года. Она была единственной дочерью великого английского поэта Джорджа Гордона Байрона (1788 — 1824) и Аннабеллы Байрон, урождённой Милбэнк (1792 — 1860).
- Алфавит языка.
- Алфавит – совокупность допустимых символов:
- буквы – буквы латинского алфавита, а также знак подчеркивания ( _ );
- цифры 0..9;
- шестнадцатеричные цифры;
- разделители: исп-ся для отделения др. от друга идентификаторов, чисел, зарезервированных слов.
- Можно исп-ть пробел, любой управляющий символ (коды 0.. 31), комментарий;
- специальные символы:
- знаки пунктуации ({}, =,:=,’ и т.д.);
- знаки операций (+, * и т.д. );
- зарезервированные слова ( напр., begin, end и др.).
- Идентификатор – имя любого объекта программы (переменной, константы, процедуры и др.).
- Идентификатор может включать буквы латинского алфавита, цифры и символ подчеркивания.
- Идентификатор не может начинаться с цифры.
- Прописные и строчные буквы в идентификаторах не различаются.
- Т.е. напр., Vasja1, VASJA1 и VaSjA1 – это один и тот же идентификатор
- Структура программы в консольном приложении.
- Консоль — это монитор и клавиатура, рассматриваемые как единое устройство. Консольное приложение — программа, предназначенная для работы в операционной системе MS-DOS (или в окне DOS), для которой устройством ввода является клавиатура, а устройством вывода — монитор, работающий в режиме отображения символьной информации (буквы, цифры и специальные знаки).
- Консольные приложения удобны как иллюстрации при рассмотрении общих вопросов программирования, когда надо сосредоточиться на сути проблемы,
- В программе могут быть следующие разделы:
- заголовок программы
- раздел объявления используемых модулей
- раздел объявления меток
- раздел описаний
- раздел объявления констант
- раздел объявления типов
- раздел объявления переменных
- раздел объявления процедур и функций
- тело программы или раздел операторов
- ( обязательный раздел ).
- раздел описаний
- Заголовок состоит из зарезервированного слова Program и имени программы, завершается точкой с запятой. Имя программы может включать буквы, цифры и символ подчеркивания и не может начинаться с цифры.
- Порядок размещения разделов произвольный, но
- ! в любом месте программы можно использовать лишь элементы , которые были определены ранее по тексту программы или являются стандартными элементами языка.
- Тело программы начинается словом Begin и заканчивается словом End с точкой, которая является признаком конца программы.
- В любом месте программы могут располагаться комментарии. Комментарии заключаются в скобки {} или в скобки вида (* *) и могут занимать произвольное число строк. Они игнорируются компилятором и служат для пояснения текста программы.
- Пример.
- Программа, вычисляющая произведение двух чисел.
- Program Primer; {Заголовок программы}
- uses SysUtils, math; {раздел объявления используемых модулей}
- {$Apptype console}
- var {раздел объявления переменных}
- x,y,p:real;
- Write(′Введите два числа′); readln(x,y);
- Begin {тело программы}
- p:=x*y;
- writeln(′ Произведение чисел равно ′,p)
- End.
- Под типом данных понимается множество допустимых значений этих данных, а также совокупность операций над ними.
- Типы данных.
- Раздел объявления типов начинается зарезервированным словом type, после которого определяются вводимые типы.
- Type
- <имя типа1>=<определение типа1>;
- <имя типа2>=<определение типа2>;
- и т.д.
- В Object Pascal можно выделить следующие типы данных:
- простые;
- структурированные;
- указатели;
- процедурные типы;
- объекты.
- К простым типам относятся :
- целые;
- логический;
- символьный;
- перечисляемый;
- тип-диапазон;
- вещественные типы.
|
|
|
|
|
|
|
|
|
- Целые
|
|
|
|
|
|
|
|
|
|
|
|
- Вещественные
- Для размещения данных типа char требуется 1байт.
- Символьный тип.
- Обозначается словом Char.
- Значениями данных символьного типа могут являться любые символы из расширенного набора символов для ПЭВМ.
- (Каждому символу приписывается целое число или код в диапазоне 0..255. Первая половина символов соответствует стандарту ASCII / American Standart Code for Information Interchange – американский стандартный код для обмена информацией/. Вторая половина символов с кодами 128..255 может меняться на ПЭВМ разных типов).
- Тип Boolean представляет собой тип данных, любой элемент которого может принимать только два значения: True (истина) или False (ложь).
- Логический тип.
- Для размещения данных типа Boolean требуется 1 байт памяти
- Существует 2 способа использования констант:
- непосредственное использование значения константы;
- использование идентификатора (имени) константы.
- Задание констант именами осуществляется в разделе объявления констант, который начинается словом Const.
- Константы.
- Константами называются параметры программы, значения которых не меняются в процессе ее выполнения.
- Const
- <имя константы1>=<значение 1>;
- <имя константы2>=<значение 2>; и т.д.
- Имя константы формируется согласно основному правилу формирования идентификаторов(см. выше).
- Напр., Const Max=1345;
- x_2=10.5;
- 35r, f-47 , вася – недопустимые имена констант.
- Константы могут быть целого, вещественного, символьного, логического и строкового типа.
- Целые. В изображении целых к. только знак и цифры. (-45, 509, +35)
- Вещественные. В своем изображении могут содержать знак, цифры, десятичную точку, показатель степени - символ Е или е.
- Сущ. две формы записи вещ. констант:
- а) естественная 10.6 -0.001
- б) экспоненциальная 0.107Е+02 -0.1е-02
- Строковые и символьные константы.
- Строка символов(или строковая константа) – это последовательность любого, в том числе и равного нулю, количества символов из стандартного набора символов ПЭВМ, расположенных на одной строке и заключенного в апострофы. Значимое кол-во символов 126.
- Строка, состоящая из одного символа, называется символьной константой.
- Напр. ' '
- ' студент группы ТМ-11 '
- ' f= '
- ' h '
- Переменные.
- Переменные — элементы программы, значения которых могут изменяться в процессе ее выполнения.
- Имя переменной придумывает программист.
- Имя переменной формируется согласно основному правилу формирования идентификаторов (см. выше).
- Желательно, чтобы имя переменной несло смысловую нагрузку.
- Все используемые в программе переменные должны быть определены с указанием их типов.
- Раздел объявления переменных выглядит сл. образом:
- Var
- <список переменных 1>:<тип 1>;
- <список переменных 1>:<тип 1>; и т.д.
- Напр.
- var
- x,summa:real;
- priznak:boolean;
- Переменные размещаются в оперативной памяти ЭВМ и имеют размер в соответствии с объявленным типом.
- Операции.
- В Object Pascal сущ. след. операции:
- арифметические, логические, операции со строками, операции отношения, операция с битами информации, адресная операция @.
- Арифметические операции (АО) применимы только к величинам целых и вещественных типов.
- Существуют следующие Арифметические операции (расположим их в порядке убывания приоритета):
- / и *
- div (целочисленное деление )
- mod (остаток от деления целых чисел )
- + и -
- Стандартные функции.
- В языке П. существует ряд заранее разработанных подпрограмм-функций, которые можно использовать как готовые объекты.
- Аргумент функции всегда заключается в круглые скобки !
- Аргумент ф-й sin и cos указывается в радианах.
- В Паскале нет операции возведения в степень. Поэтому, если степень простая, то можно поступать, исходя из определения степени. Напр.,
- В более сложных случаях для x>0 можно воспользоваться формулой
- Если к программе подключить модуль Math, добавив в нее строку программы
- Uses math;
- можно использовать следующие функции из этого модуля:
- Выражения.
- Выражение – это синтаксическая единица языка, определяющая способ вычисления некоторого значения. Выражения формируются из констант, переменных, функций, знаков операций и круглых скобок.
- Примеры арифметических выражений:
- 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))
- или при подключенном модуле Math
- ( 2*sqr(cos(x))-2.5 )/abs( tan(x*x*x*x)-1.2 )+power(fi,2.3)
Информатика - еще материалы к урокам:
- Презентация "Моделирование и основы системного анализа. Модели и элементы теории систем"
- Презентация "Начальный курс Java (8 занятий)"
- Презентация "Основы HTML. Создание сайтов в текстовом редакторе"
- Презентация "Информационная безопасность. Криптографические средства защиты данных"
- Презентация "Перше знайомство з мовою програмування Паскаль"
- Презентация "Технологии проектирования компьютерных систем. Методы проектирования цифровых устройств"
