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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.81
diaryofsummer
1 / 1 / 0
Регистрация: 19.02.2012
Сообщений: 31
#1

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

12.04.2012, 01:54. Просмотров 3607. Ответов 5
Метки нет (Все метки)

помогите пожалуйста вычислить глубину рекурсии и итеративного способа вычисления

программа вычисляет элементы последовательности:
a(0)=1;
a(n)=a(n div 2)+a(n div 3), n>1;

для итеративного способа, я так понял, глубина равна n,
а как ее вычислить для рекурсии?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "stdafx.h"
#include <conio.h>
#include <iostream>
using namespace std;
 
int formula(int n)
{
    if (n<0)              
    {
        cout<<"error";
        getch();
        exit(1);        
    } 
    if (n==0) return 1;  
    return formula(n/2)+formula(n/3);    
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    int n;
    int i;
    cout<<"n = ";
    cin>>n;
    cout<<"recursivno: result = "<<formula(n)<<"\n";         
           
// здесь начинается итеративный способ 
    int *results = new int[n+1];                       
    results[0] = 1; 
    for (int i=1; i<n+1; i++) 
        results[i]=results[i/2]+results[i/3]; 
    cout <<"iterativno: result = "<<results[n]<<endl;   
    delete [] results;
           getch();
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.04.2012, 01:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вычислить глубину рекурсии и итеративного способа вычисления (C++):

Как увеличить глубину рекурсии - C++
почему глубина рекурсии в С++ ограничена (43281) можно ли снять это ограничение написал код который устанавливает максимальную глубину ...

Как узнать глубину рекурсии? - C++
Подскажите пожалуйста как узнать глубину рекурсии? Нужно узнать глубину рекурсии может кто помочь? #include&lt;math.h&gt; ...

Рекурсии(Вычислить значения по формуле) - C++
1-x2/2!+x4/4!-x6/6!+..+(-1n)*x2n+1/(2n+1)! функция контроля cos x помогите пожалуйста хотя бы понять как делать, что то я совсем...

Вычислить значение выражения с помощью рекурсии - C++
Ребята помогите написать рекурсивную функцию для этого выражения p=a0+x(a1+x(a2+x(a3+...+x(an))))

Вычислить произведение сомножителей с применением рекурсии и без нее - C++
Помогите написать прогу.Рекурсию не понимаю,да и задание не очень понятно,посоветуйте где лучше написано. Вот...

Вычислить сумму N элементов методом восходящей и нисходящей рекурсии - C++
необходимо вычислить сумму N элементов (целые числа например с 1 до 10) методом восходящей и нисходящей рекурсии.

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
zitxbit
Master C/C++
88 / 740 / 75
Регистрация: 11.04.2012
Сообщений: 971
12.04.2012, 04:57 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long g_depth = 0;
int formula(int n)
{
    if (n<0)              
    {
        cout<<"error";
        getch();
        exit(1);        
    } 
    if (n==0) return 1;
    g_depth++;
    return formula(n/2)+formula(n/3);    
}
..........
cout<<"recursivno: result = "<<formula(n)<<"\n";         
cout<<"glubina recursii: depth = "<<g_depth<<"\n";
0
Nameless One
Эксперт С++
5773 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
12.04.2012, 05:31 #3
zitxbit, у тебя подсчитывается не глубина рекурсии, а число рекурсивных вызовов.

Для данной формулы глубину рекурсии можно посчитать так:

http://www.cyberforum.ru/cgi-bin/latex.cgi?\operatorname{depth} (n) = \begin{cases}1, \qquad n = 0 \\ <br />
1 + \operatorname{depth}(n \, \operatorname{div} \, 2), \qquad n > 0<br />
\end{cases}

для итеративного способа, я так понял, глубина равна n
у итеративного способа нет такого понятия, как «глубина». Может, имелось в виду что-нибудь другое?
0
zitxbit
Master C/C++
88 / 740 / 75
Регистрация: 11.04.2012
Сообщений: 971
12.04.2012, 10:27 #4
Общий смысл рекурентной формулы выше понятен. Только непонятно одно: для чего необходимо
вычислять остаток от деления переменной n на 2 (n div 2)??

Вообще, давайте разберемся что такое глубина рекурсии. Напомним, что "рекурсия" - это вызов
некоторой функции formula при выполнении ее же самой. Таким образом, каждый следующий (!)
вызов функции formula инициируется в процессе текущего выполнения функции formula. В нашем
случае при каждом вызове функции formula, переменная g_depth увеличивается на единицу. И так,
до бесконечности, или до тех пор пока не выполнится определенное условие (напр. if (n==0) return 1. После этого происходит завершение выполнения всех экземпляров функции formula в порядке обратном их вызову. С логической точки зрения чем больше количество рекурентных вызовов, тем больше глубина
рекурсии. Для линейной рекурсии глубина равна g_depth, для бинарной - pow(g_depth,2), для косвенной -
2 * g_depth.
0
Nameless One
Эксперт С++
5773 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
12.04.2012, 11:20 #5
Цитата Сообщение от 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)):
Вычислить глубину рекурсии и итеративного способа вычисления
0
diaryofsummer
1 / 1 / 0
Регистрация: 19.02.2012
Сообщений: 31
13.04.2012, 19:49  [ТС] #6
Спасибо большое!)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.04.2012, 19:49
Привет! Вот еще темы с ответами:

Нужно вычислить произведение всех элементов массива с помощью рекурсии. - C++
Доброго времени суток! Нужно вычислить произведение всех элементов массива с помощью рекурсии. Подскажите как это можно сделать?

Ограничить глубину рекурсии - C#
Доброго времени суток! Помогите ограничить глубину рекурсии.. Есть код: public static TreeNode...

Назначить глубину рекурсии при поиске определённого файла - CMD/BAT
И опять двадцать пять. Пример тут где-то был, но найти не могу. При поиске определенного файла надо прошерстить 1-2 уровня вниз и найти...

Для графа дерева найти длину пути от вершины U до V (использовать поиск в глубину и счётчик глубины рекурсии WG) - Pascal
помоги, пожалуйста, нужна программа:wall: Для графа дерева найти длину пути от вершины U до V (использовать поиск в глубину и счётчик...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.04.2012, 19:49
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru