ОБЩИЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ

По дисциплине

«АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ»

 

 

Новочеркасск 2007

УДК 681.3(076.5)

 

 

Рецензент – доцент В.В. Луценко

 

 

        

 

Составитель Бондаренко А.И.

 

    Методические указания к практическим занятиям  по дисциплине «Алгоритмизация и программирование» / Сост. А.И. Бондаренко; Шахтинский ин-т (филиал) ЮРГТУ (НПИ). – Новочеркасск: ЮРГТУ, 2007. - 16 с. – 50 экз.

 

    Методические указания содержат теоретический материал и задачи для разработки алгоритмов.

Предназначены для студентов первого курса специальностей 230201«Информационные системы и технологии» и 0808001 «Прикладная информатика».

 

УДК 681.3(076.5)

© Шахтинский институт ЮРГТУ, 2007

© Бондаренко А.И., 2007

Содержание

 

1. Общие сведения об алгоритмах........................................................... 4

2. Линейные вычислительные алгоритмы.............................................. 7

3. Разветвляющиеся алгоритмы............................................................... 8

4. Циклы................................................................................................... 10

5. Массивы............................................................................................... 12

6. Разработка типовых алгоритмов........................................................ 14

Библиографический список.....................................................................15

 

 

 

ОБЩИЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ

 

Одним из основных этапов решения задачи на ЭВМ является разработка алгоритма, т.е. сведение её к последовательности конечного числа операций, которую необходимо выполнить в определённом порядке, чтобы получить нужный результат. Именно последовательность действий обозначается ёмким словом - алгоритм. Это порядок решения задачи. Этим понятием мы часто пользуемся и в повседневной жизни. Например, в кулинарии, при приготовлении лекарств и т.д. Алгоритмы представляют самостоятельную ценность как интеллектуальные ресурсы общества.

Строгое математическое определение термина “алгоритм” принадлежит математикам А. Н. Колмогорову и А. А. Маркову. Проблемы, связанные с изучением самого понятия алгоритма, выросли в настоящее время в отдельную “теорию алгоритмов”. Потребность такой теории вызвана бурным развитием ЭВМ, а также средств автоматизированного проектирования промышленных роботов, автоматизированных линий, систем управления. Во всех случаях требуется создание алгоритмов выполнения тех или иных операций разной степени сложности. Что же мы называем алгоритмом?

В соответствии с ГОСТ 19. 004-80 “алгоритм – точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату”. В литературе встречаются различные трактовки термина “алгоритм”. Приведем их.

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

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

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

Например, в "Началах" древнегреческого математика Евклида (III век до н.э.) описан алгоритм нахождения наибольшего общего

 

4

делителя (НОД) двух заданных чисел двух чисел. Евклид писал:

а) «обозревай два числа и переходи к следующему указанию;

    б) если числа равны, то каждое из них есть НОД, если нет –

переходи к следующему указанию;

    в) вычитай из большего числа меньшее и обозревай два числа:

        вычитаемое и разность. Переходи к указанию б)».

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

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

п.1 Вычислить полупериметр треугольника p=(a+b+c)/2 Þ п.2

п.2 Вычислить S= Þ п.3

п.3 Вывести на печать значение S , как искомый результат и прекратить вычисления.

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

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

Составление блок-схем алгоритмов осуществляется в соответствии с требованиями ГОСТ 19701–90 “Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения”.

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

 

 

5

Рис.1. Условные обозначения блоков выполняемых действий

 

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

Алгоритм должен обладать следующими свойствами:

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

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

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

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

6

Алгоритм, записанный на языке программирования, называется программой. В этом случае алгоритм представляется в виде последовательности операторов языка. Языки программирования - изобразительные средства для непосредственной реализации программы на ЭВМ.

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

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

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