Форум программистов, компьютерный форум CyberForum.ru

Вычислить глубину рекурсии и итеративного способа вычисления - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Сумма в строках двумерного массива http://www.cyberforum.ru/cpp-beginners/thread545726.html
Задача такая: в массив записываются данные о продажах за каждый месяц за три года. Нужно ввести эти данные с клавиатуры, сохраняя их в двумерном массиве (3*12) и вывести количество проданных (скажем книг - не важно чего) за каждый год. С клавиатуры ввод работает, а вот с подсчетом за год проблемы.. Подскажите, пожалуйста, что не так.. #include "stdafx.h" #include <iostream> using namespace...
C++ Как преобразовать строку цифр в число? Как преобразовать строку цифр в число? http://www.cyberforum.ru/cpp-beginners/thread545706.html
Операции над целыми множествами. C++
Должно быть: ввод, вывод, копирование, сложение множеств (+), пересечение множеств (*), разность (-), добавление в множество, проверка вхождения в множество. (Элементы хранятся в отсортированном порядке; поиск - двоичный) Может быть кто-нибудь делал?
Помогите сделать программу C++
помогите пожалуйста придумать программку на с++ по теме "оптимизация циклов"
C++ Не компилируется: что не так с конструктором структуры? http://www.cyberforum.ru/cpp-beginners/thread545676.html
Есть некий класс - односвязный линейный список, с элементами типа TElem. Шаблонность здесь только чтобы хранить различные объекты в списке и собственно эта же шаблонность и приводит к ошибке при компиляции. template <class T> CSparseArray { CSparseArray() :size(0) { m_First= NULL;
C++ Определить двухмерную матрицу целочисленных элементов int максимальным размером 20*20 1.Определить двухмерную матрицу целочисленных элементов int максимальным размером 20*20. 2.В диалоге запросить размер обрабатываемой матрицы или завершение работы программы. 3.Ввести матрицу запрошенного размера с клавиатуры. 4 Задание. Запросить строку и в ней отсортировать элементы по возрастанию, методом пузырьковой сортировки. (или 4. запросить правая/левая диагональ вверх вниз по... подробнее

Показать сообщение отдельно
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
12.04.2012, 11:20     Вычислить глубину рекурсии и итеративного способа вычисления
Цитата Сообщение от zitxbit Посмотреть сообщение
Общий смысл рекурентной формулы выше понятен. Только непонятно одно: для чего необходимо вычислять остаток от деления переменной n на 2 (n div 2)??
чтобы вычислить глубину рекурсии, нужно определить длину пути по наибольшей «ветви» рекурсивных вызовов. А наибольший путь, очевидно, будет при вызове a(n div 2). И да, нигде остаток от деления вычислять не надо: div — это целочисленное деление, а не вычисление остатка.

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

C
1
2
3
4
5
6
void rec1(size_t n)
{
   if(n == 0)
     return;
   rec1(n - 1);
}
C
1
2
3
4
5
6
7
8
9
void rec2(size_t n)
{
   size_t i;
 
   if(n == 0)
     return;
   for(i = 0; i < 100500; ++i)
     rec2(n - 1);
}
Глубина рекурсии у них одинаковая, но число рекурсивных вызовов у второй функции несоизмеримо больше.

Цитата Сообщение от zitxbit Посмотреть сообщение
Для линейной рекурсии глубина равна g_depth, для бинарной - pow(g_depth,2)
Опять неправильно. Для бинарной рекурсии в данном случае зависимость глубины в явном виде от числа n рекурсивных вызовов будет выражаться следующей формулой (можно доказать по индукции):

http://www.cyberforum.ru/cgi-bin/latex.cgi?\log_2 (n + 1)

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

Но вся загвоздка в том, что вышеприведенное выражение работает только для бинарной рекурсии, у которой длина обоих рекурсивных ветвей одинакова. Но не в нашем случае, когда длина ветви a(n div 2) больше ветви a(n div 3).

Выполнение рекурсивной функции можно представить в виде дерева, в котором каждое поддерево представляет рекурсивный вызов. Высота этого дерева и будет представлять глубину рекурсии, число же узлов — это число рекурсивных вызовов. Рассмотрим пример, в котором по исходной рекуррентной формуле вычисляется a(8) (каждое левое поддерево будет представлять вызов a(n div 2), каждое правое — a(n div 3)):
Вычислить глубину рекурсии и итеративного способа вычисления
 
Текущее время: 05:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru