Тема 2.2. Основы алгоритмизации и программирования (базовая часть).

Цели и задачи. Изучить понятие алгоритма, основные алгоритмические структуры (следование, ветвление, цикл), освоить способ представления алгоритма в виде блок-схемы и его запись на языке программирования высокого уровня.

Справочный материал.

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

- ввод исходных данных;

- преобразование исходных данных через промежуточные данные в конечные результаты;

- вывод полученных результатов.

Алгоритм обычно предназначен для определенного исполнителя, в качестве которого может выступать человек, устройство, компьютер и т. д. Любой исполнитель имеет свойство выполнять определенные действия (команды). Система команд исполнителя – это совокупность всех действий, которые могут быть им выполнены. Алгоритм записывается в командах того исполнителя, который будет его выполнять. Каждая команда имеет четкое описание производимых ею действий и применяется к определенному объекту. Все объекты составляют так называемую среду исполнения.

Разработка алгоритма - наиболее сложная часть решения. Требуется проанализировать задачу и составить такую последовательность понятных исполнителю действий, которая, изменяя исходные данные, поэтапно позволит получить решение за конечное число шагов Данные, полученные в результате выполнения одного действия, можно использовать на следующем шаге. Каждое действие алгоритма, как правило, должно соответствовать системе команд исполнителя, либо описывать более простую задачу, алгоритм решения которой уже известен.

Порядок составления алгоритма можно описать следующим образом:

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

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

- указывается порядок выполнения действий над данными, при этом обязательно нужно предусмотреть порядок окончания работы алгоритма;

- определяется, что должно быть результатом решения задачи.

Процесс разработки алгоритма называется алгоритмизацией. В зависимости от порядка выполнения действий по базовой структуре алгоритмы можно разделить на линейные (последовательные), разветвляющиеся, циклические и рекурсивные. Алгоритм каждой базовой структуры детально описан в [7],[12]. В одном алгоритме можно использовать различные структуры. К получению однозначного результата решения задачи могут привести различные алгоритмы. При выборе оптимального алгоритма следует использовать такие критерии, как точность полученного решения, время выполнения, количество действий, простота и т. д. Алгоритм, как правило, тестируют на различных значениях исходных данных для проверки правильности его работы.

Для записи алгоритма наиболее часто используют два способа - графический (в виде блок-схемы) или программный (с помощью языка программирования). Также можно применить псевдокод или словесное описание.

Блок-схема - описание структуры алгоритма с помощью связанных геометрических фигур, показывающих порядок выполнения отдельных действий. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т. п.) соответствует геометрическая фигура, называемая блоком. Блочные символы соединяются линиями переходов (стрелками), определяющими очередность выполнения действий. Система символов и правила построения алгоритмов определены соответствующими стандартами (ГОСТ 19.701-90 «СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ, ДАННЫХ И СИСТЕМ).

Программа это алгоритм, записанный в виде последовательности команд, исполнителем которых является компьютер (ЭВМ). При записи алгоритмов в виде программ для ЭВМ используются языки программирования. Под языком программирования понимают систему кодирования команд и правила их записи. Такие языки являются искусственными (формальными) языками, имеют ограниченный набор слов (операторов), строгие правила записи (синтаксис), могут быть низкого уровня (ориентированы на команды процессора и учитывать его особенности) или высокого уровня (ближе к естественному языку, не зависят от конкретной компьютерной архитектуры и ориентированы "на человека"). Существует большое количество языков программирования, предназначенных для решения прикладных задач.

Примеры задач и образцы их решения.

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

Решение:

Исполнителем алгоритма решения данной задачи является ЭВМ, объекты, понятные исполнителю – переменные (ячейки памяти), система команд исполнителя – запись, чтение, сравнение, ввод и вывод, арифметические действия над переменными. С помощью действий над исходными числовыми значениями, требуется получить результат решения задачи (также в виде числа).

Опишем действия алгоритма.

Исходные данные задачи – неотрицательные двузначные целые числа из диапазона [10; 99]. Результат – сумма чисел этого диапазона, которые удовлетворяют двум условиям – являются неотрицательными и четными (делятся на 2 без остатка).

Изначально результат равен нулю. Исполнитель (ЭВМ) должен проверить каждое число, начиная с 10, на четность, и, в случае выполнения условия, добавить число в результат (сумму). Последним проверяемым числом является 99.

