Алгоритм. Эффективность алгоритма. Рекурсивные алгоритмы

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

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.

Содержание

Введение…………………………………………………………………4
1. Алгоритм и алгоритмизация………………………………………...5
1.1. Основные свойства алгоритмов…………………………………11
1.2. Эффективность алгоритма………………………………………13
2. Рекурсия………………………………………………………………14
3. Практическая часть…………………………………………………...16
Заключение………………………………………………………………24
Список литературы……………………………………………………...25

Введение

Темой курсовой работы является «Алгоритмы, эффективность алгоритма, рекурсивные алгоритмы», но прежде чем приступить непосредственно к самому повествованию по данной теме, с приведением примеров, я бы хотел рассмотреть само понятие алгоритм, его происхождение и другие виды алгоритмов.
Так что же такое алгоритм? Это понятие весьма многозначно и имеет множество определений, но всегда обозначает примерно следующее:
Алгоритм - это точное предписание исполнителю совершить определенную последовательность действий для достижения поставленной цели за конечное число шагов.
Термин «Алгоритм» был известен еще в глубокой древности, считается что его ввел арабский мыслитель и математик Аль Хорезми. В современном мире он получил наиболее широкое распространение благодаря бурному развитию вычислительных технологий. Сегодня трудно представить мир без персональных компьютеров и сотовых телефонов, а ведь в основы их работы заложен какой-то алгоритм. Да и вся жизнь человека, каждодневные действия, которые мы совершаем, мы исполняем по какому-либо алгоритму. Вспомните ваш обычный распорядок дня – утром вы просыпаетесь и идете чистить зубы и умываться, потом позавтракали, оделись, и на работу ... вечером вы приходите с работы – ужинаете, и выполняете еще какие либо действия (смотрите телевизор, помогаете детям с домашним заданием, выгуливаете собаку), принимаете душ и ложитесь спать.

1. Алгоритмы и алгоритмизация

