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

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

Войти
Регистрация
Восстановить пароль
 
fuzzytoozy
8 / 8 / 1
Регистрация: 23.11.2012
Сообщений: 94
#1

Рекурсия - C++

19.10.2013, 14:49. Просмотров 550. Ответов 5
Метки нет (Все метки)

Есть такой код. В нем рисуется что то вроде линейки. Данный код предназначен для иллюстрации работы рекурсии. Может мне кто нибудь объяснить. Вот при первом вызове subdivide палочка ставится посередине, значение середины 32. Далее палочки ставятся на 32, 16 и 48, ок. Но что происходит потом я не могу понять. Происходит вызов subdivide с level 3, она ставит палочку на 32 и вызывает subdivide с level 2, которая, в свою очередь ставит палочку на 16 и вызывает subdivide с level 1, которая ставит палочку на значении 8. Но как в этом рекурсивном цикле палочка оказывается на значении 24 я не понимаю. Откуда она его берёт!?!? Объясните пожалуйста, всю голову сломал уже....

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
36
37
38
39
// ruler.cpp -- using recursion to subdivide a ruler
#include <iostream>
const int Len = 66;
const int Divs = 6;
void subdivide(char ar[], int low, int high, int level);
int main()
{
    char ruler[Len];
    int i;
    for (i = 1; i < Len - 2; i++)
        ruler[i] = ' ';
    ruler[Len - 1] = '\0';
    int max = Len - 2;
    int min = 0;
    ruler[min] = ruler[max] = '|';
    std::cout << ruler << std::endl;
    for (i = 1; i <= Divs; i++)
    {
        subdivide(ruler,min,max, i);
        std::cout << ruler << std::endl;
        for (int j = 1; j < Len - 2; j++)
            ruler[j] = ' ';  // reset to blank ruler
    }
    // std::cin.get();
    std::system("PAUSE");
    return 0;
}
 
void subdivide(char ar[], int low, int high, int level)
{
    if (level == 0)
        return;
    int mid = (high + low) / 2;
    ar[mid] = '|';
    std::cout << "Recursion at level: " << level << std::endl
    << "Mid = " << mid << std::endl;
    subdivide(ar, low, mid, level - 1);
    subdivide(ar, mid, high, level - 1);
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.10.2013, 14:49
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия (C++):

Рекурсия - C++
Здравствуйте, писали на лабораторной программу с использованием рекурсии, о бъясните почему в ответе двойки выдает?? и что рекурсивная...

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

рекурсия на с - C++
разработать рекурсивную функцию для вычитания двух подлинных двоичных чисел, заданных в виде символьных строк. разрядность цифр может быть...

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

Рекурсия - C++
Привет, помогите пожалуйста надо вычислить рекурсивную функцию : (x+a(x+(a-1)(x+(a-2)(x+...2(x+1)^2)^2)^2)^2)^2. Помогите пожалуйста ,...

Рекурсия - C++
Задан массив целых чисел: а0, а1 ..., аn-1. Известно, что один из элементов массива принимает нулевое значение. Найти номер данного...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
dzrkot
zzzZZZ...
519 / 349 / 53
Регистрация: 11.09.2013
Сообщений: 1,998
19.10.2013, 16:50 #2
знакомая програмка из Стивена Прата))

C++
1
2
3
 
subdivide(ar, low, mid, level - 1);
subdivide(ar, mid, high, level - 1)
обрати внимание функция 1ый раз вызывается для low mid, 2ой, для mid high

low=0, high = LEN-2=64,
1) mid = 0 + 64 / 2 = 32
2) mid+high=32+64=96
mid=96/2=48
0
fuzzytoozy
8 / 8 / 1
Регистрация: 23.11.2012
Сообщений: 94
19.10.2013, 18:53  [ТС] #3
Да, из него родимого. Нет, это я понял. Меня интересует именно то, каким образом функция получает значение 24 в переменную mid. Потому что это значение должно получаться именно при вызове первой функции с mid в качестве high.
Ну вот например: level = 3, значит при вызове первой функции level-1 = 2. Получаем что mid = 16 так? то бишь 32/2. Потом вызывается эта же функция с level -1, level = 1. Получается mid = 16/2 = 8, так?. Далее функция опять вызовет сама себя но натолкнется на проверку условия level == 0 и выполнит оператор return. Что происходит дальше? откуда программа берет значение 24 в переменную mid?

