Основы алгоритмизации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Информатика. Модуль 16. Основы алгоритмизации и программирования
Способы описания алгоритмов
Программа – описание структуры алгоритма на языке программирования.
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. Основы алгоритмизации и программирования
Основные алгоритмические конструкции

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

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

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

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

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

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

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

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

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

Информатика. Модуль 16. Основы алгоритмизации и программирования
ПРИМЕР 1
Псевдокод:
Ввод a, b, c.
d=b2–4⋅a⋅c.
ЕСЛИ d<0, ТО «Корней нет», перейти к п.5. ИНАЧЕ Х1=(-b+d0,5)/(2⋅a), X2=(-b-d0,5)/(2⋅a).
Вывод Х1 и Х2.
Конец.

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

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

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

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

Информатика. Модуль 16. Основы алгоритмизации и программирования
Команда «Выбор»

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

Информатика. Модуль 16. Основы алгоритмизации и программирования
Команда «Выбор»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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