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

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

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

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

12.04.2012, 01:54. Просмотров 3563. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.04.2012, 01:54     Вычислить глубину рекурсии и итеративного способа вычисления
Посмотрите здесь:

Как увеличить глубину рекурсии - 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";
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,446
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++
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.
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,446
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)):
Вычислить глубину рекурсии и итеративного способа вычисления
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.04.2012, 19:49     Вычислить глубину рекурсии и итеративного способа вычисления
Еще ссылки по теме:

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

задача в 3 способа (циклы for, while и do while) - C++
Напишите программу, которая выводит таблицу квадратов первых десяти целых положительных чисел.

Вывести на консоль массив в три способа - C++
Напишите пожалуйста код, если не сложно. В долгу не останусь) Очень нужна помощь, скоро сдавать. Задача: Разработать программу,...

Выбор перегруженного метода в зависимости от способа вызова - C++
Столкнулся со странным поведением компилятора. При попытке вызвать оператор напрямую - выводит в виде числа. #include &lt;iostream&gt; ...

Архаичный сбор отчетов, поиск способа и языка - C++
Здравствуйте. Прошу у вас консультативной помощи. Есть задача: Создать форму для ввода однотипных данных. После заполнения...

Выбор подходящего способа хранения\обработки данных - C++
Здравствуйте! Передо мной встала задача выбора структуры данных, позволяющего хранить сортированные данные (в идеале позволяющая...


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

Или воспользуйтесь поиском по форуму:
diaryofsummer
1 / 1 / 0
Регистрация: 19.02.2012
Сообщений: 31
13.04.2012, 19:49  [ТС]     Вычислить глубину рекурсии и итеративного способа вычисления #6
Спасибо большое!)
Yandex
Объявления
13.04.2012, 19:49     Вычислить глубину рекурсии и итеративного способа вычисления
Ответ Создать тему
Опции темы

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