Как было сказано выше, конкретных алгоритмов решения одной задачи может быть несколько, различаются они своей эффективностью. В данной задаче ключевым местом алгоритма можно считать определение четности числа. В одном случае числа можно перебирать с шагом 2 и складывать (если начать с 10, то следующим четным будет 10+2=12, а последним – 98), в другом - добавлять к числу 10 значение 1, пока не получим 100, и сравнивать остаток от деления получаемого числа на двойку с нулем или результаты целочисленного и обычного деления числа на 2. Во втором случае алгоритм менее эффективен по количеству действий, так как перебрать придется все заданные числа, каждое разделить пополам и сравнить остаток от деления c 0. Однако результат решения задачи в разных алгоритмах должен совпадать.

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

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

Определим имена переменных для хранения данных и условия изменения их значений. Хранить в памяти ЭВМ все 90 чисел не нужно, достаточно записать первое число (10) в переменную (назовем ее i), обработать его (проверить на четность и в случае успеха добавить значение i в сумму - переменную S), далее прибавить к i значение 1 и получить в i новое число, проверить, не превысило ли i конечного значения диапазона (99), повторить обработку i, получить новое число и т.д.

Проверку условия четности i будем выполнять сравнением результатов обычного (i/2) и целочисленного (i\2) деления числа на двойку: если результаты делений совпадают (условие i/2=i\2 выполнено), то в i – четное число и его необходимо прибавить к результату (сумме). Однако в языке VBA проверить четность можно и другим способом (найти команду проверки четности самостоятельно).

В алгоритме обычно предусмотрена инициализация используемых переменных (задание их начальных значений). Для i это 10 (первое обрабатываемое число диапазона), для S – ноль. Инициализация переменных – важное действие алгоритма, ее отсутствие может привести к неверному результату решения задачи.

Описанный порядок действий алгоритма представлен в виде блок-схемы на рис. 20.

Рис.20. Алгоритм решения задачи 2.2.1 в виде блок—схемы.

Заметим, что данный алгоритм легко приспособить для нахождения количества или произведения четных чисел из того же диапазона. Для поиска количества переименуем везде переменную S в К (это имя лучше отражает содержимое переменной - Количество, однако переименовывать не обязательно, главное в алгоритме – значение, а не имя переменной), а вместо действия S=S+i будем выполнять K=K+1 – прибавление 1 к переменной К означает подсчет количества.

Для поиска произведения - аналогичные действия: вместо S будет P, S=S+i заменим на P=P*i. Кроме того, обязательна инициализация P=1, в противном случае произведение окажется всегда равным нулю.

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

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

Для записи на основе блок-схемы алгоритма программы на языке высокого уровня и ее выполнения используем язык Visual Basic for Application (VBA) пакета Microsoft Office и редактор VBA Microsoft Excel.

В редакторе VBA Microsoft Excel программу можно оформить в виде процедуры - макроса (Sub) или функции (Function). Текст программы вводится в модуль, принадлежащий VBA-проекту рабочей книги Excel. Подробно работа с редактором VBA, способы оформления и записи программ рассмотрены в [5].

В VBA не обязательно указывать тип значения для используемых переменных, однако это экономит память, отводимую для хранения данных. В задаче речь идет только о целых числах, входные и выходные данные предполагаются небольшие по значению, поэтому с помощью оператора Dim для переменных i и S определим тип данных Integer (2 байта для хранения значения переменной, диапазон значений от -215 до 215-1).

В алгоритме присутствует циклическая структура, число повторений действий которой известно. Для ее реализации в языке VBA используем оператор FOR, переменная цикла i, ее начальное значение 10, конечное 99.

Для записи условия проверки четности числа служит оператор If. Для вывода результатов – функция MsgBox. Полный текст программы для задачи 2.2.1 в редакторе VBA Microsoft Excel 2010 представлен на рис. 21.

Рис. 21. Текст программы для задачи 2.2.1 на VBA для MS Excel 2010.

Выполнение программы, оформленной в виде макроса, в MS Excel осуществляется через меню Макросы вкладки Разработчик (или Alt+F8). Скриншот с результатами работы программы для задачи 2.2.1 представлен на рис. 22.

Рис. 22. Результат выполнения программы для задачи 2.2.1 на VBA для MS Excel.

Задача 2.2.2. Провести анализ и составить блок-схему алгоритма, определяющего принадлеж­ность точки с координатами (x,y) закрашенной области (I или II) на рис.23.