Процессор электронно-вычислительной машины, это чудо техники, умеет, тем не менее, выполнять лишь простейшие команды. Каким же образом компьютер решает сложнейшие задачи обработки информации? Для решения этих задач программист должен составить подробное описание последовательности действий, которые необходимо выполнить центральному процессору компьютера. Составление такого пошагового описания процесса решения задачи называется алгоритмизацией, а алгоритмом называется конечный набор правил, расположенных в определенном логическом порядке, позволяющий исполнителю решать любую конкретную задачу из некоторого класса однотипных задач. В разных ситуациях в роли исполнителя может выступать электронное или какое-либо иное устройство или человек (например, военнослужащий, охраняющий склад боеприпасов и действующий согласно алгоритмам, записанным в устав караульной службы).
Само слово «алгоритм» возникло из названия латинского перевода книги арабского математика IX века Аль-Хорезми «Algoritmi de numero Indorum», что можно перевести как «Трактат Аль-Хорезми об арифметическом искусстве индусов». Составление алгоритмов и вопросы их существования являются предметом серьезных математических исследований. Здесь мы познакомимся только с основными понятиями и фактами, касающимися алгоритмизации.
Алгоритм должен удовлетворять определенным требованиям. Принято выделять следующие семь:
1. Наличие ввода исходных данных.
2. Наличие вывода результата выполнения.
3. Однозначность (компьютер «понимает» только однозначные инструкции).
4. Общность — алгоритм предназначен для решения некоторого класса задач.
5. Корректность — алгоритм должен давать правильное решение задачи.
6. Конечность — решение задачи должно быть получено за конечное число шагов.
7. Эффективность — для решения задачи должны использоваться ограниченные ресурсы компьютера (процессорное время, объем оперативной памяти и т. д.).
Если речь идет о составлении алгоритмов для процессора ЭВМ (электронно-вычислительной машины), исполнителем является процессор. Упрощенная модель процессора содержит устройство считывания данных, стек (специальную оперативную память небольшого объема, предназначенную для временного хранения данных) и арифметическое устройство, которое может выполнять арифметические действия.
Предположим, что программа, составленная для такого процессора, содержит
числовые данные и символы арифметических действий над этими данными.
Вот пример такой программы, предназначенной для вычисления суммы двух
чисел 2 и 3:
2, 3, +
Проследим выполнение этой программы. Первая операция — считывание в стек значения 2. Затем в стек считывается второе значение (3), Первоё значёние при этом сдвигается во вторую ячейку памяти. Третий шаг выполнения программы — вычисление суммы двух считанных значений (они называются операндами). Результат этой операции — значение 5 — записывается в первую ячейку стека.
Мы рассмотрели пример простейшей программы. Она является записью алгоритма решения некоторого класса задач — задач вычисления суммы двух чисел. Обозначим эти числа а и Ь. Тогда алгоритм можно записать следующим образом:
1. Считать число а.
2. Считать число Ь.
3. Выполнить суммирование с := а + Ь.
4. Вывести число с.
Это пример записи алгоритма на естественном языке, то есть на языке Человеческого общения. Мы видим, что формулировка алгоритма не зависит от конкретных значений переменных а и Ь, поэтому его можно применять для решения достаточно большого числа сходных задач, вместе составляющих целый класс задач суммирования. Алгоритм описывает действия не над конкретными значениями, а над абстрактными объектами.
Основными объектами программирования являются переменные. Переменные в программе отличаются от переменных, используемых в записи математических формул. Несмотря на сходство терминов, правила использования переменных в программах для компьютера отличаются от правил работы с математическими переменными. Это различие необходимо уяснить. В программировании переменную можно трактовать как одну или несколько ячеек оперативной памяти компьютера, которым присвоено определенное имя. Содержимое этих ячеек может меняться, но имя переменной остается неизменным. В математике значение переменной в рамках определенной задачи неизменно, но меняется в других задачах из данного класса. Именно поэтому конструкция
а := а + 1
воспринимается программистом совершенно естественно, а уравнение
а = а + 1
математик сочтет неверным. В первом случае имеется в виду вычисление суммы содержимого ячейки а и числовой константы 1 и занесение полученного результата в ту же ячейку а. Второй случай равносилен неверному тождеству 0=1.
Составим алгоритм решения следующей задачи. Пусть заданы два значения, х и у. Необходимо сравнить эти значения и напечатать имя большей переменной. Для решения этой задачи достаточно сравнить оба значения и в зависимости от результата сравнения вывести на печать символ «х» или символ «у»:
1. Ввести значение х.
2. Ввести значение у.
3. Если х < у, то напечатать «у», иначе напечатать «х». В этом алгоритме используются алгоритмические структуры — линейная последовательность операций и ветвление (шаг 3, условный оператор). Последняя структура называется так потому, что после передачи в нее управления выполнение алгоритма может пойти по одной из двух возможных ветвей. То, какая ветвь будет выбрана, зависит от выполнения условия. Линейная последовательность в данном примере состоит из блоков ввода/вывода данных. Рассмотрим еще один пример составления алгоритма. Пусть необходимо вычислить целую степень числа х" для произвольных значений степени и основания, используя только операцию умножения. Проблема здесь заключается в том, что конкретное значение степени заранее неизвестно, следовательно, неизвестно и необходимое количество умножений. Чтобы решить эту проблему, введем в алгоритм вспомогательную переменную — счетчик числа выполненных умножений, а степень будем вычислять по рекуррентной формуле: Z0 = 1, Zn = Zn-1 × X. Запись алгоритма вычисления произвольной целочисленной степени числа приводится ниже: 1. Ввести значения х и п 2. Переменной z присвоить начальное значение 1. 3. Вспомогательной переменной i присвоить начальное значение 0. 4. Переменной z присвоить результат выполнения операции z × x. 5. Переменной z присвоить значение Г + 1. 6. Если z < n, то перейти к шагу 4, иначе остановить работу программы. Этот алгоритм содержит ввод данных (шаг 1), блок вычислений (шаги 2, 3), ветвление (шаг 6), а также еще одну алгоритмическую структуру — цикл (шаги 4, 5 и 6). Цикл представляет собой многократно повторяющуюся последовательность операторов и играет в программировании важнейшую роль. Кроме уже перечисленных структур иногда выделяют еще одну — обход, который представляет собой передачу управления с пропуском нескольких шагов алгоритма. Для записи алгоритмов мы пользовались естественным языком. Иногда используют полуформальный язык с ограниченным словарем (часто на основе английского языка), промежуточный между естественным языком и языком программирования. Такой язык называется псевдокодом. Запись алгоритма на псевдокоде называется структурным планом. Псевдокод удобен тем, что позволяет программисту сосредоточиться на формулировке алгоритма, не задумываясь над синтаксическими особенностями конкретного языка программирования. Для разработки структуры программы удобнее пользоваться записью алгоритма в виде блок-схемы (в англоязычной литературе используется термин flowchart). Для изображения основных алгоритмических структур и блоков на блок-схемах используют специальные графические символы. Они приведены на рис. 1.1. Составим алгоритм вычисления квадратного корня из произвольного положительного вещественного числа х методом Герона и запишем его на естественном языке, а также в виде блок-схемы. Напомню (см. Учебник, урок 1), что метод основан на многократном применении формулы , при z0 = 1. Числовая последовательность zn в пределе при п → ∞ сходится к искомому значению. Мы, разумеется, не сможем устремить нашу последовательность к бесконечности, поэтому примем самое простое (но не самое верное!) решение — выполним только 5 итераций метода, считая, что при этом будет достигнута достаточно хорошая точность. Обычно десяти итераций метода Герона более чем достаточно для достижения хорошей точности расчета. На рис. 1.2 приводятся оба варианта записи алгоритма 1. Ввести х. 2. Присвоитьz= 1. 3. Присвоить i = 0. 4. Присвоить z = (z + х / z) / 2. 5. Присвоить i = i+1. 6. Если i < 6, то перейти к шагу 4, иначе напечатать значение z. Рис1.2. Алгоритм вычисления квадратного корня методом Герона: слева блок-схема, справа – запись алгоритма на естественном языке. 1.1. Основные свойства алгоритмов 1. Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма. 2. Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов). 3. Определенность — каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче. 4. Результативность (иди конечность) состоит в том, что за конечное число шагов алгоритм либо должен приводить к решению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов. 5. Массовость означает, что алгоритм решения задачи разрабатывается в общем виде, т.е, он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма. Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление называется блок-схемой. Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. В псевдокоде не приняты строгие синтаксические правила для записи команд, однако в нем имеются некоторые конструкции, присущие формальным языкам(школьный АЯ). На практике исполнителем алгоритмов являются компьютеры. Поэтому язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера. 1.2. Эффективность алгоритмов В наше время бурно развивается отрасль программирования, все больше предприятий хотят выйти из «ХХ века» и оснастить свои заводы современной информационно-вычислительной техникой с эффективными программами. Существует множество путей написаний одной и той же программы, но предприятия заинтересованы в использовании программ, которые превосходят по своим характеристикам, а именно: 1. Простота в написании. 2. Компактность. 3. Минимальное время работы программы. Первые два пункта связаны между собой, так как простота программы ведет к увеличении компактности. Время работы программы измеряется с помощью дополнительных программ или с использованием секундомера. Но так как большинство программ работают доли секунд, то создаются проблемы в измерении. Программисты нашли выход из этой ситуации: создается цикл, и программа работает определенное количество раз, затем полученное значение времени делят на число раз сколько работала программа, в результате мы получаем временной показатель работы программы. 2. Рекурсия Не так давно человечество вступило в новый XXI век – век информации и компьютеров. Благодаря бурному развитию научных, технических и технологических исследований стало возможным хранить огромные объёмы данных и преобразовывать их со скоростями, которые ещё несколько десятилетий назад могли только сниться. При создании сложных информационных систем перед проектировщиками стали нетривиальные задачи, требующие разработки новых концепций программирования. Для решения проблем такого рода, особенно при учёте человеческого фактора, возникает необходимость обеспечения понятности алгоритма, так называемой «читабельности» исходного кода программы, и как следствие модифицируемости и относительной лёгкости сопровождения конечного программного продукта. Часто этого можно достигнуть включением в реализацию приложения рекурсивных подпрограмм, механизмы использования которых предоставляются практически всеми современными компиляторами и средами разработки. Объект называется рекурсивным, если для своего определения или функционирования он прямо или косвенно обращается к объекту в некотором смысле такого же типа. Так, например, в теле рекурсивных подпрограмм, которые будут подробно рассмотрены ниже, в простейшем случае содержится вызов самих себя, но с другими параметрами. Рекурсия является одним из наиболее мощных и, наверно, самым общим методом научного познания. Она эффективно применяется во многих прикладных и теоретических естественнонаучных дисциплинах, и стала неотъемлемой их частью. Этому нетрудно найти множество подтверждений, однако один и тот же по сути метод, применительно к различным областям носит различные названия, такие как индукция, рекурсия или рекуррентные соотношения. Различия касаются особенностей использования. Под индукцией понимается метод доказательства утверждений с формулировкой зависящей от натурального переменного , который строится на базе индукции (правильности утверждения при или ), затем утверждение полагается правильным при и проводится доказательство для . Термин рекуррентное соотношение связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии. Важную роль в теории алгоритмов сыграл аппарат рекурсивных функций, разработанный Алонзо Чёрчем и позволивший ему формализовать понятие алгоритма. Последние двадцать лет получили бурное развитие созданная и глубоко развитая Бенуа Мандельбротом фрактальная геометрия, теория мультифракталов и их приложения. Нужно заметить, что в теориях понятие рекурсии одно из основных. Так, например, многие фрактальные геометрические фигуры, такие как совершенное канторово множество или салфетка Серпинского, определяются рекурсивно. Как видим, понятие рекурсии очень широко и многогранно. В настоящей работе будет освещён лишь один аспект этого понятия, а именно рекурсивные алгоритмы. Они рассмотрены как с позиций теории алгоритмов и теории сложности, так и с точки зрения практического программирования. Читатель сможет узнать, как применять на практике алгоритмы, содержащие рекурсию, а главное когда стоит это делать. Важно сохранять баланс между изящностью и простотой восприятия, присущие рекурсивным алгоритмам, и сложностью его реализации на конкретной вычислительной системе. 3. Практическая часть. Задание 1. При некоторых заданных х, /V, и Е определяемых вводом. вычислите сумму N слагаемых заданного вида, а также сумму тех слагаемых, которые по абсолютной величине больше Е. Для второго случая выполните суммирование для двух значений Е, отличающихся на порядок, и при этом определите количество слагаемых, включенных в сумму. Сравните результаты с точным значением функции, для которой данная сумма определяет приближенное значение при х, лежащем в интервале (-R;R). Построить график изменения суммы предложенного ряда (N>=20).

Программа:
program zadacha1;
var x,e,sn, se,see,no,stoch :real;
a, n,i,k,numb:integer;
begin
for a:=1 to 6 do begin
writeln('vvedite x,n,e');
readln(x,n,e);
sn:=x;
se:=x;
no:=x;
for i:= 1 to (n-1) do begin
no:= -(no*x*x*(2*i-1))/((2*i)*(2*i+1));
sn:=sn+no; ////Schitaet summu
end;
k:=2;
no:=x;
repeat ////summa teh slagaemih kotorie po abs. velichine >e
no:= -(no*x*x*(2*k-1))/((2*k)*(2*k+1));
se:=se+no;
k:=k+1; ////schetchchiki dlia vicheslenia poriadkovogo nomera chlena
until (abs(no)) < e;////postuslovie numb:=0;////kol-vo elementov mezhdu E-mi see:=0; ////Summa chlenov mezhdu E-mi Otlich. na poriadok repeat k:=k+1; no:= -(no*x*x*(2*k-1))/((2*k)*(2*k+1)); see:=see+no;//// Summa see numb:=numb+1; ////Schetchik until (abs(no)) < (e/10); {abs. velichina chlena ne budet minshe E, na poriadok menshego E} stoch:=ln(x+sqrt(x*x+1)); {vichesliaem tochnoe znachenie} writeln('summa N slagaemih : ',sn:1:10); writeln('summa slagaemih>E : ',se:1:15);
writeln('summa otlichayushihsa na poryadok : ',see:1:15);
writeln('kol-vo slagaemix v summe na poryadok : ',numb);
writeln('tochnoe znachenie funkcii: ',stoch:1:10);
readln;
end;
end.
Программа просит ввести данные x, n, E.
Затем выводит посчитанные значения (Рисунок 2).

