Лекция_05_Алгоритмы

1.

1

2.

Дискретность
Детерминированность
Конечность
(финитность)
Результативность
Элементарность
Понятность
Массовость
Завершаемость
2

3.

3

4.

Псевдокод - это система обозначений, предназначенная для неформального представления идей в процессе
разработки алгоритмов.
name = выражение
• Если валовой внутренний продукт растет, покупать обыкновенные акции; в противном случае продавать
обыкновенные акции.
• Покупать обыкновенные акции, если валовой внутренний продукт растет, и продавать их в противном случае.
i f (условие) :
дей̆ствие
else:
действие
В зависимости от того, является год високосным или нет, разделить итог на 366 или 365 соответственно.
i f (год високосный):
ИтогоЗаДень = Итог / 366
else:
ИтогоЗаДень = Итог / 365
4

5.

Мы также примем сокращенный̆ синтаксис этого конструкта:
if (условие):
действие
Итерация - это повторение некоторой части алгоритма до тех пор, пока не будет выполнено заданное условие либо
пока она не будет выполнена указанное количество раз.
Универсальный шаблон:
while (условие):
действие
while (имеются билеты, которые можно продать):
продавать билеты
Упорядоченные (последовательно выполняемые) инструкции, выбор и итерация являются строительными
блоками алгоритмов.
Любой̆ алгоритм может быть реализован с использованием только упорядоченных инструкций, выбора и
итерации.
def имя( ):
If (. . .):
ПредоставлениеЗайма( )
else:
ОтклонениеЗаявки( )
def Сортировка (Список):
5

6.

Фаза 1. Понять существо задачи.
Фаза 2. Разработать план решения задачи.
Фаза 3. Выполнить план.
Фаза 4. Оценить точность решения, а также
его потенциал в качестве средства для
решения других задач.
Фаза 1. Понять существо задачи.
Фаза 2. Предложить идею, какая
именно алгоритмическая процедура
позволила
бы
решить
задачу.
Фаза 3. Сформулировать алгоритм и
представить его в виде программы.
Фаза 4. Оценить точность программы и
ее потенциал в качестве средства для
решения других задач.
6

7.

Задача. Предположим, что некто А хочет определить возраст трех детей некоего В. Этот В сообщает А, что
произведение возрастов его детей̆ равно 36. Обдумав эту подсказку, А отвечает, что необходима еще
подсказка, и В сообщает ему сумму возрастов его детей̆. Затем А отвечает, что требуется еще подсказка, и
В говорит ему, что старший из детей̆ играет на пианино. Услышав эту подсказку, А сообщает В возраст всех
трех его детей. Сколько лет детям?
7

8.

Поменять местами имена David и Alice.
Поместить имя Carol между именами Alice и David.
Поместить имя ВоЬ между именами Alice и Carol.
Нисходящее
проектирование состоит в
пошаговой детализации
(декомпозиции,
разложении) задачи на
подзадачи.
Восходящее
проектирование
–
методика, при которой
крупные
блоки
собираются из ранее
созданных мелких блоков
8

9.

Линейные алгоритмические конструкции
Команда 1
Команда 2
Команда 3
Пример.
Определить значение целой
переменной n после выполнения следующего
алгоритма:
m := 3
n := 4
m := 6 + m*n
n := n + m/3
Решение. Первые две команды присваивания
определяют начальные значения переменных.
Для выполнения третьей команды сначала надо
вычислить правую часть выражения: 6 + 3 х 4 =
18 Это значение будет присвоено переменной
m. Для выполнения последней команды также
сначала вычисляется правая часть выражения:
4 + 18/3 = 10.
Результат будет присвоен переменной п.
Ответ: 10
9

10.

Алгоритмические конструкции ветвления
10

11.

11

12.

12

13.

Циклические конструкции
Структура цикла типа while
Структура цикла типа repeat
while (условие):
действие
13

14.

while (есть еще элементы для анализа):
…
выбрать следующий элемент списка
f o r Элемент i n Список:
…
Сумма = 0
f o r Число i n Список:
Сумма = Сумма + Число
14

15.

Алгоритм сортировки методом вставки
Fred
Alex
Diana
Byron
Carol
Alex
Fred
Diana
Byron
Carol
15

16.

16

17.

переместить опорный элемент во временное хранилище,
оставив в списке пустое место
while (над пустым местом есть имя and
оно по алфавиту размещается ниже опорного элемента):
переместить имя, находящееся над пустым местом, вниз,
оставив в его прежней позиции пустое место
поместить опорный элемент на пустое место в списке
N=2
while (значение N не превышает длину списка):
выбрать N-й элемент списка в качестве опорного элемента
.
.
.
N=N+1
17

18.

def Сортировка (Список):
N=2
while ( значение N не превышает длину списка) :
выбрать N-й элемент списка в качестве опорного элемента
переместить опорный элемент во временное хранилище,
оставив в списке пустое место
w h i l e ( над пустым местоместь имя a n d
оно по алфавиту размещается ниже опорного элемента):
переместить имя, находящееся над пустым местом, вниз,
оставив в его прежней позиции пустое место
поместить опорный элемент на пустое место в списке
N =N + 1
18

19.

19

20.

Рекурсивные структуры
20

21.

21

22.

22

23.

23

24.

24

25.

25

26.

Эффективность и правильность
1. пространственная эффективность (память);
2. временная эффективность;
3. интеллектуальная сложность.
26