Файл: ОСНОВНЫЕ СТРУКТУРЫ АЛГОРИТМОВ: СРАВНИТЕЛЬНЫЙ АНАЛИЗ И ПРИМЕРЫ ИХ ИСПОЛЬЗОВАНИЯ (В C++, PASCALABC, QBASIC).pdf

ВВЕДЕНИЕ

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

Для программиста алгоритмическое мышление является одной из необходимых профессиональных компетенций. Современные компьютеры понимают программы, разработанные на языках программирования, которые сегодня в основном являются алгоритмическими, то есть программа – это алгоритм, записанный на языке программирования.

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

Сегодня насчитывается большое количество языков программирования высокого уровня. Многие из них разработаны для решения произвольных задач – такие языки программирования являются универсальными. Другие языки программирования высокого уровня создавались специально для разработки программ в какой – либо узко специальной области и оснащены инструментальным аппаратом для манипулирования данными и функциями применительно к этой предметной области. Такие языки программирования являются специальными языками программирования высокого уровня.

Изучение языков программирования высокого уровня практичнее начинать со знакомства с универсальными языками. Знакомство с несколькими языками программирования высокого уровня, предназначенными для решения приблизительно одинаковых классов задач, сравнительный анализ реализации в них основных алгоритмических структур дает понимание общности современных подходов к программировании.

В курсовой работе для изучения основных структур алгоритмов и их сравнительного анализа выбраны наиболее популярные универсальные языки программирования высокого уровня: C++ (среда разработки Visual Studio 2010), Pascal (среда разработки и версия PascalABC) и Basic (версия QBasic).

Объектом исследования курсовой работы являются языки программирования высокого уровня.

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

Цель курсовой работы – изучение и сравнительный анализ использования основных структур алгоритмов в языках программирования высокого уровня C++, PascalABC, QBasic.

Задачи курсовой работы:

• изучить алгоритмы и основные структуры алгоритмов;
• изучить способы реализации основных структур алгоритмов в языках программирования C++, PascalABC, QBasic и провести сравнительный анализ;
• представить примеры их практического использования.

1 АЛГОРИТМЫ И ПРОГРАММЫ

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

В IX веке узбекским математиком Мухаммадом Ал-Хорезми были сформулированы пошаговые правила выполнения четырех арифметических действий над числами. В Европе эти правила стали называть алгоритмами от латинской формы написания имени автора – Alchorismi или Algorithmi. В арифметическом трактате ученого Ал-Хорезми описывалась индийская позиционная система счисления и искусство счета в этой системе. Пример - алгоритм сложения и умножения в столбик.

Можно смело говорить о том, что сначала понятие «алгоритм» обозначало десятичную позиционную арифметику и процедуры цифровых вычислений.

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

Алгоритм одно из самых основных понятий вычислительной математики. Это понятие возникло в связи с поисками общих методов решения однотипных задач задолго до появления ЭВМ.

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

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

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

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

• алгоритм Евклида;
• алгоритм Гаусса;
• алгоритм Штурма.

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

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

В конце первой трети двадцатого века годах в работах математиков Д. Гильберта, А. Черча, С. Клини, Э. Поста, А.Тьюринга понятие алгоритма было определено в двух формах:

• на базе понятия рекурсивной функции;
• на базе описания алгоритмического процесса.

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

Рисунок – Алан Тьюринг

При описании различных алгоритмов своей машины (ее так и называют машиной Тьюринга) и утверждении реализуемости разнообразных композиций алгоритмов, автор убедительно изобразил многообразие возможностей разработанной им конструкции и сформировал тезис:

«Всякий алгоритм может быть реализован соответствующей машиной Тьюринга».

Тезис Тьюринга считается формальным определением алгоритма.

Советский математик А.А. Марков ( рисунок 2) в 1954 году предложил свою формулировку алгоритма;

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

Рисунок – Андрей Андреевич Марков

1.2 Свойства алгоритма

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

Алгоритм — руководство к действию для исполнителя. В связи с этим описанием алгоритма считают, что значение слова «алгоритм» близко по смыслу к значению слов «указание» или «предписание».

Алгоритм — понятное и точное предписание (указание) исполнителю совершить определенную последовательность действий для достижения указанной цели или решения поставленной задачи.

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

Алгоритм должен отвечать определенному набору свойств. Основные свойства алгоритма представлены на рисунке 3.

Рисунок – Свойства алгоритма

1. Массовость.

Алгоритм имеет определенное количество входных параметров — аргументов, описанных до начала выполнения.

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

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

1. Понятность.

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

1. Дискретность.

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

1. Конечность.

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

1. Определенность.

Каждое предписание алгоритма должно быть отчетливо и недвусмысленно сформулировано. Не допускается произвольной трактовки команд исполнителем. Фактически алгоритм рассчитан на исключительно механическое исполнение. Свойство определенности алгоритма предоставляет специалистам полностью доверить его исполнение автомату.

1. Эффективность.

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

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

Набор команд, которые может реализовать конкретный исполнитель, называется системой команд исполнителя.

1.3 Способы описания алгоритмов

Существует несколько способов задания алгоритмов.

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

Пример словесного описания алгоритма Евклида для определения НОД двух чисел представлен на рисунке 4.

Рисунок – Алгоритм Евклида

Графическое описание алгоритма осуществляется в виде специальных графических объектов – блок-схем.

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