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

1.

ОСНОВЫ и МЕТОДОЛОГИИ
ПРОГРАММИРОВАНИЯ
96 аудиторных.
лекций – 32, лабораторных занятий – 64.
зачет
Горбадей Ольга Юрьевна

2.

ПОНЯТИЕ АЛГОРИТМА
Алгоритм - конечная последовательность
точно определенных действий, приводящих к
однозначному
решению
поставленной
задачи.
Главная особенность любого алгоритма формальное
исполнение,
позволяющее
выполнять заданные действия (команды) не
только
человеку,
но
и
различным
техническим устройствам (исполнителям).
Процесс составления алгоритма называется
алгоритмизацией.

3.

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

4.

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

5.

Способы описания алгоритмов
Общеприняты несколько способов описания алгоритма: словесное
описание, псевдокод, блок-схема, программа.
Словесное описание представляет структуру алгоритма на
естественном языке. Например, любой прибор бытовой техники (утюг,
электропила, дрель и т.п.) имеет инструкцию по эксплуатации, т.е.
словесное описание алгоритма, в соответствии которому данный
прибор должен использоваться.
Никаких правил составления словесного описания не существует.
Запись алгоритма осуществляется в произвольной форме на
естественном, например, русском языке. Этот способ описания не имеет
широкого распространения, так как строго не формализуем (под
«формальным» понимается то, что описание абсолютно полное и
учитывает все возможные ситуации, которые могут возникнуть в ходе
решения); допускает неоднозначность толкования при описании
некоторых действий; страдает многословностью.

6.

Способы описания алгоритмов
Общеприняты несколько способов описания алгоритма: словесное
описание, псевдокод, блок-схема, программа.
Псевдокод – описание структуры алгоритма на естественном, частично
формализованном языке, позволяющее выявить основные этапы
решения задачи, перед точной его записью на языке
программирования.
В
псевдокоде
используются
некоторые
формальные конструкции и общепринятая математическая символика.
Строгих синтаксических правил для записи псевдокода не существует.
Это облегчает запись алгоритма при проектировании и позволяет
описать алгоритм, используя любой набор команд. Однако в
псевдокоде обычно используются некоторые конструкции, присущие
формальным языкам, что облегчает переход от псевдокода к записи
алгоритма на языке программирования. Единого или формального
определения псевдокода не существует, поэтому возможны различные
псевдокоды, отличающиеся набором используемых слов и конструкций.

7.

Способы описания алгоритмов
Общеприняты несколько способов описания алгоритма: словесное
описание, псевдокод, блок-схема, программа.
Блок-схема – описание структуры алгоритма с помощью
геометрических фигур с линиями-связями, показывающими порядок
выполнения отдельных инструкций. Этот способ имеет ряд
преимуществ. Благодаря наглядности, он обеспечивает «читаемость»
алгоритма и явно отображает порядок: выполнения отдельных команд.
В блок-схеме каждой формальной конструкции соответствует
определенная геометрическая фигура или связанная линиями
совокупность фигур.
Программа
–
описание
структуры
алгоритма
на
языке
алгоритмического
программирования.
Программа
на
языке
декларативного программирования представляет собой совокупность
описанных знаний и не содержит явного алгоритма исполнения.

8.

Графическое описание алгоритма

9.

Типы алгоритмов
Алгоритмы бывают :
линейные,
разветвляющиеся
и циклические.

10.

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

11.

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

12.

13.

Разветвляющийся алгоритм
содержит одно или несколько логических
условий и имеет несколько ветвей
обработки.
Структура РАЗВЕТВЛЕНИЕ предусматривает
проверку
условия,
после
которого
вычислительный процесс развивается по
одной из двух ветвей (в зависимости от
ответа на поставленный в условии вопрос).
Каждый из путей (ветвей) ведет к общему
выходу

14.

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

15.

Построить
значения
формулой
алгоритм
вычисления
функции у, заданной
х 2 2, если х 1
у 2
х 2 х 4, если х 1

16.

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

17.

Основные разновидности
циклов
Цикл с предусловием. (Цикл пока.)
Предписывает выполнение тела цикла
до тех пор, пока выполняется условие,
записанное после слова пока

18.

Основные разновидности
циклов
Цикл
с
постусловием.
Предписывает выполнять тело цикла
для
всех
значений
некоторой
переменной (параметра цикла) в
заданном диапазоне

19.

Итерационные и рекурсивные
алгоритмы
Под итерацией в общем случае понимают
такой способ организации обработки
данных, при котором многократно
повторяется
некоторая
последовательность действий.
Алгоритм,
основу которого составляет
итерация, называется итерационным
(итеративным).
Примером
итерационных
алгоритмов
являются
циклические конструкции.

20.

Итерационные и рекурсивные
алгоритмы
Обобщением понятия итерации является рекурсия,
под которой понимают такой способ организации
обработки данных, при котором алгоритм
использует сам себя в качестве вспомогательного
алгоритма.
Классическими
примерами
рекурсивных
алгоритмов являются вычисление факториала и
чисел Фибоначчи.
Факториал
целого
числа
п
рекурсивно
определяется как
Для того чтобы вычислить факториал некоторого
числа п> необходимо рассчитать факториал числа
(п - 1), для которого, в свою очередь, нужно
вычислить факториал числа (п - 2), и т.д.

21.

1. Составить блок-схему нахождения
площади и периметра прямоугольника по
введенным двум сторонам.
2. Составить блок-схему нахождения
суммы чисел от 1 до 10.
3. Составить блок схему нахождения
максимального числа из трех введенных.
4. Составить блок схему решения
квадратного уравнения
5. Построить алгоритм вычисления
значения функции у, заданной формулой
2
х
2, если х 1
у 3
х 2 х 8 3, если х 7