Рисунок 2
По этим значениям построим график изменения суммы ряда.

Алгоритм задачи №1

Задание 2. Составить программу, проверяющую правильность вычисления площади треугольника по заданным сторонам (ф-ла Герона). Обучаемому предлагается шесть задач. Обучаемому предлагается вопрос и три числа а, Ь, с. Решив задачу, он должен ввести ответ. Если ответ правильных, то предлагается следующий вопрос и сообщение «правильно». В противном случае обучаемому предлагается снова ответить на вопрос. Если повторный ответ также неправильный, то предложить вычислить сначала р=(а+Ь+с)/2, затем x1=р(р-а), x2=x1(р-Ь), х3=х2(р-с) и . После трех неудачных попыток ответить на вопрос, выдать обучаемому правильный ответ и предложить следующий. Подсчитать число правильных ответов с первой попытки.
Программа:
program zadacha2;
Var ©,k:integer;
a,b,c,p,S,x1,x2,x3,otvet,pp:real;
begin
k:=0;
For i:=1 to 6 do begin
writeln(‘Vvtdite storoni treugolnika’);
readln(a);
readln(b);
readln©;
if ((a+b)>c) and ((b+c)>a) and ((a+c)>b) then begin
p:=(a+b+c)/2;
x1:=p*(p-a);
x2:=x1*(p-b);
x3:=x2*(p-c);
s:=sqrt(x3);
writeln(‘Vvedite pravelniy otvet’);
readln(otvet);
if otvet=s then
begin
k:=k+1;
writeln (‘V Pravelno’);continue; end
else
writeln(‘Otvet ne verniy, poprobuyte esho raz’);
readln(otvet);
if otvet=s then writeln (‘V Pravelno’) else
Begin
writeln(‘Neverno’);
writeln(‘Poprobuyte vicheslit sperva P=(a+b+c)/2:’);
writeln(‘x1:=p(p-a):’);
writeln(‘x2:=x1(p-b):’);
writeln(‘x3:=x2(p-c):’);
writeln(‘s=sqrt(x3)’);
writeln(‘Otvet:’);
readln(otvet);
if otvet=s then writeln(‘Verno’) else writeln(‘Neverno, pravelniy otvet: ‘,S);
end;
end else writeln(‘Neverno vedeni storoni treugolnika!’); continue; end;
writeln(‘Kolichestvo vernih otvetov s pervoy popitki: ‘,k);
readln;
end.
Работа программы показана на рисунке 3.

Рисунок 3.

Алгоритм задачи № 2

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

Список используемой литературы

1. Нестеренко А. В. ЭВМ и профессия программиста.М., Просвещение, 1990.
2. Брудно А. Л., Каплан Л. И. Московские олимпиады по программированию. М., Наука, 1990.
3. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. М., Энергоатомиздат, 1988.
4. Гейн А.Г. и др.. Основы информатики и вычислительной техники. М., Просвещение, 1994.


Скачиваний: 1
Просмотров: 1
Скачать реферат Заказать реферат