Понятие алгоритма. Свойства алгоритмов.

Абдулла Мухаммед аль-Хорезми ( гг.) Algorithmi 825 год

А Л Г О Р И Т М - описание последовательности действий, необходимых для получения ожидаемого результата

Исполнитель Исполнитель - это что-то или кто-то, способный выполнить действия, предписываемые алгоритмом

ИСПОЛНИТЕЛИ АЛГОРИТМОВ НЕФОРМАЛЬНЫЕ: ФОРМАЛЬНЫЕ: Человек животные Робот-манипулятор Техническое устройство (бытовые приборы) Компьютер

Система команд исполнителя Система команд исполнителя (СКИ) – совокупность команд, которые данный исполнитель может выполнить.

Свойства алгоритмов Понятность Дискретность Массовость Результативность Конечность

Понятность Алгоритм составляется только из команд, входящих в СКИ исполнителя.

Дискретность Алгоритм разбит на отдельные элементарные действия (шаги).

Массовость Алгоритм, разработанный для решения некоторой задачи, должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных

Результативность (или конечность) Выполнение алгоритма должно приводить к результату за конечное число шагов

Способы записи алгоритма Словесный Графический Программный

Блок-схемы как один из способов записи алгоритмов

Блок схема - -графическое представление алгоритма. Она состоит из функциональных блоков, которые выполняют различные назначения (ввод/вывод, начало/конец, вызов функции и т.д.).

Основные символы блок-схем

БЛОК НАЧАЛА ИЛИ ОКОНЧАНИЯ ВЫПОЛНЕНИЯ АЛГОРИТМА НАЧАЛО КОНЕЦ

БЛОКИ ВВОДА-ВЫВОДА БЛОК ВВОДА – ВЫВОДА ВЫВОД

БЛОК ПРИСВАИВАНИЯ Х:=У+120 ОБРАБАТЫВАЕТ ДАННЫЕ И РАЗМЕЩАЕТ РЕЗУЛЬТАТЫ В ЯЧЕЙКИ ПАМЯТИ С УКАЗАННЫМ ИМЕНЕМ

ПАРАМЕТР УСЛОВИЕ ДаНет БЛОК ПРОВЕРКИ УСЛОВИЯ БЛОК ЦИКЛА С ПАРАМЕТРОМ

НАЧАЛО ВВОД R S:=3,14*R 2 КОНЕЦ S ВЫВОД S

Линейный алгоритм (последовательный) - - описание действий, которые выполняются однократно в заданном порядке

Линейный алгоритм начало Закрыть глаза Открыть глаза Посмотреть влево Посмотреть вправо конец Выполни алгоритм

Разветвляющийся алгоритм- -алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий. Условие –выражение, находящееся между словами «если» и «то» и принимающее значение «истина» или «ложь».

КОМАНДА ВЕТВЛЕНИЯ ИМЕЕТ ПОЛНУЮ (1) ИЛИ СОКРАЩЕННУЮ ФОРМУ(2) 1 Серия 1 Условие Серия 2 ДаНет Да Нет Условие Серия 1 2

НАЧАЛО ВВОД A,B КОНЕЦ ВЫВОД M A>B M:=AM:=B ДаНет

Циклический алгоритм - -описание действий, которые должны выполняться указанное число раз или пока не выполнено заданное условие.

ТРИ ТИПА КОМАНД ПОВТОРЕНИЯ: ЦИКЛ «ДЛЯ» ЦИКЛ «ПОКА» ЦИКЛ «ДО» ОТЛИЧИЕ - СПОСОБ ПРОВЕРКИ ОКОНЧАНИЯ ЦИКЛА.

НАЧАЛО КОНЕЦ I I

НАЧАЛО КОНЕЦ ДаНет I=1,10,2 I ЦИКЛ «ДЛЯ»

НАЧАЛО КОНЕЦ I I>10 I:=I+2 ДаНет ЦИКЛ «ДО»

Циклический алгоритм начало Встать Сделал упр-е 5 раз? Наклониться влево Наклониться вправо Сесть конец нетда

Рассмотрим алгоритм нахождения большего из двух заданных чисел А и В 1.Из числа А вычесть число В. 2.Если получилось отрицательное значение, то сообщить, что число В больше. 3.Если получилось положительное значение, то сообщить, что число А больше. 4. Если получился ноль, то сообщить, что числа равны.

