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

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

Термин “алгоритм” происходит от имени узбекского ученого IX века аль-Хорезми́, который изложил правила арифметических действий над числами в десятичной системе счисления. Эти правила и называли алгоритмами.
Т.о., правила сложения, вычитания, деления, умножения чисел, правила преобразования алгебраических выражений, правила построения геометрических фигур, правила правописания слов и предложений, различные правила и инструкции, представляющие собой подробные указания, годные в однотипных ситуациях – всё это алгоритмы.

Пример
(линейного) алгоритма
Начало
Конец

Алгоритмизация вычислительного процесса включает следующие действия:
Последовательная декомпозиция задачи, выделение автономных этапов вычислительного процесса и разделение каждого этапа на отдельные шаги.
Формализация задачи, перевод задачи на язык математических формул, уравнений, отношений.

3. Построение алгоритма, определение общего порядка выполнения этапов и/или шагов.
4. Проверка правильности алгоритма.
Далее следует программирование на определенном языке в определенной системе программирования.
Затем перед использованием программы выполняется отладка и тестирование.

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

3. Массовость – возможность решения по одному алгоритму множества однотипных задач.
4. Результативность – алгоритм должен обеспечивать возможность получения результата после конечного числа шагов.

Способы описания алгоритмов
Словесный – это последовательное описание основных этапов обработки данных в произвольном изложении на естественном языке.
Пример словесного способа записи алгоритма нахождения НОД двух чисел:
Если числа равны, то взять любое из них в качестве ответа, в противном случае – продолжить выполнение алгоритма;
Определить большее из чисел;
Заменить большее число разностью большего и меньшего чисел;
Повторить алгоритм сначала.

2. Графический – это метод блок-схем. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Для начертания схем алгоритмов используется набор символов, определяемых государственным стандартом:

3. Псевдокод – представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Псевдокод занимает промежуточное место между естественным и формальным языками.
Примером псевдокода может являться алгоритмический язык:
алг Сумма квадратов (арг цел n, рез цел S)
дано | n > 0
надо | S = 1*1 + 2*2 + 3*3 + ... + n*n
нач цел i
ввод n;
S:=0
нц для i от 1 до n
S:=S+i*i
кц
вывод "S = ", S
кон

4. Программный способ представления алгоритмов – осуществляется с помощью языков программирования.

Данные и величины

Каждая величина занимает определенное место в памяти – ячейку, а значение этой величины определяется двоичным кодом в этой ячейке.

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

Линейный алгоритм
Линейный алгоритм – это тип алгоритма, в котором последовательность действий не меняется в процессе его выполнения.

Задача 1. Составить блок-схему линейного алгоритма посадки дерева.

В алгоритмах линейной структуры инструкции выполняются последовательно, одна за другой, т.е. линейно. Алгоритмы и программы с линейной структурой являются простейшими используются, как правило, для реализации простых вычислений по формулам.

начало
y1 := 3*3
y2 := 2*3
x := y1 – y2
вывод x
конец
начало
x := 3*3 – 2*3
вывод x
конец

Правила записи математических выражений в блок-схемах

Примеры записи арифметических выражений
или

Типичные ошибки в записи выражений
2x+1
b + sin x
((x + y)*2 / (b+1)

Задача 2. Записать по правилам алгоритмического языка следующие выражения:

Задача 3. Записать в обычной математической форме арифметические выражения:
а) d*c/2/(R+a*a)
б) abs (x) / 3 / z + x * x

Златопольский Д.М. Сборник задач по программированию.
Стр. 5, № 1.14. – 1.17.

начало
ввод a, b, c
p := (a+b+c)/2
S := sqrt (p*(p-a)*(p-b)*(p-c))
вывод S
конец

Составить блок-схемы алгоритмов по следующим задачам.
Задача 4. Даны два действительных числа. Получить их сумму, разность и произведение.
Задача 5. Даны два действительных числа. Получить их среднее арифметическое.
Задача 6. Даны катеты прямоугольного треугольника. Найти площадь треугольника и его гипотенузу.
Задача 7. Написать алгоритм деления одной обыкновенной дроби на другую обыкновенную дробь.

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

