68598

Программирование рекурсивных алгоритмов

Лабораторная работа

Информатика, кибернетика и программирование

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

Русский

2014-09-23

38.5 KB

8 чел.

Лабораторная работа №6

Тема: Программирование рекурсивных алгоритмов

Цель занятия:

  •  Совершенствование навыков разработки программ в среде программирования MS Visual C++
  •  Совершенствование навыков описания и использования функций в программах
  •  Получение начальных навыков в использовании рекурсий

Время на выполнение работы: 2 часа

Учебные вопросы:

  1.  Рекурсивные определения и алгоритмы
  2.  Программирование рекурсий

Подготовка к выполнению работы:

  1.  Изучить рекомендованную литературу (базовые конструкции структурного программирования, массивы и указатели, функции).
  2.  Изучить материал настоящего руководства.

Материалы для подготовки к занятию:

  1.  Конспект лекций.
  2.  [1] стр. 73-82.


ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

  1.  Рекурсивные определения и алгоритмы

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

Классическим примером рекурсивной функции является вычисление факториала числа. Для того чтобы получить значение факториала числа n, требуется умножить на n факториал числа (n-1). Известно также, что 0!=1 и 1!=1.

Рассмотрим реализацию рекурсивной функции для вычисления факториала числа:

long fakt (long n)

{

if (n==0 || n==1) return 1;

return (n*fakt(n-1));

 }

То же самое можно записать  короче:

long fakt(long n)

{

return (n>1)?n*fakt(n-1):1;

 }

Рассмотрим реализацию этой же задачи без использования рекурсии:

Long fakt(int n)

{

long m=1;

for (int i=2;i<=n;i++)

 m*=i;

 return m;

}

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

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

  1.  Программирование рекурсий

Рассмотрим еще один пример функции, с которой мы уже знакомились на практическом занятии №7 – функция определения длины строки strlen(s). Учитывая, что элементы любого массива расположены друг за другом и любой строковый массив заканчивается символом окончания строки «\0», то можно рекурсивно вызывать функцию определения длины строкового массива (или строки):

int lengh(char *a)

    {

    static int n=0;

    n++; a++;

    return (*a!='\0')?lengh(a):n;

    }

Разберем работу этой рекурсивной функции.

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

int main(int argc, char* argv[])

{

char str[50]; int n=0;

cout<<"\Input the string: ";

cin>>str;

n=lengh(str);

cout<<endl<<n;

return 0;

}

ПРОГРАММА  РАБОТЫ

  1.  Реализовать программу вычисления факториала числа.
  2.  Реализовать программу вычисления длины строки.

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


 

А также другие работы, которые могут Вас заинтересовать

79274. Нормативно-методическое и правовое обеспечение системы управления персоналом 16.07 KB
  Нормативнометодическое обеспечение системы управления персоналом представляет собой обеспечение документами устанавливающими нормы управления правила и методы организации труда необходимыми для нормальной организации трудовых процессов ведения нормативного хозяйства системы управления. Нормативнометодические документы подразделяются на следующие группы: нормативносправочные определяют нормы времени управленческих действий задания на конкретный период времени инструкции вышестоящих организаций или органов власти;...
79275. Кадровая политика организации – основа формирования стратегии управления персоналом 20.81 KB
  Кадровая политика организации генеральное направление кадровой работы совокупность принципов методов форм организационного механизма по выработке целей и задач направленных на сохранение укрепление и развитие кадрового потенциала на создание квалифицированного и высокопроизводительного сплоченного коллектива способного своевременно реагировать на постоянно меняющиеся требования рынка с учетом стратегии развития организации. Назначение кадровой политики своевременно формулировать цели в соответствии со стратегией развития...
79276. Система стратегического управления персоналом организации 23.23 KB
  Система стратегического управления персоналом организации Кадровая политика предусматривает в первую очередь формирование стратегии управления персоналом организации. Цель стратегического управления персоналом обеспечить адекватное состоянию внешней и внутренней среды формирование человеческого капитала предприятия в расчете на долгосрочный период. Стратегическое управление персоналом направлено на решение следующих задач: 1 обеспечение организации необходимым трудовым потенциалом в соответствии со стратегией; 2 формирование внутренней...
79277. Стратегия управления персоналом организации и ее реализация 25.51 KB
  Стратегия управления персоналом организации и ее реализация Стратегическое управление это система менеджмента ориентирующаяся на человеческий капитал как основу компании гибко реагирующая на динамику изменений внешней среды проводящая своевременные изменения в организации позволяющие добиться конкурентных преимуществ через приближение своей деятельности к запросам покупателей что обеспечивает долгосрочное устойчивое развитие и достижение поставленных целей. Стратегическое управление персоналом это управление формированием...
79280. Маркетинг персонала 14.68 KB
  Маркетинг персонала это вид деятельности который направлен на выявление потребности в персонале а также удовлетворение этих потребностей то есть покрытие потребности организации в персонале. С одной стороны маркетинг персонала можно рассматривать как философию организации и стратегию управления человеческими ресурсами компании а с другой стороны маркетинг персонала это одна из функций кадровой службы организации. Однако маркетинг персонала подходит к вопросу определения и покрытия потребности в персонале с точки зрения рыночного...
79281. Планирование и прогнозирование потребности в персонале 13.31 KB
  Планирование потребностей в персонале как и любой хороший план базируется на предпосылках которые позволяют делать предположения относительно будущего. Если Вы разрабатываете планы потребностей в персонале Вам скорее всего понадобятся три вида прогнозов: один для разработки Ваших требований к персоналу другой для поиска кандидатов со стороны и третий для поиска кандидатов внутри организации. Прогнозирование потребности в персонале строится на основе анализа прогнозов спроса и предложения для определения перспективной нехватки или...
79282. Планирование производительности труда и показателей по труду 14.55 KB
  Производительность труда это плодотворность продуктивность производственной деятельности людей. Планирование производительности труда определение уровня производительности труда и темпов ее роста обеспечивающих конкурентоспособность организации. На уровень и динамику производительности труда влияет множество факторов.