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

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

История термина «алгоритм»

Слово "Алгоритм" происходит от имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика из Хорезма (город в современном Узбекистане) Мухаммеда ибн Мусу аль-Хорезми.

Сведений о жизни учёного сохранилось крайне мало.

Родился в Хорезме в 783 году. Согласно родословной происходил из рода зороастрийских жрецов, позже принявших ислам.

Значительный период своей жизни он провёл в Багдаде, возглавляя при халифе аль-Мамуне (813-833) библиотеку « Дома мудрости ».

Примерно в 830 году Мухаммад ибн Муса аль-Хорезми создал первый известный арабский трактат по алгебре. В своих трудах по арифметике и алгебре разработал правила выполнения четырёх арифметических операций над многозначными десятичными числами. Эти правила определяют последовательность действий, которые необходимо выполнить, чтобы получить сумму чисел, произведение и т.д. Первоначально только эти правила и назывались алгоритмами. В дальнейшем термин «алгоритм» стали использовать вообще для обозначения последовательности действий, приводящей к решению проблемы.

Мухаммад ибн Муса аль-Хорезми

АЛГОРИТМ

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

Как открыть дверь ключом?

1. Достать ключ

2. Вставить ключ в замочную скважину

3. Повернуть ключ 2 раза против часовой стрелки

4. Вынуть ключ

Блок–схема алгоритма

Элемент блок-схемы

Назначение элемента блок-схемы

Применяется для обозначения начала или конца алгоритма

Предназначен для описания ввода или вывода данных

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

Проверка выполнения условий для принятия решения

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

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

СВОЙСТВА АЛГОРИТМОВ

• Конечность алгоритма

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

• Доступность алгоритма

• Массовость алгоритма

• Структура данных алгоритма

• Дискретность алгоритма

Типовые алгоритмические конструкции

• Линейная конструкция (следование)
• Разветвляющаяся конструкция

(ветвление)

• Циклическая конструкция (цикл)

НАЧАЛО

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

ВВОД

- ВСЕ КОМАНДЫ ВЫПОЛНЯЮТСЯ СТРОГО ПОСЛЕДОВАТЕЛЬНО ДРУГ ЗА ДРУГОМ

Блок исполнительных

действий

ВЫВОД

S

КОНЕЦ

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

Да

КОМАНДА ВЕТВЛЕНИЯ – ЭТО СОСТАВНАЯ КОМАНДА, В КОТОРОЙ ТА ИЛИ ИНАЯ СЕРИЯ КОМАНД ВЫПОЛНЯЕТСЯ ПОСЛЕ ПРОВЕРКИ УСЛОВИЯ

Нет

Условие

Серия 1

Серия 2

Ветвление имеет полную или не полную форму

Да

Нет

Да

Условие

Нет

Условие

Серия 1

Серия 2

Серия 1

B Да Нет M:=A-В M:=B-А ВЫВОД M КОНЕЦ " width="640"

НАЧАЛО

ВВОД

A, B

AB

Да

Нет

M:=A-В

M:=B-А

ВЫВОД

M

КОНЕЦ

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

СУЩЕСТВУЕТ ТРИ ТИПА КОМАНД ПОВТОРЕНИЯ

ОТЛИЧИЕ - СПОСОБ ПРОВЕРКИ

ОКОНЧАНИЯ ЦИКЛА

НАЧАЛО

ЦИКЛ «ПОКА»

I:=1

I

Нет

Да

I

I:=I+2

КОНЕЦ

ЦИКЛ «ДЛЯ»

НАЧАЛО

Да

I=1,10,2

Нет

I

КОНЕЦ

10 Нет КОНЕЦ " width="640"

ЦИКЛ «ДО»

НАЧАЛО

I

I:=I+2

Да

I10

Нет

КОНЕЦ

ЭТАПЫ РЕШЕНИЯ ЗАДАЧ НА ЭВМ

1.Постановка задачи

2.Математическая модель.

3. Конструирование алгоритма.

4. Перевод алгоритма в программу.

5. Ввод и испытание программы.

6. Получение и анализ результатов решения задачи.

ЗАДАЧА

Определить время встречи двух

пешеходов, идущих навстречу

друг другу, если известно, что

расстояние между пешеходами L,

скорость первого пешехода V1,

скорость второго пешехода V2.

0, V10, V20, T0 Найти: T - ? V1 V2 L " width="640"

ПОСТАНОВКА ЗАДАЧИ

Дано: L, V1, V2

L0,

V10,

V20,

T0

Найти: T - ?

V1

V2

L

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

L = V1*T + V2*T = T*(V1+V2)

T = L / (V1 + V2)

НАЧАЛО

Блок-схема алгоритма

ВВОД

L ,V1, V2

T=L / (V1 + V2)

ВЫВОД

T

S

КОНЕЦ

Сконструировать алгоритм деления двух чисел M=A/B .

а) Разветвляющийся;

б) Циклический.