Д/з Составить словесный алгоритм: 1.Перевода текста с англ.яз. на рус. яз. 2.Вычисления площади треугольника. 3.Нахождения меньшего из трех чисел.

Алгоритмические задачи Задание. Волк, коза и капуста. Старик должен переправить на лодке через реку волка, козу и капусту. Лодка может выдержать только старика и одного «пассажира». В каком порядке старик перевезёт «пассажиров»? Не забудь, что волк может съесть козу, а коза – капусту. Найди два варианта решения.

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

Основные сведения о языках программирования Язык – система знаков. Язык ЭВМ ( машинный язык ) – двоичная знаковая система. Поэтому, чтобы компьютер мог понять написанную программу, она должна быть переведена на язык, понятный компьютеру. Этот процесс перевода называется трансляцией.

Интерпретаторы и компиляторы Существует два различных подхода к трансляции – интерпретация и компиляция : Интерпретатор переводит и выполняет программу строка за строкой. Компилятор переводит программу целиком, а затем выполняет её.

При компиляции (compile) в память ЭВМ загружается программа – компилятор. Компилятор производит синтаксический контроль программы и при обнаружении ошибок выводит соответствующее сообщение. Если ошибок нет, то результатом компиляции является программа на языке машинных команд. Затем компилятор удаляется из оперативной памяти. В памяти остается только программа на языке машинных команд, которая выполняется для получения необходимых результатов.

Интерпретатор в течении всего времени работы программы находится в оперативной памяти. В память также помещается программа на языке программирования высокого уровня. Интерпретатор «читает» ее первый оператор, переводит его в машинные команды и тут же организует выполнение этих команд. Затем переходит к переводу и выполнению следующего оператора и так до конца программы. При этом результаты предыдущих переводов в памяти не сохраняются. Перед трансляцией каждого оператора производится его синтаксический анализ.

Язык программирования Pascal Язык программирования Паскаль был разработан профессором, директором Института информатики Швейцарской высшей политехнической школы Николаусом Виртом в гг. как язык обучения студентов программированию.

Николаус Вирт Но думать, что Паскаль - язык исключительно для обучения, было бы неверно. Вот что говорил об этом Н. Вирт (1984 г.): « Утверждалось, что Паскаль был разработан в качестве языка для обучения. Хотя это утверждение справедливо, но его использование при обучении не являлось единственной целью. На самом деле я не верю в успешность применения во время обучения таких инструментов и методик, которые нельзя использовать при решении каких - то практических задач ». * *

Язык программирования Pascal С тех пор Паскаль становился всё более и более популярным, причем не только, как язык для обучения принципам программирования, но и как средство создания достаточно сложного программного обеспечения. В своем первоначальном виде Паскаль имел довольно ограниченные возможности, но расширенный вариант этого языка – Turbo Pascal является мощным языком программирования.

Почему PASCAL? Язык программирования Pascal был назван в честь французского учёного Блеза Паскаля, который еще в 1642 г. изобрел первую механическую счётную машину. Она представляла собой систему взаимодействующих зубчатых колёсиков, каждое из которых соответствовало одному разряду десятичного числа и содержало цифры от 0 до 9. Когда колёсико совершало полный оборот, следующее сдвигалось на одну цифру. Машина Паскаля была суммирующей машиной.

Основные средства языка Символы языка - это элементарные знаки, используемые при составлении текстов. Алфавит языка - набор таких символов. Алфавит языка Turbo Pascal включает : 1. все латинские прописные и строчные буквы ; 2. арабские цифры (0 – 9); 3. символы + - * / =,. ; : _ ( ) { } и др.; 4. служебные ( зарезервированные ) слова.

Для записи команд, имен функций, поясняющих терминов Pascal существует набор строго определенных слов, которые называются служебными или зарезервированными ( это английские мнемонические сокращения ). Служебные слова делятся на три группы : 1. операторы (READ, WRITELN и др.) ; 2. имена функций (SIN, COS и др.) ; 3. ключевые слова (VAR, BEGIN, END и др.). Основные средства языка

Обрабатываемые данные - величины Входные Промежуточные Выходные (аргументы) (результаты) Исходные данные, известные перед выполнением задачи, из условия Результат решения задачи