Рис. 23. Исходные данные к задаче 2.2.2.

Решение:

Прежде чем переходить к построению алгоритма, проведем поэтапный анализ задачи.

1. Условием нахождения точки с координатами (x,y) внутри окружности (включая границы) (закрашенная область А на рис.24) является выполнение неравенства .

 

А


Рис. 24. Область А: .

2. Условием нахождения точки с координатами (x,y) внутри параболы (закрашенная область B на рис. 25) является выполнение условия .

 

B

Рис. 25. Область B: .

 

3. Условием нахождения точки с координатами (x,y) выше прямой y=1.5 (закрашенная область С на рис. 26) является выполнение неравенства только для значения y:

 

C
Рис. 26. Область C: .

 

4. Условием нахождения точки с координатами (x,y) ниже оси ОХ (закрашенная область D на рис. 27) является выполнение неравенства .

 

D
Рис. 27. Область D: .

 

 

Теперь заметим, что областьI на рис. 23 является пересечением областей А и D, т.е. для точки с координатами (x,y) попадание в I определяется выполнением условий, записанных в виде системы неравенств

(1)

Область II (рис. 23) более сложная. Она представляет собой пересечение областей A, B и C, т.е. для попадания в II точки с координатами (x,y) требуется одновременное выполнение условий

(2)

Поскольку области I и II не пересекаются (точка попадает или в I, или в II), то условие принадлежности точки (x,y) областям будет заключаться в проверке выполнения совокупности системы неравенств (3):

(3)

Запишем данную совокупность в виде логического выражение и упростим его (см. тему 2.3 Раздела II настоящих методических указаний):

, (4)

где А, B, C и D являются неравенствами, соответствующими закрашенным областям на рис. 24-27.

Анализ полученного логического выражения (4) позволяет сделать вывод, что в алгоритме потребуется проверить 4 условия: точка с координатами (x,y) принадлежит закрашенной области рис. 23, при обязательном выполнении условия Аи одного из условий D или B или C.

Рис. 28. Блок-схема алгоритма решения задачи 2.2.2.

В качестве самостоятельной работы на основе полученной блок-схемы (рис. 28) можно записать и выполнить алгоритм на языке высокого уровня (например, в среде программирования VBA для MS Excel).

Индивидуальные варианты задач по Теме 2.2 "Основы алгоритмизации и программирования".

Задача 2.2.1.Описать словесно алгоритм решения задачи, оформить алгоритм в виде блок-схемы и записать на ее основе программу на языке высокого уровня. Привести скриншот результатов выполнения программы в выбранной среде программирования.

№ Задача
Найти сумму всех нечетных отрицательных двузначных чисел, кратных 3.
Найти произведение чисел из диапазона [-50;50], кратных 13 и 10 одновременно.
Найти количество всех трехзначных чисел, кратных 4 и 6.
Найти сумму степеней 2, где n – нечетное целое число от 1 до 10.
Найти количество всех трехзначных чисел кратных 2 и не кратных 3.
Найти произведение нечетных чисел из диапазона [-100;100], кратных 15.
Найти сумму степеней 3n, где n – четное, кратное 3 целое число от 0 до 20.
Найти количество четных четырехзначных чисел, заканчивающихся на 0 или 5.
Найти произведение отрицательных четных двузначных чисел, кратных 13.
Найти сумму всех двузначных чисел, кратных 2 и 3 одновременно.
Найти количество четных неотрицательных двузначных чисел с одинаковыми цифрами.
Найти произведение четных отрицательных двузначных чисел, кратных 20.
Найти сумму квадратов неотрицательных двузначных чисел с разными цифрами.
Найти количество четных трехзначных чисел с одинаковыми цифрами.
Найти произведение нечетных чисел из диапазона [-60;60], кратных 20.
Найти сумму кубов нечетных чисел от 1 до 50, не кратных 3.
Найти количество четных чисел от 1 до 500, кратных 9.
Найти произведение четных чисел от 1 до 50, кратных 7.
Найти сумму квадратов нечетных чисел от 10 до 80, не кратных 3.
Найти количество нечетных чисел от 100 до 500, кратных 14.

Задача 2.2.2 (дополнительная часть).Провести анализ и составить блок-схему алгоритма, определяющего принадлеж­ность точки с координатами (x,y) закрашенной области на заданном рисунке.

№ Рисунок № Рисунок