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

ГПОУ «Ленинск-Кузнецкий политехнический техникум»

ИНФОРМАТИКА

Понятие алгоритма

Свойства алгоритмов

Алгоритмические структуры

Преподаватель Щеглова Алена Александровна

Теоретическое занятие

для студентов I курса

Ленинск-Кузнецкий, 2024

Историческая справка

Термин «алгоритм» возник в средние века, под ним понимали способ выполнения арифметических действий над десятичными числами, описанными узбекским математиком Муххамедом бен Аль-Хорезми

«Аль-Хорезми» - человек из города Хорезми; в настоящее время город Хива в Узбекистане

Со временем это понятие стали использовать для обозначения последовательности действий, приводящей к решению поставленной задачи

Понятие алгоритма

Алгоритм – описанная точная конечная система правил, определяющая содержание и порядок действий над объектами, строгое выполнение которых дает решение, поставленной задачи

Пример алгоритма

Инструкция, использования домофона, на двери дома

Алгоритм «Использование домофона»

начало

• Набрать номер квартиры
• Нажать кнопку «Вызов»
• Услышав прерывистый сигнал, ждите ответа
• Услышав ответ, говорите
• Услышав звуковой сигнал, входите

конец

Пример алгоритма

Рецепт

Алгоритм «приготовления салата Оливье»

начало 1.Мясо отварить до готовности (около 40 минут) 2.Остудить мясо 3.Лук мелко покрошить 4.Залить его кипятком и оставить на 10 минут, воду слить

5.Мясо нарезать кубиками 6.Картофель почистить, нарезать кубиками 7. Яйца мелко покрошить 8.Огурцы мелко нарезать 9.Смешать картофель, мясо, лук, горошек (воду слить) , яйца, огурцы 10.Посолить по вкусу 11. Заправить майонезом

конец

Пример алгоритма

Алгоритм « Покупка хлеба » Начало

• Взять деньги и пойти в магазин
• Прийти в магазин и купить хлеб
• Вернуться домой с хлебом

Конец

Свойства алгоритма

1. Дискретность – это свойство алгоритма означает, что путь решения задачи разделён на отдельные шаги. Каждому действию соответствует предписание (команда). Только выполнив одну команду, исполнитель может приступить к выполнению следующей команды.

Шаг алгоритма – это каждое отдельное действие алгоритма.

Алгоритм «Использование домофона»

начало

• Набрать номер квартиры
• Нажать кнопку «Вызов»
• Услышав прерывистый сигнал, ждите ответа
• Услышав ответ, говорите
• Услышав звуковой сигнал, входите

конец

Свойства алгоритма

2. Массовость – применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных. Исходные данные могут выбираться из области, которая называется областью применимости алгоритма.

Алгоритм «Определение расстояния»

начало

• Возьмите линейку
• Вытяните руку с линейкой
• Направьте руку на просматриваемый предмет
• Установите линейку вертикально
• Запомните количество делений линейки, соответствующих изображению предмета
• Умножьте длину руки на примерную высоту предмета
• Разделите получившееся число на измеренное в п. 5 количество делений. Это расстояние до предмета

Конец

Свойства алгоритма

3. Определенность (детерминированность, точность) – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; строго должен быть определен порядок выполнения отдельных шагов.

Алгоритм «Использование домофона»

начало

• Набрать номер квартиры
• Нажать кнопку «Вызов»
• Услышав прерывистый сигнал, ждите ответа
• Услышав ответ, говорите
• Услышав звуковой сигнал, входите

конец

Пример алгоритма

Рецепт

Алгоритм «приготовления салата Оливье»

начало 1.Мясо отварить до готовности (около 40 минут) 2.Остудить мясо 3.Лук мелко покрошить 4.Залить его кипятком и оставить на 10 минут, воду слить

5.Мясо нарезать кубиками 6.Картофель почистить, нарезать кубиками 7. Яйца мелко покрошить 8.Огурцы мелко нарезать 9.Смешать картофель, мясо, лук, горошек (воду слить) , яйца, огурцы 10.Посолить по вкусу 11. Заправить майонезом

конец

Свойства алгоритма

4. Результативность (конечность) – свойство, состоящее в том, что любой алгоритм должен завершаться за конечное число шагов.

Алгоритм «Использование домофона»

начало

• Набрать номер квартиры
• Нажать кнопку «Вызов»
• Услышав прерывистый сигнал, ждите ответа
• Услышав ответ, говорите
• Услышав звуковой сигнал, входите
• конец

Свойства алгоритма

5. Формальность – это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции.

Пример алгоритма

Рецепт

Алгоритм «приготовления салата Оливье»

