Алгоритмы_Технологии программирования_ООП (1)

Кафедра

Лекции по программированию

Кафедра

Преподаватель

информатики

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

информатики

УГАТУ

УГАТУ

Для студентов факультета ИРТ

Направление СТС, ЭАС, БПС

Рамбургер Ольга Леонардовна

Составитель:

Телефон: 8 908 357 68 21

доценты кафедры Информатика

Карчевская Маргарита Петровна

E-mail: ramburger_2013@mail.ru

Рамбургер Ольга Леонардовна

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

1

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

2

Кафедра

Кафедра

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

информатики

Тема

информатики

УГАТУ

УГАТУ

Алгоритмы

Понятие алгоритма является одним из основных

понятий современной информатики.

•

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

Алгоритм* – конечный набор точных и понятных

•

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

исполнителю предписаний, позволяющих

•

Объекты алгоритма

решать конкретную задачу из определенного

класса однотипных задач.

•

Способы записи алгоритмов

•

Базовые структуры алгоритмов

* Algorithmi – латинская форма написания имени математика IX

века Аль Хорезми, который сформулировал правила

выполнения четырех арифметических действий в

десятичной системе счисления.

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

4

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

Алгоритм – это преобразование входных

Исполнитель – это человек, группа людей,

(исходных) данных в выходные (результат

робот, станок, компьютер, язык

решения задачи). Преобразование выполняет

Исполнитель.

программирования и т.д.

СКИ (система команд исполнителя) – некоторая

совокупность команд, которую может

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

алгоритма для получения необходимого

результата.

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

5

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

6

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

Действия исполнителя – строгое выполнение

ОДЗ – область

допустимых значений

заданных инструкций (формальное, не вникая в

смысл того, что он делает).

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

Алгоритм – это

преобразование

Наличие алгоритма формализует процесс

решения задачи, исключает рассуждение

Знания о предметной

исполнителя.

области

Искомый результат

Конкретный набор исходных данных из ОДЗ –

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

данного алгоритма.

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

7

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

8

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

Дискретность. Путь решения задачи определен в

Результативность. На каждом шаге известно,

виде последовательности шагов. Только

что считать результатом этого шага, а сам

выполнив одно предписание, можно приступить

процесс должен закончиться за конечное число

к выполнению следующего.

шагов.

Понятность. Необходимо, чтобы исполнитель

Массовость. Алгоритм применим к целому

мог понять и выполнить каждый шаг

классу однотипных задач, а при решении

предписания.

конкретной задачи из класса исходные данные

Детерминированность. Процесс применения

могут меняться в определенных пределах.

правил к исходным данным (путь решения

задачи) определен однозначно.

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

9

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

10

Кафедра

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

Кафедра

Объекты алгоритма

информатики

информатики

УГАТУ

УГАТУ

Алгоритм – это последовательность

Решение любой задачи предполагает наличие

реальных объектов – объектов задачи.

однозначных понятных исполнителю

Каждый объект задачи имеет свои характеристики

предписаний, исполнение которых позволяет

(атрибуты).

за конечное число шагов получить искомый

Задача о начислении зарплаты сотрудникам

результат, определяемый исходными

Объекты задачи : табельный номер сотрудника,

данными для однотипных задач некоторого

ФИО, оклад, отработанное время, зарплата и т.д.

класса.

Характеристики объектов: ФИО – это строки

символов, а табельный номер, оклад, отработанное

Примечание. Это понятие алгоритма применимо для

время , зарплата – это числовые значения,

практических задач, имеющих решение.

представленные числами или арифметическими

выражениями.

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

11

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

12

Кафедра

Объекты алгоритма

Кафедра

Объекты алгоритма

информатики

информатики

УГАТУ

УГАТУ

Задача о решении системы уравнений

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

Объекты задачи – число уравнений,

компьютер, необходима строгая формализация

коэффициенты уравнений, правые части.

задачи.

Она предполагает замену объектов задачи –

Характеристики объектов: число уравнений,

объектами алгоритма, которые должны

коэффициенты уравнений, правые части – это

наследовать их атрибуты.

числовые значения, представленные

При разработке алгоритма могут появиться и

арифметическими выражениями или числами.

вспомогательные объекты не соответствующие

никаким объектам задачи.

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

13

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

14

Кафедра

Объекты алгоритма

Кафедра

Объекты алгоритма. Константы

информатики

информатики

УГАТУ

УГАТУ

Каждый объект алгоритма имеет собственное имя

Объект алгоритма Константа. Каждая константа

Имя это неизменно, фиксировано и уникально.

имеет фиксированный тип (арифметический,

символьный или другой) и имеет фиксированное,

Имена для объектов устанавливает автор

неизменяемое в данном алгоритме значение,

алгоритма.

соответствующее ее типу.

Рекомендуется выбирать мнемонические имена,

Значение константы обычно определено в условии

которые отражают суть объекта.

задачи и известно до начала разработки

алгоритма.

Например, в некотором списке фамилий определяется

наличие фамилии Иванов. В алгоритме Фамилия – это

объект, а Иванов – символьная константа.

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

15

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

16

Кафедра

Объекты алгоритма. Переменные

Кафедра

Объекты алгоритма

информатики

информатики

УГАТУ

УГАТУ

Переменная – это объект алгоритма, который

Задача: вычислить длину окружности: L = π* D,

имеет определенный фиксированный тип

L (длина), D (диаметр), π (величина постоянная в

(арифметический, символьный или другой) и

любой задаче) – объекты задачи.

который в каждый момент исполнения

Объекты алгоритма

алгоритма имеет единственное значение

входные: pi (константа);

соответствующего типа.

D (переменная)

К моменту использования переменной в

соответствуют объектам задачи

алгоритме ее значение должно быть

выходные: L (переменная)

определено. В ходе выполнения алгоритма

значение переменной может изменяться.

соответствуют объектам задачи

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

17

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

18

Кафедра

Объекты алгоритма. Переменные

Кафедра

Объекты алгоритма. Переменные

информатики

информатики

УГАТУ

УГАТУ

Задача. Вычислить значение функции

Задача. Протабулировать функцию y = sin(x) на

y = arctg(

3

+ b + ln(ac

3

+ b))

заданном промежутке [х0 , хk]

ac

с шагом h.

Объекты алгоритма (переменные):

Объекты алгоритма (переменные):

• входные a, b, c (соответствуют объектам

•

входные x0, xk, h (соответствуют

задачи)

объектам задачи)

• вспомогательные z (используются во время

•

вспомогательные x

вычислений)

z = ac3 + b

•

выходные y (соответствуют

объектам задачи)

• выходные y (соответствуют объектам задачи)

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

19

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

20

Кафедра

Объекты алгоритма. Массивы

Кафедра

Объекты алгоритма. Массивы

информатики

информатики

УГАТУ

УГАТУ

Многие задачи связаны с обработкой больших

В линейной таблице (список) каждому ее

объемов информации, представляющей

элементу соответствует порядковый номер.

совокупность данных, объединенных единым

Для элемента прямоугольной таблицы должны

математическим содержанием или связанных

быть указаны два номера: номер по вертикали

между собой по смыслу.

(номер строки) и номер по горизонтали (номер

столбца).

Такие данные удобно представлять в виде

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

линейных или прямоугольных таблиц.

данных используются массивы.

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

21

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

22

Кафедра

Массивы

Кафедра

Массивы

информатики

информатики

УГАТУ

УГАТУ

Массив – это конечная упорядоченная по индексу

Число индексов определяет размерность массива.

совокупность однотипных данных, имеющая

Количество элементов в массиве определяет его

одно имя.

размер.

Работа с массивом сводится к действиям над его

элементами.

Размерность массива – одномерный. Размер

Индексы определяют положение элемента в

массива равен 5

массиве.

Элемент одномерного массива обозначается

Массив характеризуется – именем, размерностью

переменной с одним индексом

и размером.

ai

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

23

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

24

Кафедра

Массивы

Кафедра

Способы записи алгоритмов

информатики

информатики

УГАТУ

УГАТУ

Размерность массива –

Задача. Найти произведение C n натуральных

чисел, т.е. факториал числа n.

двумерный

n! = 1 × 2 × 3 × … × n

Размер массива равен 12

1. Полагаем C равным единице и переходим к

Элемент двумерного массива обозначается

следующему пункту.

переменной с двумя индексами. Первый индекс

2. Полагаем i равным единице и переходим к

обозначает номер строки, а второй – номер

следующему пункту.

столбца

3. Полагаем C = C × i и переходим к следующему пункту.

bi , j

4. Проверяем, равно ли i числу n. Если i < n, то

увеличиваем i на единицу и переходим к пункту 3.

Если i = n, то вычисления прекращаем.

Входные данные?

Выходные данные?

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

25

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

26

Кафедра

Способы записи алгоритмов

Кафедра

Способы записи алгоритмов

информатики

информатики

УГАТУ

УГАТУ

Задача. Найти наименьшее число М в

1. Полагаем i = 1, переходим к следующему пункту.

последовательности из n чисел a1, a2, …, an.

2. Полагаем М = аi, переходим к следующему

Первоначально предположим М = a1.

пункту.

Затем М сравним с последующими числами

3. Сравниваем i с n, если i < n, переходим к пункту 4,

последовательности, начиная с а2 до тех пор, пока не

если i = n, процесс поиска останавливаем.

найдется число аi < М.

