ИССЛЕДОВАНИЕ АЛГОРИТМОВ РЕКУРСИВНЫХ ФУНКЦИЙ В РЕШЕНИИ СПЕЦИАЛЬНЫХ ЗАДАЧ

I Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

ИССЛЕДОВАНИЕ АЛГОРИТМОВ РЕКУРСИВНЫХ ФУНКЦИЙ В РЕШЕНИИ СПЕЦИАЛЬНЫХ ЗАДАЧ

Корниенко Д.С. 1
1
Маркина В.А. 1
1
Автор работы награжден дипломом победителя II степени
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Содержание
  1. Введение 3

  2. Из истории 5

  3. Основная часть 6

  4. Заключение 10

  5. Список использованных источников 11

  6. Приложения

Введение

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

В связи с развитием информационных технологий, понятие рекурсивного алгоритма является не основным понятием теории алгоритмов, но одним из главных понятий современной науки. Более того, в XXI-ом веке, так называемый век информации, «алгоритм» является одним из важнейших факторов цивилизации.

Теория алгоритмов как самостоятельная наука появилась в 30-40х годах ХХ-века и имеет огромное значение во всех направлениях математических наук. Благодаря этой теории находят свои точные определения такие фундаментальные понятия алгоритм, доказуемость, сложность.

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

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

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

Цель исследования: возможности области применения в повседневной жизни.

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

Задачи проекта:

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

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

Методы исследования:

  • анализ информационных источников

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

Из истории

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

Одним из свойств алгоритма является конструктивность – объекты из X, над которыми работает алгоритм, должны быть конструктивными (конструктивный объект – это такой объект, который может быть набран весь целиком и представлен нам для рассмотрения).

В силу этого свойства алгоритма между объектами счетного множества X и множества натуральных чисел N можно установить взаимно однозначное соответствие и в дальнейшем вместо объекта х є Х рассматривать его номер или код объекта, являющийся натуральным числом.

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

Основная часть.

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

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

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

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

Рекурсивный алгоритм - это алгоритм, в определении которого содержится прямой или косвенный вызов этого же алгоритма.

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

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

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

Для решения задач рекурсивными методами разрабатывают следующие этапы, образующие рекурсивную триаду:

  • параметризация - выделяют параметры, которые используются дляописания условия задачи, а затем в решении;

  • база рекурсии - определяют тривиальный случай, при которомрешение очевидно, то есть не требуется обращение функции ксебе;

  • декомпозиция - выражают общий случай через более простыеподзадачи с измененными параметрами.

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

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

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

Пример 1. Для целого неотрицательного числа n найдите его факториал.

Разработаем рекурсивную триаду.

Параметризация: n- неотрицательное целое число. База рекурсии: для n=0 факториал равен 1. Декомпозиция: n!=(n-1)!*n.

long factor (int n)

{

if (n pn) bezu(d, m, n, bm, bn);

/*если произведение pm меньше, чем pn, то порядок

параметров изменятеся*/

else bezu(d, n, m, bn, bm); } }

Пример 4. Задача о Ханойских башнях

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

Существует древнеиндийская легенда, согласно которой в городе Бенаресе под куполом главного храма, в том месте, где находится центр Земли, на бронзовой площадке стоят три алмазных стержня. В день сотворения мира на один из этих стержней было надето 64 кольца. Бог поручил жрецам перенести кольца с одного стержня на другой, используя третий в качестве вспомогательного. Жрецы обязань соблюдать условия:

  1. переносить за один раз только одно кольцо;

  2. кольцо можно класть только на кольцо большего размера или напустой стержень.

Согласно легенде, когда, соблюдая все условия, жрецы перенесут все 64 кольца, наступит конец света. Для 64 колец это 18 446 744 073 709 551 615 перекладываний, и, если учесть скорость одно перекладывание в секунду, получится около 584 542 046 091 лет, то есть апокалипсис наступит нескоро.

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

Рис. 3.2. Ситуация при переносе семи колец

Кольцо со стержня А можно перенести на стержень В или С, кольцо со стержня В можно перенести на стержень С, однако, нельзя перенести его на стержень А.

Задача состоит в том, чтобы определить последовательность минимальной длины переноса колец. Решением задачи будем считать последовательность допустимых переносов, каждый из которых имеет вид: А—»В, А—ИЗ, В—*А, В—ИЗ, С—*А, С—*В. Если кольцо всего одно, то задача решается за один перенос А—*В. Для перемещения двух колец требуется выполнить три действия: А—из, А—»В, С—*В. Решение задачи для трех колец содержит семь действий, для четырех - 15.

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

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

База рекурсии. Перенос одного стержня.

Декомпозиция. Последовательность переноса колец изображена на рисунке (рис. 3.3).

Рис. 3.3. Схема решения задачи о Ханойских башнях для четырех колец

Чтобы перенести п колец со стержня А на стержень В, используя стрежень С в качестве вспомогательного, можно поступить следующим образом:

  • перенести п-1 кольцо со стержня А на С, используя стержень В вкачестве вспомогательного стержня;

  • перенести последнее кольцо со стержня А на стержень В;

  • перенести п-1 кольцо со стержня С на В, используя стержень А вкачестве вспомогательного стержня.

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

//Ханойские башни

#include "stdafx.h"

#include

using namespace std;

int hanoj(int n, char A, char B, char C);

//Объявление функции перемещения колец с А на С через В

int _tmain(int argc, _TCHAR* argv[ ] ){

char x='A',y='B',z='C';

int k,h;

printf("Задача о Ханойских башнях");

printf("пВведите количество колец: ");

scanf("%d",&k);

h=hanoj(k,x,z,y);

printf("пКоличество перекладываний равно %d",h);

system("pause");

return 0; }

//Описание функции перемещения колец с А на С через В int hanoj(int n, char A, char B, char C){ int num;

if (n == 1) {printf("n %c -> %c", A, C); num = 1;} else {

num=hanoj(n-1, A, C, B) ; printf("n %c -> %c", A, C); num++;

num+=hanoj(n-1, B, A, C);

}

return num;

}

18

Просмотров работы: 1110