начало 1.Мясо отварить до готовности (около 40 минут) 2.Остудить мясо 3.Лук мелко покрошить 4.Залить его кипятком и оставить на 10 минут, воду слить

5.Мясо нарезать кубиками 6.Картофель почистить, нарезать кубиками 7. Яйца мелко покрошить 8.Огурцы мелко нарезать 9.Смешать картофель, мясо, лук, горошек (воду слить) , яйца, огурцы 10.Посолить по вкусу 11. Заправить майонезом

конец

Формы представления алгоритмов

• Словесная форма. Алгоритм задается в произвольном изложении на естественном языке

Недостаток: при составлении сложных алгоритмов описание становится громоздким и ненаглядным

Алгоритм «Использование домофона»

начало

• Набрать номер квартиры
• Нажать кнопку «Вызов»
• Услышав прерывистый сигнал, ждите ответа
• Услышав ответ, говорите
• Услышав звуковой сигнал, входите

конец

Формы представления алгоритмов

2. Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.

Служебные слова алгоритмического языка (псевдокода)

Формы представления алгоритмов

Алг название алгоритма

• Нач
• Серия команд алгоритма
• Кон

алг Вычисление гипотенузы

нач

дано k1=3, k2=4,

z:=k1 2 // Вычислить квадрат k1 и запомнить в переменной z z2:=k2 2 // Вычислить квадрат k2 и запомнить в переменной

g = // Вычислить гипотенузу g

рез g.

кон

Формы представления алгоритмов

3. Графический способ (блок-схемы)

• При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков и стрелок, соединяющих эти блоки

начало

Набрать номер квартиры

Нажать кнопку «Вызов»

Услышав ответ говорите

Услышав звуковой сигнал, входите

Конец

Блок-схемы

• В блок-схеме каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа

Форма блока

Назначение блока

начало и конец блок-схемы

блок ввода/вывода данных

блок выполнения действия

блок условия

организация циклических процессов

вызов вспомогательного алгоритма

Блок-схемы

Форма блока

Назначение блока

комментарии

Вывод на печать

Правила построения блок-схем

• Блок-схема строится сверху вниз
• В любой блок-схеме имеется один элемент, соответствующий началу, и один элемент, соответствующий концу
• Должен быть хотя бы один путь из начала блок-схемы к любому элементу
• Должен быть хотя бы один путь от каждого элемента блок-схемы в конец блок-схемы

Блок-схема

• Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий

начало

Набрать номер квартиры

Нажать кнопку «Вызов»

Услышав ответ говорите

Услышав звуковой сигнал, входите

Конец

Блок-схема

• Вычислите значение переменной m, если a=10, b=2, c=8

Блок-схемы

Найдите результат вычисления блок-схемы

Начало

a, b

x : = a – 2 * b

x

Конец

Исходные данные

Результаты выполнения

а =__, b = __

Вывод значений

х =

х =

Классификация выражений

• Арифметические выражения состоят из чисел и переменных, арифметических операций, служат для нахождения числового значения.

= x*y/z

=(a^3+b^3)/(b*c)

или x^2

Найти и исправить ошибку в записи:

5x+1 a+sinx