4. Увеличиваем i на 1 и переходим к следующему

Меняем М = аi, и продолжаем сравнение нового М с

пункту.

последующими числами из последовательности,

начиная с а

i+1

и так до тех пор, пока не будут

5. Сравниваем аi, с М. Если аi >= M, то переходим

просмотрены все n чисел.

к пункту 3, иначе (ai < M) переходим к пункту 2.

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

27

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

28

Входные данные?

Выходные данные?

Кафедра

Способы записи алгоритмов

Кафедра

Способы записи алгоритмов

информатики

информатики

УГАТУ

УГАТУ

Задача. Найти наибольший общий делитель

«Школьный» метод:

(НОД) двух натуральных чисел m и n.

Шаг 1 Разложить на простые множители число m.

Входные данные:

m = 60 n = 24

60 = 2 × 2 × 3 × 5

Выходные данные (результат):

Шаг 2 Разложить на простые множители число n.

НОД для чисел m и n.

24 = 2 × 2 × 2 × 3

Шаг 3 Выделить их общие делители. Это 2, 2, 3.

Шаг 4 Перемножить общие делители

НОД = 2 × 2 × 3 = 12

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

29

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

30

Кафедра

Способы записи алгоритмов

Кафедра

Способы записи алгоритмов

информатики

информатики

УГАТУ

УГАТУ

Метод последовательного перебора:

Метод последовательного перебора:

Подобрать наибольшее целое число t – такое,

Шаг 1 Присвоить значение функции min {m, n}

переменной t.

чтобы оба числа делились на него без остатка.

Шаг 2 Разделить m на t. Если остаток равен нулю,

Первоначально

t = min {m, n}.

перейти к шагу 3; иначе перейти к шагу 4.

Выполнение алгоритма можно начать с проверки

Шаг 3 Разделить n на t. Если остаток равен нулю,

делятся ли оба числа, m и n, на t без остатка.

вернуть t в качестве ответа и закончить

Если это так, то число t является ответом; если

работу; иначе перейти к шагу 4.

нет, нужно уменьшить значение t на единицу и

Шаг 4 Вычесть 1 из t. Перейти к шагу 2.

снова выполнить проверку.

Алгоритм не будет корректно работать, если хотя бы один

из его входных параметров равен нулю.

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

31

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

32

Кафедра

Способы записи алгоритмов

Кафедра

Способы записи алгоритмов

информатики

информатики

УГАТУ

УГАТУ

Алгоритм Евклида:

1. Проверяем n = 0, если да, то ответ m, если нет,

то п.2

2. Находим r = m mod n

3. Меняем m = n и n = r

4. Переходим к п.1

нет

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

33

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

34

Кафедра

Способы записи алгоритмов

Кафедра

Способы записи алгоритмов

информатики

информатики

УГАТУ

УГАТУ

Алгоритм Евклида:

1. Проверяем, если m и n ≠ 0, то п. 2, иначе п. 4

2. Проверяем, если m > n, то m = m mod n, иначе

n = n mod m

3. Проверяем, если m и n ≠ 0, то повторяем п. 2

иначе п. 4

4. Проверяем, если m = 0, то НОД = n, иначе

НОД = m

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

35

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

36

Кафедра

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

Кафедра

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

информатики

информатики

УГАТУ

УГАТУ

При составлении алгоритма важно понимать:

При составлении алгоритма важно понимать:

•

Каждый шаг алгоритма должен быть четко и

•

Для решения одной и той же задачи может

однозначно определен.

существовать несколько разных алгоритмов.

•

Должны быть точно указаны диапазоны

•

В основу алгоритмов для решения одной и той же

допустимых значений входных данных, которые

задачи могут быть положены совершенно разные

обрабатываются с помощью алгоритма.

принципы, что может существенно повлиять на

•

Один и тот же алгоритм можно представить

скорость решения этой задачи.

несколькими разными способами.

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

37

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

38

Кафедра

Способы записи алгоритмов

Кафедра

Способы записи алгоритмов

информатики

информатики

УГАТУ

УГАТУ

Задача. Найти количества цифр в заданном

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

десятичном натуральном числе m.

Шаг 1: Задать число m.

Входные данные:

m = 476892

Шаг 2: Cделать k равным 0.

Выходные данные:

количество цифр в числе m.

Шаг 3: Cделать m равным целой части от деления

Алгоритм:

m на 10.

476892 div 10 = 47689

Шаг 4: Увеличить значение k на 1

47689 div 10 = 4768

Шаг 5: Если m не равен нулю, то перейти к шагу 3,

4768 div 10 = 476

если равен 0, то перейти к шагу 6.

476 div 10 = 47

47 div 10 = 4

Шаг 6: Вывести значение k.

4 div 10 = 0

Ответ: 6 цифр

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

39

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

40