Добавлено через 1 час 35 минут
в общем я вставлял в код принтф и заметил такую штуку. В определенный момент, при вызове функции, значение low в ней становится 16 а high = 32, они складываются, делятся на 2 и получается 24. НО КАК!?!? Ведь при вызове функции один параметр high или low всегда константый.... либо low = 0 и high переменная, либо high = 64 а low переменная. Как они обе поменяли значение!?!?!
0
dzrkot
zzzZZZ...
519 / 349 / 53
Регистрация: 11.09.2013
Сообщений: 1,998
19.10.2013, 20:39 #4
Цитата Сообщение от fuzzytoozy Посмотреть сообщение
Да, из него родимого. Нет, это я понял. Меня интересует именно то, каким образом функция получает значение 24 в переменную mid. Потому что это значение должно получаться именно при вызове первой функции с mid в качестве high.
Ну вот например: level = 3, значит при вызове первой функции level-1 = 2. Получаем что mid = 16 так? то бишь 32/2. Потом вызывается эта же функция с level -1, level = 1. Получается mid = 16/2 = 8, так?. Далее функция опять вызовет сама себя но натолкнется на проверку условия level == 0 и выполнит оператор return. Что происходит дальше? откуда программа берет значение 24 в переменную mid?

Добавлено через 1 час 35 минут
в общем я вставлял в код принтф и заметил такую штуку. В определенный момент, при вызове функции, значение low в ней становится 16 а high = 32, они складываются, делятся на 2 и получается 24. НО КАК!?!? Ведь при вызове функции один параметр high или low всегда константый.... либо low = 0 и high переменная, либо high = 64 а low переменная. Как они обе поменяли значение!?!?!
долго пытался понять то, что тебе не понять...

low и high не меняются, меняется только mid. Мы при вызове функции, просто от середины меняем границы функции, в одном случае вместо low ставим mid, в другом вместо high. Ты функцию вызываешь первый раз, subdivide(ar, low(0), high(64), level - 1);
потом она вызывает сама себя с разными значениями:
subdivide(ar, low(0), mid(32), level - 1);
subdivide(ar, mid(32), high(64), level - 1);
дальше mid снова меняется, и для каждой функции из этих 2ух он будет свой, т.е. в 1ом случае (0+32)/2=16, в другом (32+64)/2=48, потом каждая из функций вызывает другие две себя, дргумими значениями mid

я не понимаю что непонятно...)
0
zss
Модератор
Эксперт С++
6382 / 5947 / 1927
Регистрация: 18.12.2011
Сообщений: 15,264
Завершенные тесты: 1
19.10.2013, 21:04 #5
Легче будет понять в отладчике.
Поставьте останов на строку 32.
И далее выполняйте код построчно с заходом в функции
(в VS - клавиша F11). При этом следите за переменной mid.
0
fuzzytoozy
8 / 8 / 1
Регистрация: 23.11.2012
Сообщений: 94
19.10.2013, 21:32  [ТС] #6
Цитата Сообщение от dzrkot Посмотреть сообщение
долго пытался понять то, что тебе не понять...

low и high не меняются, меняется только mid. Мы при вызове функции, просто от середины меняем границы функции, в одном случае вместо low ставим mid, в другом вместо high. Ты функцию вызываешь первый раз, subdivide(ar, low(0), high(64), level - 1);
потом она вызывает сама себя с разными значениями:
subdivide(ar, low(0), mid(32), level - 1);
subdivide(ar, mid(32), high(64), level - 1);
дальше mid снова меняется, и для каждой функции из этих 2ух он будет свой, т.е. в 1ом случае (0+32)/2=16, в другом (32+64)/2=48, потом каждая из функций вызывает другие две себя, дргумими значениями mid

я не понимаю что непонятно...)
Ты просто не понимаешь что я спрашиваю. Я понимаю что меняется значение только mid и оно передается как high или low. Суть вопроса не в том КАК это происходит. А каким образом получается число 24 в mid. Ты проследи цикл и попробуй мне объясни это. там получается так что в функции которой ПЕРЕДАЛИ MID в качестве параметра low = 16, а high = 32. Я и спрашиваю каким образом получаются такие значения, если у первого вызова функции low всегда = 0 и в качества параметра high передается mid, а у второго high всегда = 64 и в качестве параметра low. Тогда получается что одновременно могут изменяться только либо high либо low в одной функции, другое значение всегда остается постоянным 0 или 64, тогда каким образом они приняли вид 16 и 32....я не понимаю

Добавлено через 11 минут
Цитата Сообщение от zss Посмотреть сообщение
Легче будет понять в отладчике.
Поставьте останов на строку 32.
И далее выполняйте код построчно с заходом в функции
(в VS - клавиша F11). При этом следите за переменной mid.
я знаю в каком месте она меняется таким образом, я просто не понимаю почему и как именно таким образом. Откуда берется значение 24
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.10.2013, 21:32
Привет! Вот еще темы с ответами:

рекурсия - C++
Сделать рекурсию, кроме факториала!

Рекурсия - C++
Вопрос не по коду. Вот есть у меня рекурсивная функция, глубина рекурсии достигает 10 в среднем. Эта функция вызывается огромное (порядка...

Рекурсия - C++
Есть задача, написал решение но ответ неправильный. Задача: Решение: #include &lt;iostream&gt; using namespace std; int a, n, m, t,...

рекурсия - C++
Доброго времени суток. Уважаемые ГУРУ, есть одна проблема. Ниже представлен код, в котором параметр b должен быть всегда...


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

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

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