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

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

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

программа вычисляет элементы последовательности:
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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 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";
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
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
у итеративного способа нет такого понятия, как «глубина». Может, имелось в виду что-нибудь другое?
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 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.
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
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)):
Вычислить глубину рекурсии и итеративного способа вычисления
diaryofsummer
1 / 1 / 0
Регистрация: 19.02.2012
Сообщений: 31
13.04.2012, 19:49  [ТС]     Вычислить глубину рекурсии и итеративного способа вычисления #6
Спасибо большое!)
Yandex
Объявления
13.04.2012, 19:49     Вычислить глубину рекурсии и итеративного способа вычисления
Ответ Создать тему
Опции темы

Текущее время: 09:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru