Реферат: Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок схем на языке Turbo Pascal

<img src="/cache/referats/15033/image001.gif" align=«left» hspace=«12» v:shapes="_x0000_s1117">ИНСТИТУТ

КАЛИНИНГРАДСКАЯ ВЫСШАЯ ШКОЛА УПРАВЛЕНИЯ

РЕФЕРАТ

по теме

Понятие алгоритма, его свойства.Описание алгоритмов с помощью блок схем на языке TurboPascal

студент:Чижов Н. А.

группа:02-СА9(2)

Калининград

2003

Содержание:

Введение………………………………………………………………

Алгоритм. Свойства алгоритма……………………………………..

Описание алгоритмов на естественном языке……………………..

Описание алгоритмов с помощью блок-схем……………………...

Заключение…………………………………………………………...

Список литературы…………………………………………………..

Введение.

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

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

Само слово «алгоритм»возникло из названия латинского перевода книги арабского математика IXвека Аль-Хорезми «AlgoritmidenumeroIndoru», что можно перевести как «ТрактатАль-Хорезми об арифметическом искусстве индусов». Составление алгоритмов ивопросы их существования являются предметом серьёзных математических исследований.

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

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

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

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

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

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

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

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

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

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

2,3, +

Проследим выполнение этойпрограммы. Первая операция — считывание в стёк значения 2. Затем в стёксчитывается второе значение (3). Первое значение при этом сдвигается во вторуюячейку памяти. Третий шаг выполнения программы – вычисление суммы двухсчитанных значений (они называются операндами).Результат этой операции – значение 5 – записывается в первую ячейку стёка.

Был рассмотрен примерпростейшей программы. Она является записью алгоритма решения некоторого классазадач – задач вычисления суммы двух чисел. Обозначим эти числа aи b. Тогда алгоритм можно записать следующимобразом:

1.

Считать число a.

2.

Считать число b.

3.

Выполнить суммирование c:= a+ b.

4.

Вывести число c.

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

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

а:= а + 1

воспринимается программистомсовершенно естественно, а уравнение

a= a+1

математик сочтёт неверным. В первомслучае имеется в виду вычисление суммы содержимого ячейки а

и числовой константы 1и занесение полученного результата вту же ячейку а. Второйслучай равносилен неверному тождеству 0 = 1.

Оставималгоритм решения следующей задачи. Пусть заданы два значения xи y. Необходимо сравнить эти значения инапечатать имя большей переменной. Для этой задачи достаточно сравнить обазначения и в зависимости от результата сравнения вывести на печать символ «х» исимвол «у»:

1.

Ввести значение x.

2.

Ввести значение y.

3.

Если x< y, то напечатать «у», иначе напечатать«х».

В этом алгоритмеиспользуются алгоритмические структуры- линейная последовательность операцийи ветвление (шаг 3, условныйоператор). Последняя структура называется так потому, что после передачи в неёуправления выполнение алгоритма может пойти по одному из двух возможныхветвлений. То, какая ветвь будет выбрана, зависит от выполнения условия.Линейная последовательность в данном примере состоит из блоков ввода/вывода данных.

Для записи алгоритмовиспользовался естественный язык. Иногда используют полуформальный язык с ограниченнымсловарём (часто на основе английского языка), промежуточный между естественнымязыком и языком программирования. Такой язык называется псевдокодом. Запись алгоритма на псевдокоде называется структурным планом. Псевдокод удобентем, что позволяет программисту сосредоточиться на формулировке алгоритма, не задумываясьнад синтаксическими особенностями конкретного языка программирования.

Описание алгоритмов с помощью блок-схем.

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

SHAPE * MERGEFORMAT <img src="/cache/referats/15033/image002.gif" v:shapes="_x0000_s1040"> Начало/конецалгоритма

SHAPE * MERGEFORMAT <img src="/cache/referats/15033/image003.gif" v:shapes="_x0000_s1067"> Передачауправления

SHAPE * MERGEFORMAT <img src="/cache/referats/15033/image004.gif" v:shapes="_x0000_s1060"> Вводданных

SHAPE * MERGEFORMAT <img src="/cache/referats/15033/image005.gif" v:shapes="_x0000_s1070"> Блоквычислений

SHAPE * MERGEFORMAT <img src="/cache/referats/15033/image006.gif" v:shapes="_x0000_s1076"> Начало(заголовок) цикла

SHAPE * MERGEFORMAT <img src="/cache/referats/15033/image007.gif" v:shapes="_x0000_s1082"> Конеццикла

SHAPE * MERGEFORMAT <img src="/cache/referats/15033/image008.gif" v:shapes="_x0000_s1095 _x0000_s1085 _x0000_s1088 _x0000_s1091 _x0000_s1094"> Ветвление

SHAPE * MERGEFORMAT <img src="/cache/referats/15033/image009.gif" v:shapes="_x0000_s1101"> Выводданных

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

при

Числоваяпоследовательность <img src="/cache/referats/15033/image015.gif" v:shapes="_x0000_i1035"><img src="/cache/referats/15033/image017.gif" v:shapes="_x0000_i1036"> сходится к искомомузначению. Выполним только 5 итераций метода, считая, что при этом будетдостигнута достаточно хорошая точность. Обычно десяти итераций метода Геронаболее чем достаточно для достижения хорошей точность расчёта. Оба вариантазаписи алгоритма:

1.

Ввести х.

2.

Присвоить <img src="/cache/referats/15033/image020.gif" v:shapes="_x0000_i1037">

3.

Присвоить <img src="/cache/referats/15033/image022.gif" v:shapes="_x0000_i1038">

4.

Присвоить <img src="/cache/referats/15033/image024.gif" v:shapes="_x0000_i1039">

5.

Присвоить <img src="/cache/referats/15033/image026.gif" v:shapes="_x0000_i1040">

6.

Если <img src="/cache/referats/15033/image028.gif" v:shapes="_x0000_i1041"><img src="/cache/referats/15033/image030.gif" v:shapes="_x0000_i1042">

Атеперь займёмся самым любимым занятием школьников всех времён и народов –решением квадратного уравнения:

Будемполагать, что коэффициенты этого уравнения <img src="/cache/referats/15033/image034.gif" v:shapes="_x0000_i1044"><img src="/cache/referats/15033/image036.gif" v:shapes="_x0000_i1045"> и <img src="/cache/referats/15033/image038.gif" v:shapes="_x0000_i1046"> представляют собойвещественные числа. Простейший случай предполагает, что все коэффициентыотличны от нуля. В зависимости от знака дискриминанта квадратного уравнения

возможны три случая:

1.

Если <img src="/cache/referats/15033/image042.gif" v:shapes="_x0000_i1048">

2.

Если <img src="/cache/referats/15033/image048.gif" v:shapes="_x0000_i1051">

3.

Если <img src="/cache/referats/15033/image052.gif" v:shapes="_x0000_i1053">

Блок схема алгоритмаприведена на рисунке:

Следует заметить, чтоприведённый алгоритм предназначен для решения узкого класса задач – квадратныхуравнений с «хорошими» коэффициентами. Если допустить, что коэффициенты могут приниматьпроизвольные вещественные значения, есть опасность, что при определённыхзначениях коэффициента (например, <img src="/cache/referats/15033/image055.gif" v:shapes="_x0000_i1054">

<img src="/cache/referats/15033/image056.gif" align=«right» hspace=«12» v:shapes="_x0000_s1116">Разработанный программистом алгоритмдолжен давать правильный ответ. Проверка алгоритма может оказаться непростым делом.В простых случаях такая проверка может быть выполнена с помощью заполнения трассировочной таблицы. Каждый столбецтакой таблицы соответствует определённой переменной, а каждая строка – одномушагу алгоритма. Для заполнения таблицы необходимо шаг за шагом проследить выполнениеалгоритма, записывая в таблицу текущие значения выбранных для трассировки переменных.Такой метод позволяет выявить логические ошибки, допущенные при составлении илизаписи алгоритма, и определить, верен ли окончательный ответ. Составим вкачестве примера трассировочную таблицу для алгоритма Герона вычисления квадратногокорня из числа 2.

i

z

1,00000

1,50000

1,41666

1,41421

Каквидно из таблицы, уже после третьей итерации приближенное значение квадратногокорня отличается от точного 1,414213 лишь в шестом знаке после запятой.

Заключение.

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

Список литературы.

1.

Коляда М. Г. Окно в удивительный мир информатики. –Д.: Сталкер, 1997.

2.

Немнюгин С. А. TurboPascal:практикум. – СПб: Питер, 2003.

3.

Попов В. Б. TurboPascalдля школьников: Учеб.пособие. – М.: Финансы и статистика, 2000.

4.

Турбо Паскаль 7.0. Самоучитель. – СПб.: Питер; К.:Издательская группа BHV, 2002.

еще рефераты

Еще работы по программированию, базе данных

Реферат по программированию, базе данных