Понятие алгоритма и основные алгоритмические структуры

1. Понятие алгоритма и основные алгоритмические структуры

КГБПОУ «Сосновоборский многопрофильный техникум
«Импульс»
Понятие алгоритма и
основные алгоритмические
структуры

2. План:

1 Алгоритмы и способы их описания;
2 Правила построения блок-схем;
3 Этапы решения задач на ЭВМ.

3. Алгоритмы и способы их описания

Алгоритм – строгая система правил или инструкций
для
исполнителя,
определяющая
некоторую
последовательность действий, которая после
конечного числа шагов приводит к достижению
искомого результата.
Дискретность
Конечность
Результативность
Массовость
Определенность

4. Специальные языки

Для
записи
алгоритмов
используются
специальные языки:
1. Естественный язык (словесная запись);
2. Формулы;
3. Псевдокод;
4. Структурограммы;
5. Синтаксические диаграммы;
6. Графический (язык блок-схем).

5. Составление блок-схем

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

1.
2.
Блок-схема
выстраивается
в
одном
направлении либо сверху вниз, либо слева
направо;
Все
повороты
соединительных
линий
выполняются под углом 90 градусов

7. Общими правилами при проектировании визуальных алгоритмов (блок-схем) являются следующие:

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

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

Алгоритм Евклида. Чтобы
найти НОД (наибольший
общий делитель)
двух
натуральных чисел, нужно
вычитать из большего числа
меньшее до тех пор, пока
меньшее не станет равно
нулю. Тогда второе число и
есть НОД исходных чисел.

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

1. Словесный
Алгоритм записывается на естественном языке в виде
последовательно пронумерованных команд, каждая из которых
представляет собой произвольное изложение действия.
Пример:
алгоритм
нахождения
площади
прямоугольника S = a × b, где S – площадь, а, b –
длины его сторон.
Недостатки:
словесная
запись
многословна, трудно
представить сложные
задачи
в
такой
форме,
так
как
словесные описания
строго
не
формализуемы.
1. Начало алгоритма.
2. Задать численное значение стороны a.
3. Задать численное значение стороны b.
4. Вычислить площадь S прямоугольника
по формуле S = a × b.
5. Вывести результат вычислений.
6. Конец алгоритма.

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

2. Графический
Алгоритм изображается в виде последовательности связанных
между собой функциональных блоков (блок-схемы). Каждый блок
соответствует выполнению одного или нескольких действий.
Пример: алгоритм нахождения наибольшего
общего делителя (НОД) двух натуральных чисел:
1. Задать два числа.
2. Если числа равны, то взять любое
из них в качестве ответа и
остановиться, в противном случае
продолжить выполнение алгоритма.
3. Определить большее из чисел.
4. Заменить большее из чисел
разностью большего и меньшего из
чисел.
5. Повторить алгоритм с шага 2.

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

3. Программный
Алгоритм записывается на языке программирования –
системе кодирования предписаний с правилами их применения.
Запись
алгоритма
на
языке
программирования
называется
компьютерной
программой.

12. Анализ алгоритмов с помощью трассировочных таблиц

Трассировочные таблицы – инструмент для пошагового
отслеживания работы алгоритма или программы. Они помогают:
1.
визуализировать изменения переменных;
2.
находить ошибки в логике;
3.
оценивать сложность алгоритма (время/память).

13. Виды трассировочных таблиц

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