Информатика. Модуль 16. Основы алгоритмизации и программирования1 ОСНОВЫ АЛГОРИТМИЗАЦИИ Информатика

Информатика. Модуль 16. Основы алгоритмизации и программирования2 Содержание раздела 1.Понятие алгоритма, его свойства. Основные алгоритмические конструкции 2.Простые и структурированные типы данных 3.Основы программирования 4.Программирование на языке Pascal

Информатика. Модуль 16. Основы алгоритмизации и программирования3 1. Понятие алгоритма, его свойства. Основные алгоритмические конструкции

Информатика. Модуль 16. Основы алгоритмизации и программирования4 Понятие алгоритма Алгоритм –упорядоченная совокупность системы правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых приводит к решению любой задачи из рассматриваемого класса задач за конечное число шагов.

Информатика. Модуль 16. Основы алгоритмизации и программирования5 Понятие алгоритма Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми («Аль-Хорезми» – человек из города Хорезми). Слово алгоритм – есть результат европейского произношения слов Аль-Хорезми.

Информатика. Модуль 16. Основы алгоритмизации и программирования6 Свойства алгоритмов АЛГОРИТМ ДискретностьОпределенностьМассовостьРезультативность

Информатика. Модуль 16. Основы алгоритмизации и программирования7 Свойства алгоритмов Дискретность (разрывность) – это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий. Массовость – применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных. Определенность – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. Результативность - конечность действий алгоритма решения задач, позволяющая получить желаемый результат при допустимых исходных данных за конечное число шагов.

Информатика. Модуль 16. Основы алгоритмизации и программирования8 Способы описания алгоритмов Словесное описание Псевдокод(школьный алгоритмический язык) табличный Блок-схема Программа

Информатика. Модуль 16. Основы алгоритмизации и программирования9 Способы описания алгоритмов Словесное описание представляет структуру алгоритма на естественном языке. Пример: инструкция по эксплуатации любого прибора бытовой техники (утюг, телевизор, электрочайник), рецепт блюда, правила дорожного движения. Словесная форма имеет ряд недостатков: строго не формализуема; страдает многословностью записей; допускает неоднозначность толкования отдельных предписаний. Обычно используется на начальных стадиях разработки алгоритма.

Информатика. Модуль 16. Основы алгоритмизации и программирования10 Способы описания алгоритмов Псевдокод – пошагово-словесная запись алгоритма по определенным правилам или соглашениям. Пример. Алгоритм сложения двух чисел: 1.Ввод a, b. 2.S=a + b. 3.Вывод S. 4.Конец.

Информатика. Модуль 16. Основы алгоритмизации и программирования11 Способы описания алгоритмов Примером псевдокода является школьный алгоритмический язык. Основные служебные слова этого языка представлены в таблице 1.1.

Информатика. Модуль 16. Основы алгоритмизации и программирования12 Пример записи алгоритма на школьном АЯ алг Сумма квадратов (арг цел n, рез цел S) дано | n > 0 надо | S = 1*1 + 2*2 + 3* n*n нач цел i ввод n; S:=0 нц для i от 1 до n S:=S + i*I кц вывод "S = ", Sкон

Информатика. Модуль 16. Основы алгоритмизации и программирования13 Способы описания алгоритмов Блок-схема – это наглядное графическое представление алгоритма с помощью геометрических фигур, соединенных линиями связями, показывающими порядок выполнения инструкций.

Информатика. Модуль 16. Основы алгоритмизации и программирования14 Графические объекты блок-схем Начало - Начало алгоритма Конец - Конец алгоритма - Процесс Ввод / Вывод - Ввод/вывод данных с неопределенного носителя

Информатика. Модуль 16. Основы алгоритмизации и программирования15 Графические объекты блок-схем - Условный блок - Ввод с клавиатуры - Вывод на монитор - Вывод на печатающее устройство Нет Да Услови е

Информатика. Модуль 16. Основы алгоритмизации и программирования16 Графические объекты блок-схем - Цикл с параметром - Границы цикла Тело цикла

Информатика. Модуль 16. Основы алгоритмизации и программирования17 Способы описания алгоритмов Программа – описание структуры алгоритма на языке программирования. program sistema ; var x, xn, xk, dx, y: real ; uses crt ; begin clrscr; writeln ('Введите начальное, конечное значение х и шаг') ; readln (xn, xk,dx) ; x:=xn; repeat if x > 0 then y:=ln(x) else y:=sqr(x)+5*x; writeln ('x=', x:6:2, 'y=',y) ; x:=x+dx; until x > xk; readln; end. Пример:

Информатика. Модуль 16. Основы алгоритмизации и программирования18 Основные алгоритмические конструкции Алгоритмические конструкции ЛинейнаяРазветвляющаясяЦиклическая

Информатика. Модуль 16. Основы алгоритмизации и программирования19 Линейная алгоритмическая конструкция Линейный алгоритм – это описание последовательности действий, которые выполняются однократно в заданном порядке Начало Конец

Информатика. Модуль 16. Основы алгоритмизации и программирования20 Линейная алгоритмическая конструкция Примеры линейных алгоритмов

Информатика. Модуль 16. Основы алгоритмизации и программирования21 ПРИМЕР 1 Зная радиус основания и высоту цилиндра, вычислить его объем. Псевдокод: 1.Ввод R и H. 2.V= R 2 H. 3.Вывод V. 4.Конец. Начало Конец Вывод V V= R 2 H Ввод R, H Блок-схема:

Информатика. Модуль 16. Основы алгоритмизации и программирования22 ПРИМЕР 2 Составить алгоритм для решения линейного уравнения k x+b=0. Блок-схема: Псевдокод: 1.Ввод k, b Вывод x. 4.Конец. Начало Конец Вывод V Ввод k, b x = - b/k

Информатика. Модуль 16. Основы алгоритмизации и программирования23 Разветвляющаяся алгоритмическая конструкция Разветвляющийся алгоритм – такой алгоритм, в котором выполняется либо одна, либо другая последовательность действий, в зависимости от условия.

Информатика. Модуль 16. Основы алгоритмизации и программирования24 Разветвляющаяся алгоритмическая конструкция Ветвление Полное ЕСЛИ – ТО – ИНАЧЕ Неполное ЕСЛИ – ТО

Информатика. Модуль 16. Основы алгоритмизации и программирования25 Разветвляющаяся алгоритмическая конструкция Полное ветвление Условие Действия 2Действия 1 ДаНет Полное ветвление позволяет организовать в алгоритме две ветви (ТО или ИНАЧЕ).

Информатика. Модуль 16. Основы алгоритмизации и программирования26 Разветвляющаяся алгоритмическая конструкция Неполное ветвление Неполное ветвление предполагает наличие действий только на одной ветви (ТО), вторая ветвь отсутствует. Условие Действия ДаНет

Информатика. Модуль 16. Основы алгоритмизации и программирования27 ПРИМЕР 1 Известны коэффициенты a, b, c квадратного уравнения. Вычислить корни квадратного уравнения.

Информатика. Модуль 16. Основы алгоритмизации и программирования28 ПРИМЕР 1 Псевдокод: 1.Ввод a, b, c. 2.d=b 2 –4 a c. 3.ЕСЛИ d

Информатика. Модуль 16. Основы алгоритмизации и программирования29 Блок-схема: Начало Ввод a, b, c d=b 2 -4 a c Конец Вывод Х 1, Х 2 d

Информатика. Модуль 16. Основы алгоритмизации и программирования30 ПРИМЕР 2 Составить псевдокод и блок-схему к алгоритму вычисления значения функции

Информатика. Модуль 16. Основы алгоритмизации и программирования31 ПРИМЕР 2 Псевдокод: 1.Ввод Х. 2.ЕСЛИ Х > 0, ТО Y(X) = X 3, ИНАЧЕ Y(X) = – 1. 3.Вывод Y(X). 4.Конец. X > 0X > 0 Y(X) = – 1Y(X) = X 3 ДаНет

Информатика. Модуль 16. Основы алгоритмизации и программирования32 Команда «Выбор» Перед выполнением команды «выбор» вычисляется значение некоторого выражения Х, а затем начинается проверка условий Y1(Х), Y2(Х)...Yn(Х). Проверка продолжается до тех пор, пока не встретится условие, принимающее значение ИСТИНА при данном Х. Y 1 (Х ) Y 2 (Х ) Y 3 (Х ) Действие 1 Действие 2 Действие 3Действие 4 Да Нет Да

Информатика. Модуль 16. Основы алгоритмизации и программирования33 Команда «Выбор» ХnХn Х2 Х1 … Х Действие1Действие2Действие n

Информатика. Модуль 16. Основы алгоритмизации и программирования34 ПРИМЕР Составить блок-схему к программе, которая запрашивает у пользователя номер дня недели и выводит одно из сообщений «Рабочий день», «Суббота» или «Воскресенье». Псевдокод: 1.Ввод Х. 2.Выбор Х : 1.. 5: вывод «рабочий день»; 6: вывод «суббота»; 7: вывод «воскресенье»; ИНАЧЕ вывод «Ошибка! Введите число от 1 до 7». Конец.

Информатика. Модуль 16. Основы алгоритмизации и программирования35 Команда «Выбор» х=1..5 х = 6 Да Нет Вывод Рабочий день Вывод Суббота Вывод Воскресень е Ввод Х Начало Конец Да х = 7 Вывод Ошибка!!! Нет

Информатика. Модуль 16. Основы алгоритмизации и программирования36 2 Вариант Х Раб. деньСуббота Воскре- сенье Ошибка!!!

Информатика. Модуль 16. Основы алгоритмизации и программирования37 Циклическая алгоритмическая конструкция Циклической называют алгоритмическую конструкцию, в которой действие выполняется указанное число раз, или, пока не выполнится условие. Группа повторяющихся действий цикла называется телом цикла.

Информатика. Модуль 16. Основы алгоритмизации и программирования38 Циклическая алгоритмическая конструкция Цикл С параметром С предусловием С постусловием

Информатика. Модуль 16. Основы алгоритмизации и программирования39 Цикл с параметром В цикле с параметром число повторений цикла однозначно определено и задается с помощью начального, конечного значений параметра и шагом его изменения. Тело цикла i = N,К,Н

Информатика. Модуль 16. Основы алгоритмизации и программирования40 Цикл с параметром ПРИМЕР. Даны целые числа K и N (N>0). Вывести N раз число K. Начало Ввод K, N Конец Вывод K i =1,N,1

Информатика. Модуль 16. Основы алгоритмизации и программирования41 Цикл с предусловием Действия внутри этого цикла повторяются, пока выполняется условие в блоке ветвления, причем сначала проверяется условие, а затем выполняется действие. Услови е Тело цикла Нет Да Тело цикла Условие +

Информатика. Модуль 16. Основы алгоритмизации и программирования42 Цикл с предусловием ПРИМЕР. Найти значение всех Y = X при Х, изменяющемся от 1 до 10 с шагом 0,5.

Информатика. Модуль 16. Основы алгоритмизации и программирования 43 Цикл с предусловием ПРИМЕР. Найти значение всех Y = X при Х, изменяющемся от 1 до 10 с шагом 0,5. Начало Х = 1 Конец Выво д Х, Y Х 10 Y = X Нет Да Х = Х + 0,5

Информатика. Модуль 16. Основы алгоритмизации и программирования44 Цикл с постусловием Тело цикла с постусловием всегда будет выполнено хотя бы один раз. Оно будет выполняться до тех пор, пока значение условного выражения ЛОЖНО. Как только условное выражение принимает значение ИСТИНА, цикл завершается. Условие Тело цикла Нет Да Условие Тело цикла +

Информатика. Модуль 16. Основы алгоритмизации и программирования45 Цикл с постусловием ПРИМЕР. Составить блок-схему к программе, которая запрашивает у пользователя положительные числа, считает их сумму и количество. Как только введено отрицательное число или ноль, программа завершается.

Информатика. Модуль 16. Основы алгоритмизации и программирования 46 Цикл с постусловием ПРИМЕР. Составить блок-схему к программе, которая запрашивает у пользователя положительные числа, считает их сумму и количество. Как только введено отрицательное число или ноль, программа завершается. Правило суммирования: 1.Необходимо задать начальное значение суммы S = 0. 2.В теле циклической конструкции выполнить команду: S = S +.

Информатика. Модуль 16. Основы алгоритмизации и программирования 47 Цикл с постусловием ПРИМЕР. Составить блок-схему к программе, которая запрашивает у пользователя положительные числа, считает их сумму и количество. Как только введено отрицательное число или ноль, программа завершается. Правило суммирования: 1.Необходимо задать начальное значение суммы S = 0. 2.В теле циклической конструкции выполнить команду: S = S +. Правило счетчика: 1.Начальное значение счетчика К = 0. 2.В теле цикла выполнить команду К = К + 1.

Информатика. Модуль 16. Основы алгоритмизации и программирования48 Вывод S, K Начало S = 0 Конец Ввод х Х 0 Нет S = S + х, К = К + 1 К = 0 Да S = S – х, К = К – 1 Псевдокод: 1.S = 0, K = 0. 2.Ввод х. 3.S = S + x. 4.K = K Если х 0, ТО переходим к шагу 6. ИНАЧЕ переходим к п S = S – x, K = K – 1. 7.Вывод S, K 8.Конец.

Информатика. Модуль 16. Основы алгоритмизации и программирования49 2. Простые и структурированные типы данных

Информатика. Модуль 16. Основы алгоритмизации и программирования50 Простые типы данных Целые, вещественные числа, логические величины – все это простые типы данных (или базовые). Переменная – это именованный объект (ячейка памяти), который может изменять свое значение. Кроме имени и значения, переменная имеет тип, определяющий, какая информация находится в памяти.

Информатика. Модуль 16. Основы алгоритмизации и программирования51 Если переменные присутствуют в программе, на протяжении всего времени ее работы – их называют статическими. Простые типы данных

Информатика. Модуль 16. Основы алгоритмизации и программирования52 Если переменные присутствуют в программе, на протяжении всего времени ее работы – их называют статическими. Переменные, создающиеся и уничтожающиеся на разных этапах выполнения программы, называют динамическими. Простые типы данных

Информатика. Модуль 16. Основы алгоритмизации и программирования53 Если переменные присутствуют в программе, на протяжении всего времени ее работы – их называют статическими. Переменные, создающиеся и уничтожающиеся на разных этапах выполнения программы, называют динамическими. Данные, значения которых не изменяются на протяжении работы программы, называют постоянными или константами. Простые типы данных

Информатика. Модуль 16. Основы алгоритмизации и программирования54 Структурированные типы данных. Одномерные и двумерные массивы Тип данных, позволяющий хранить вместе под одним именем несколько переменных, называется структурированным. К структурированным типам данных относятся: массивы, строки, множества, записи, файлы. Значениями этих типов всегда являются простые типы.

Информатика. Модуль 16. Основы алгоритмизации и программирования55 Типы данных Скалярные Стандартные Целочисленный Вещественный Символьный Логический Определяемые пользователем Перечисляемый Интервальный Структурированные Массивы Строки Записи Файлы Множества

Информатика. Модуль 16. Основы алгоритмизации и программирования56 Целочисленные типы ТипДиапазон Размер (в байтах) Byte0….2551 Word0… Integer-32768… Shortint-128…1271 Longint Определяют константы, переменные и функции, значения которых реализуются множеством целых чисел, допустимых в данной ЭВМ.

Информатика. Модуль 16. Основы алгоритмизации и программирования57 Вещественные типы Определяют те данные, которые реализуются подмножеством действительных чисел, допустимых в данной ЭВМ. ТипДиапазон Размер (в байтах) Real2.9E-39…1.7E386 Single1.5E-45…3.4E384 Double5E-324…1.7E3088 Extended3.4E E493210

Информатика. Модуль 16. Основы алгоритмизации и программирования58 Стандартные типы данных Символьный тип представляет собой любой символ, который может быть отображен на экране дисплея. Он занимает 1 байт и может быть описан с помощью служебного слова char. В тексте программы значения переменных и константы символьного типа должны быть заключены в апострофы. Логический тип (boolean) определяет те данные, которые могут принимать логические значения TRUE и FALSE.

Информатика. Модуль 16. Основы алгоритмизации и программирования59 Типы, определяемые пользователем Перечислимый тип задается непосредственным перечислением значений, которые может принимать переменная данного типа. Например: var a, b: (read, blue, green); Интервальный тип позволяет задавать две константы, которые определяют границы изменения переменных данного типа. Например: var a: 1..10;

Информатика. Модуль 16. Основы алгоритмизации и программирования60 Структурированные типы Массив – это совокупность данных одного и того же типа. Для описания массивов используется служебное слово array. var a: array[1..10] of integer; Строки – последовательность символов. При использовании в выражениях строка заключается в апострофы. Ее длина ограничена 255 символами. Для описания переменных строкового типа используется служебное слово string. var a: string[10];

Информатика. Модуль 16. Основы алгоритмизации и программирования61 Арифметические операции ОперацияДействиеТип операндовТип результата +СложениеЦелый, вещественный -ВычитаниеЦелый, вещественный *УмножениеЦелый, вещественный /ДелениеЦелый, вещественный DivДеление нацелоЦелый ModОстаток от деленияЦелый And«И»Целый ShlСдвиг влевоЦелый ShrСдвиг вправоЦелый Or«ИЛИ»Целый XorИсключающее «ИЛИ»Целый -ОтрицаниеЦелый NotЛогическое отрицаниеЦелый

Информатика. Модуль 16. Основы алгоритмизации и программирования62 Структура программы Раздел описаний содержит: раздел описания констант; раздел описания типов; раздел описания переменных; раздел описания процедур и функций.