Void bezu(int d, int m, int n, int bm, int bn)
{
int pm,pn;
pm = m * bm;
pn = n * bn;
//проверка базы рекурсии (выполнение линейной комбинации)
if (d == pm - pn)
printf ("%d = %d*%d - %d*%d", d, bm, m, bn, n); //d=bm*m-bn*n
//декомпозиция
Else
{
bn++;
pn=n*bn;
/*если произведение pm больше, чем pn, то порядок параметров сохраняется*/
if (pm > pn)
bezu(d, m, n, bm, bn);
/*если произведение pm меньше, чем pn, то порядок параметров изменятся*/
Else
Bezu(d, n, m, bn, bm);
}
}
Определить ресурсную сложность алгоритма!
Пример 4 . Задача о Ханойских башнях
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны n колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из n колец за наименьшее число ходов с одного стержня на другой. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
Существует древнеиндийская легенда, согласно которой в городе Бенаресе под куполом главного храма, в том месте, где находится центр Земли, на бронзовой площадке стоят три алмазных стержня. В день сотворения мира на один из этих стержней было надето 64 кольца. Бог поручил жрецам перенести кольца с одного стержня на другой, используя третий в качестве вспомогательного. Жрецы обязаны соблюдать условия:
1. переносить за один раз только одно кольцо;
2. кольцо можно класть только на кольцо большего размера или на пустой стержень.
|
|
|
Согласно легенде, когда, соблюдая все условия, жрецы перенесут все 64 кольца, наступит конец света. Для 64 колец это 18 446 744 073 709 551 615 перекладываний, и, если учесть скорость одно перекладывание в секунду, получится около 584 542 046 091 лет, то есть апокалипсис наступит нескоро.
На рисунке ( рис. 3.2) изображена ситуация, иллюстрирующая перекладывание 7 колец со стержня А на В через вспомогательный С.
Рис. 3.2. Ситуация при переносе семи колец
Кольцо со стержня А можно перенести на стержень В или С, кольцо со стержня В можно перенести на стержень С, однако, нельзя перенести его на стержень А.
Задача состоит в том, чтобы определить последовательность минимальной длины переноса колец. Решением задачи будем считать последовательность допустимых переносов, каждый из которых имеет вид: A->B, A->C, B->A, B->C, C->A, C->B. Если кольцо всего одно, то задача решается за один перенос A->В. Для перемещения двух колец требуется выполнить три действия: A->C, A->В, C->B. Решение задачи для трех колец содержит семь действий, для четырех – 15.
Напишем рекурсивную функцию, которая находит решение для произвольного числа колец.
Параметризация. Функция имеет четыре параметра, первый параметр – число переносимых колец, второй параметр – стержень, на который первоначально нанизаны кольца. Третий параметр функции – стержень, на который требуется перенести кольца, и, наконец, четвертый параметр – стержень, который разрешено использовать в качестве вспомогательного.
|
|
|
База рекурсии. Перенос одного стержня.
Декомпозиция. Последовательность переноса колец изображена на рисунке ( рис. 3.3).
Рис. 3.3. Схема решения задачи о Ханойских башнях для четырех колец
Чтобы перенести n колец со стержня A на стержень B, используя стержень C в качестве вспомогательного, можно поступить следующим образом:
· перенести n –1 кольцо со стержня A на C, используя стержень B в качестве вспомогательного стержня;
· перенести последнее кольцо со стержня A на стержень B ;
· перенести n –1 кольцо со стержня C на B, используя стержень A в качестве вспомогательного стержня.
При переносе n –1 кольца можно воспользоваться тем же алгоритмом, т.к. на нижнее кольцо с самым большим диаметром можно просто не обращать внимания. Перенос одного кольца в программе выражается в том, что выводится соответствующий ход.
#include <iostream> #include <stdio.h> using namespace std;//Объявление функции перемещения колец с A на C через Bint hanoj(int n, char A, char B, char C); int main() { char x='A',y='B',z='C'; O(1)+O(1)+O(1)=3O(1)=o(1) int k,h; cout<<"\nВведите количество колец: "; cin>> k; h=hanoj(k,x,z,y);//O(n)*O(1)=O(n) cout<<"\nКоличество перекладываний = " <<h; } //Описание функции перемещения колец с A на C через B 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; }
|
|
|
Задания к Пз4.
Используя теоретические материалы лекции 1 и Пз1-Пз3 разработать любые пользовательские алгоритмы для указанных задач, составить программы, определить и обосновать порядок сложности разработанных программ. Проанализировать зависимость роста сложности разработанных программ от объема входных данных. Эффективность собственных алгоритмов и программ приветствуется, но не является основной целью.
Каждое задание необходимо решить в соответствии с изученными рекурсивными методами решения задач и методами обработки числовых данных в языке С++. Перед реализацией кода каждой задачи необходимо разработать рекурсивную триаду в соответствии с постановкой задачи. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, используя рекурсивные функции. Этапы сопроводить комментариями в коде
|
|
|
Цель. Изучить понятия рекурсии, рекурсивные функции в программировании, приемы построения рекурсивной триады при решении задач, научиться применять рекурсивные методы в решении задач на языке С++. Приобрести навыки и умения анализа алгоритма и всего кода разработанной программы в Big-O-нотации.
Указания
Каждое задание необходимо решить в соответствии с изученными рекурсивными методами решения задач и методами обработки числовых данных в языке С++. Перед реализацией кода каждой задачи необходимо разработать рекурсивную триаду в соответствии с постановкой задачи. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, используя рекурсивные функции. Этапы сопроводить комментариями в коде
Задача 1.
Дата добавления: 2021-05-18; просмотров: 157; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!