((a+b)/c**3

Команда присваивания

Команда присваивания нужна для вычисления значений выражений и присваивания их значений переменным

Общий вид:

:=

  Знак «:=» читается как присвоить и заменяет предыдущее значение переменной, стоящей в левой части на новое, которое находится в правой части

Знаки «=» и «:=» — это разные знаки. Знак равно обозначает равенство двух величин. А знак «:=» присваивает новое значение переменной

A:=10; B:=(A+4)/2;

А:=В-2;

В:=А+В;

Команда присваивания

Запишите по правилам алгоритмического языка выражение

Команда присваивания

Запишите по правилам алгоритмического языка выражение

Команда присваивания

Определите значение переменной C после исполнения данного алгоритма

A :=1;

B := 1+ 2 * A;

A := B / A;

C := A + 2 * B;

Команда присваивания

Запишите в обычной математической форме арифметические выражения:

((u+v)^2)/(u/v)+(2*u-v)

Линейный алгоритм

Следование   алгоритмическая конструкция, в которой действия выполняются последовательно друг за другом.

Алгоритмы с конструкцией «следование» называются ли-нейными алгоритмами.

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

Начало

Алгоритм «Название»

начало

• Команда 1
• ………… .

n. Команда n

конец

Ввод исходных данных

Команда 1

………… .

Команда n

Вывод исходных данных

Конец

Линейный алгоритм

Установите правильную последовательность шагов.

Изобразите графически алгоритм, с помощью блок-схемы.

Алгоритм «Открой дверь»

Начало

• Достань ключ из кармана
• Поверни ключ два раза
• Вставь ключ в замочную скважину
• Вытащи ключ

Конец

Разветвляющийся алгоритм

Разветвляющаяся структура (ветвление) – это структура, обеспечивающая альтернативный выбор в зависимости от заданного условия.

Условие - вопрос, имеющий два варианта ответа: да или нет

Полное ветвление

Если условие истинно , то Команда 1 , иначе Команда 2

Условие

Да

Нет

Команда 1

Команда 2

0, то y=2x, иначе y=3x-1 Назовите условие Назовите Команду 1 Назовите Команду 2 " width="640"

Разветвляющийся алгоритм

Если условие истинно , то Команда 1 , иначе Команда 2

Условие

Нет

Да

Команда 1

Команда 2

Составить команду ветвления

Если x 0, то y=2x, иначе y=3x-1

• Назовите условие
• Назовите Команду 1
• Назовите Команду 2

Разветвляющийся алгоритм

Неполное ветвление

Если условие истинно, то Команда 1

Условие

Да

Команда 1

Неполное ветвление

Если условие, то Команда 1

Тело цикла

Пример. Изобразите графически описание пословицы: «Если хочешь быть здоров, закаляйся»

Структура разветвляющегося алгоритма

Начало

Начало

Ввод исходных данных

Ввод исходных данных

Условие

Условие

Нет

Да

Да

Команда 1

Команда 1

Команда 2

Вывод исходных данных

Вывод исходных данных

Конец

Конец

Полное ветвление

Неполное ветвление

13 Да Нет желтые c синие зеленые Конец " width="640"

Полное ветвление

В коллекции хранятся бабочки различных цветов. Чтобы узнать, какого цвета бабочки преимущественно составляли коллекцию, выполни алгоритм

Начало

• a = 5, b = 4
• a = 5, b = 3
• a = 5, b = 1

а , b

c=2a+b

Да

Нет

c 13

Да

Нет

желтые

c

синие

зеленые

Конец

Неполное ветвление

Определите слово, которое получится в результате выполнения данного алгоритма

Начало

Слово «парус»

Да

Нет

Буква П

Заменить на букву «В»

Да

Нет

Буква А

Заменить на букву «И»

Слово

Конец

Циклический алгоритм

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

Итерационный цикл - это цикл, для которого число повторений тела цикла заранее неизвестно. 

В итерационных циклах на каждом шаге вычислений происходят последовательное приближение и проверка условия достижения искомого результата.

Выход из итерационного цикла осуществляется в случае выполнения заданного условия.

Циклический алгоритм

Цикл «пока» (цикл с предусловием):

Проверяется условие, если оно истинное, то происходит переход к выполнению тело цикла, иначе происходит выход из цикла. Тело цикла выполняется до тех пор, пока истинно условие

Условие

Да

Нет

Тело цикла

Циклический алгоритм

Цикл «до» (цикл с постусловием):

Исполнение цикла начинается с выполнения действия. После этого происходит проверка условия. Если условие не выполняется, то происходит возврат к выполнению действий. Если условие истинно, то осуществляется выход из цикла.

Тело цикла

Условие

Нет

Да

Циклический алгоритм

Пример 1. Построить блок схему по циклу «пока»

Алгоритм «Чтение книги»

Начало

• Открыть книгу
• Пока книга не закончится повторять:
• Прочесть две страницы
• Перевернуть страницу

конец

Да

Нет

Условие

Команда 1

Циклический алгоритм

Цикл «пока» (цикл с предусловием):

Проверяется условие, если оно истинное, то происходит переход к выполнению Команда 1, иначе происходит выход из цикла. Команда 1 выполняется до тех пор, пока истинно условие

Условие

Да

Нет

Тело цикла

Циклический алгоритм

Какой результат будет при выполнении данного алгоритма?

Есть слова?

Да

Нет

Найти слово в словаре

Записать найденное слово в тетрадь

Составить предложение

Циклический алгоритм

Пример. Какой результат будет при выполнении данного алгоритма?

Есть чувство голода?

Да

Нет

Купить пирожок

Съесть пирожок

Циклический алгоритм

Цикл с параметром

Используется, когда заранее известно количество повторений операций тела цикла.

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

Шаг – числовой показатель изменения параметра после каждой итерации

Счетчик = Нач.знач, Кон.знач, шаг

Команда 1

Циклический алгоритм

Пример 1. Построить блок схему по циклу с параметром описывающую пословицу «Семь лет молчал, на восьмой вскричал»

Счетчик = Нач.знач, Кон.знач, шаг

Команда 1

Команда 2