Обрабатываемые данные - величины характеризуются: - именем - типом - значением - обозначение и место в памяти - множество допустимых значений и множество применимых операций к ней, объём занимаемой памяти и способ представления в памяти ЭВМ - значение в ячейке. - М.б. не определено

Постоянная Переменная (константа) Не изменяется Значение меняется и не м.б. изменено в ходе выполнения алгоритма Величина

Арифметические операции (А, В – операнды) ВыражениеТипы операндовТип результата Операция A+BR, R I, I I, R R, I RIRRRIRR Сложение A-BA-BR, R I, I I, R R, I RIRRRIRR Вычитание

A*BR, R I, I I, R R, I RIRRRIRR Умножение A/BR, R I, I I, R R, I RRRRRRRR Вещественное деление A div BI, IIЦелое деление A mod BI, IIОстаток от целого деления

Стандартные математические функции Паскаля ОбращениеТип аргумента Тип результата Функция Abs(x) Arctan (x) Cos(x) Exp(x) Frac(x) Int(x) I, R R Модуль аргумента Арктангенс (х в радианах) Косинус (х в радианах) Экспонента Дробная часть Целая часть х

Random Random(x) Round(x) Sin(x) Sqr(x) Sqrt(x) Trunc(x) I R I, R R RIIRRRIRIIRRRI Псевдослучайное число в интервале [0, 1] Псевдослучайное число в интервале [0, х] Округление до ближайшего целого Синус (х в радианах) Квадрат Квадратный корень Ближайшее целое, не превышающее х по модулю

Структура программы Заголовок программы ; Раздел описаний ; Тело программы. Любая программа на Паскале имеет определенную структуру :

Основной файл программы имеет следующую структуру: Program ; Program ; Uses ; Uses ; const ; const ; type ; type ; var ; var ; procedure (function) ; procedure (function) ; begin begin ; ; end. end.

Структура программы PROGRAM имя; Const; Var; BEGIN оператор 1; оператор 2; ….. оператор n-1; оператор n; Readln END.

[имя] - программы может содержать до 8 символов, состоящих из латинских букв и цифр (должно начинаться с буквы и не содержать пробела).

Раздел описания переменных В разделе описания переменных содержится список переменных, используемых в программе, и определяется их тип. Var V1,V2,..,Vn : T ; где V1,V2,.., Vn -имена переменных данного типа Т Например: Var i, j : integer ; L : MyType2; M, k : char ;

Раздел операторов Раздел операторов состоит из операторов языка TР, отделенных друг от друга точкой с запятой. Он заключен в операторные скобки BEGIN END. При этом после end ставится точка. После слова begin и перед словом end точка с запятой обычно не ставится.

Любая программа взаимодействует с пользователем с помощью операторов ввода - вывода. Операторы ввода - вывода

Операторы действия Оператор присваивания := Обязательно: тип выражения и тип переменной должны быть совместимы по присваиванию. Пример. Присвоить значения переменным N, X, Y. N:=-5; X:=5678.9; Y:=5.6789e3

Ввод информации с клавиатуры осуществляется с помощью оператора READ. Когда в программе встречается оператор READ, то её действие приостанавливается до тех пор, пока не будут введены исходные данные. Имеет вид : READ( а,b,...) READLN( а,b,..,), где а,b,... – имена вводимых переменных READLN - применяется, когда исполнение программы желательно задержать до нажатия клавиши ENTER. Ln добавляется в конце оператора для автоматического перемещения курсора в начало новой строки. Оператор ввода READ

Оператор вывода WRITE Для вывода информации на экран используется оператор WRITE. Имеет вид : WRITE( а,b,...) WRITELN( а,b,..), где а,b,... – список выводимых констант, переменных, выражений. Ln добавляется в конце оператора для автоматического перемещения курсора в начало новой строки.

Оператор вывода WRITE 1. WRITE(2*2) – выводит на экран : 4 2.WRITE(2*2=) - выводит на экран : 2*2= 3. WRITE(2*2=, 2*2) - выводит на экран : 2*2=4

В программу на Паскале можно вставлять комментарии. Комментарий – это пояснение к программе, которое записывается в фигурных скобках. В комментариях можно использовать русские буквы. На исполнение программы комментарий никак не влияет.

Среда программирования Geany