8. Составить блок-схему алгоритма по следующей задаче.
Из трех монет одинакового достоинства одна фальшивая (более легкая). Как ее найти с помощью одного взвешивания на чашечных весах без гирь?

Алгоритм разветвляющейся структуры содержит как минимум одно условие, в зависимости от которого будет выполнено одно или другое действие.

Пример.
Написать алгоритм
вычисления функции Y,
используя систему:
начало
ввод x
x>0
вывод Y
конец
Да
Нет

Алгоритм обхода
Алгоритм обхода является разновидностью разветвляющегося алгоритма и применяется, когда одна из ветвей не содержит ни одного действия.
Пример. Даны числа x, y, z. Найти максимальное значение.

начало
ввод x, y, z
max := x
y>max
нет
max := y
z>max
конец
Вывод max
max := z
нет
да
да

15. Даны два действительных числа. Вывести первое число, если оно больше второго, и оба числа, если это не так.
16. Даны два действительных числа. Заменить первое число нулем, если оно меньше или равно второму, и оставить числа без изменения в противном случае.
17. Даны три действительных числа. Вывести на экран те из них, которые принадлежат интервалу [1..5].

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

Алгоритм циклической структуры – это такой алгоритм, в котором повторяются одни и те же действия.
Существует два типа циклических алгоритмов: цикл с предусловием и цикл с постусловием.
Алгоритм подготовки домашнего задания – цикл с предусловием: сначала задается условие, затем выполняются действия. Таким образом, в цикле с предусловием тело цикла может не выполниться ни разу.
Алгоритм поиска Золушки включает в себя цикл с постусловием: сначала выполняются 2 действия (встретить и примерить), а затем уже проверяется условие. Таким образом, действия в цикле с постусловием всегда будут выполнены хотя бы 1 раз.

Цикл с предусловием
Цикл с постусловием

Пример. Дано целое положительное число N. Найти N! (факториал).
Факториал числа N – это произведение всех натуральных чисел от 1 до N включительно. Факториал числа 0! = 1.
Если N=5, тогда N!=1*2*3*4*5=120
Для составления алгоритма понадобятся три переменные целого типа:
N – аргумент,
i – промежуточная переменная,
F – факториал числа, т.е. результат.

начало
ввод N
F := 1
i := 1
i <= N
F := F * i
i := i + 1
вывод F
конец
да
нет

22. Одна штука некоторого товара стоит 20,4 рубля. Напечатать таблицу стоимости от 2 до 30 штук товара.
23. Спортсмен в первый день пробежал 10 км. Каждый следующий день он увеличивал норму на 10% от нормы предыдущего дня. Какой путь пробежит спортсмен на 7 день.

31. Вывести таблицу соответствия между весом в фунтах и весом в килограммах для значений 1, 2, 3, …, 22 фунта. 1 фунт = 453 грамма.
32. Вывести таблицу перевода расстояний дюймов в сантиметры для значений
10, 12, 14, …, 30 дюймов. 1 дюйм = 2, 54 см.

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

Пример. Составить алгоритм нахождения суммы квадратов чисел от 1 до 10.
Исходная схема алгоритма:
начало
Вычислить сумму
квадратов чисел от 1 до 10
вывести результат
конец

Детализированная
схема алгоритма:
начало
вывести Sum
конец
Sum := 0
нужен ли еще один элемент?
нет
добавить к сумме
новый элемент
да
получить следующий
элемент

Итоговая
схема алгоритма:
начало
вывод Sum
конец
Sum := 0
i := 1
i <= 10
нет
Sum := Sum + i * i
да
i := i + 1

33. Найти сумму всех целых чисел от 1 до 10.
36. Найти среднее арифметическое всех целых чисел от 30 до 100.
38. Известна масса каждого из 12 предметов. Определить общую массу всего набора предметов.