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

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

Войти
Регистрация
Восстановить пароль
 
CMson
2 / 2 / 2
Регистрация: 31.01.2013
Сообщений: 96
#1

Посчитать число рекурсий - C++

16.06.2014, 23:27. Просмотров 217. Ответов 0
Метки нет (Все метки)

Доброго времени суток.
Возникла такая проблема: Необходимо считать глубину рекурсии для quicksort. И, если, это число превышает log(n)(то есть наилучший случай), то сортировать массив heapsort-ом.
Сомневаюсь, что данный код правильно выполняет эту задачу.
Подскажите, правильно ли она работает? Если нет, то помогите исправить.
Спасибо.

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
double log(double a, double b)
{
    return log(a) / log(b);
}
 
void heapsort(int array[], int n)
{
    int i, t;
    Heapify(array, n);
    for (i = n - 1; i>0; i--)
    {
        t = array[0];
        array[0] = array[i];
        array[i] = t;
        adjust(array, i);
    }
}
 
void Heapify(int array[], int n)
{
    int item, i, j, k;
    for (k = 1; k < n; k++)
    {
        item = array[k];
        i = k;
        j = (i - 1) / 2;
        while ((i>0) && (item>array[j]))
        {
            array[i] = array[j];
            i = j;
            j = (i - 1) / 2;
        }
        array[i] = item;
    }
}
 
void adjust(int array[], int n)
{
    int item, i, j;
    j = 0;
    item = array[j];
    i = 2 * j + 1;
    while (i <= n - 1)
    {
        if (i + 1 <= n - 1)
        if (array[i] < array[i + 1])
            i++;
        if (item < array[i])
        {
            array[j] = array[i];
            j = i;
            i = 2 * j + 1;
        }
        else
            break;
    }
    array[j] = item;
}
 
void QuickSort(int* q, int low, int high, double depth, double _depth, int n)
{
    int A = low;
    int B = high;
    int mid;
 
    if (high > low)
    {
        mid = q[(high + low)/2]; 
        cout << mid << endl;
        while (A <= B)
        {
            while ((A < high) && (q[A] < mid))
                ++A;
            while ((B > low) && (q[B] > mid))
                --B;
            if (A <= B)
            {
                int temp;
                temp = q[A];
                q[A] = q[B];
                q[B] = temp;
                ++A;
                --B;
            }
        }
        if (low < B)
            _depth = log(B, 2);
        if (_depth > depth)
        {
            heapsort(q, n);
            cout << "HeapSort" << endl;
        }
        else
        {
            QuickSort(q, low, B, depth, _depth, n);
        }
        if (A < high)
            _depth = log(A, 2);
        if (_depth > depth)
        {
            heapsort(q, n);
            cout << "HeapSort" << endl;
        }
        else
        {
            QuickSort(q, A, high, depth, _depth, n);
        }
    }
}
 
int main()
{
    setlocale(LC_ALL, "Rus");
    int  i, q[10000];
    int n = 0;
    double depth, _depth;
 
    cout << "N" << endl;
    cin >> n;
 
    depth = log(n, 2);
    _depth = 0;
 
    for (i = 0; i <= n; i++)
    {
        q[i] = rand() % 100000;
        cout << "Massiv:" << q[i] << " " << endl;
    }
 
    QuickSort(q, 0, n - 1, depth, _depth, n);
    
    for (i = 0; i < n; i = i++)
    {
        cout << q[i] << " ";
    }
    system("pause");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.06.2014, 23:27     Посчитать число рекурсий
Посмотрите здесь:

Программирование рекурсий - C++
Функция Аккермана. Даны неотрицательные целые числа n, m. Вычислить A(n,m), где (см рисунок) Использовать программу, включающую...

Программирование рекурсий. - C++
Здравствуйте) помогте кто знает? Задание.Числа Фибоначчи u0, u1, u2, … определяются следующим образом: u0=0, u1=1, un= un-1+ un-2(n=2,...

Программирование рекурсий. Преобразование числа в двоичное - C++
Дано целое неотрицательное число n. Преобразовать его в двоичное число.

Программирование рекурсий. Преобразование числа в двоичное - C++
Дано целое неотрицательное число n. Преобразовать его в двоичное число.

Посчитать число N Фиббоначи - C++
Здравствуйте, есть задача: нужно посчитать число N Фиббоначи по модулю 10^9+7(ограничение до 10^18),вот код, по идее всё должно работать...

Посчитать число имени - C++
Чтобы определить число имени нужно воспользоваться особой таблицей, в которой каждая буква имеет свое числовое обозначение: 1 2 3 4...

Даны натуральное число n и вещественное число x. Посчитать значение выражения cosx+cosx^2+.cosx^n - C++
Даны натуральное число n и вещественное число x. Посчитать значение выражения cosx+cosx^2+...cosx^n. Помогите пожалуйста решить данное...

Программирование рекурсий: отделить цифры данного числа и сложить межу собой - C++
Дано целое неотрицательное число n. Отделить цифры данного числа и сложить межу собой.

Посчитать число сравнений в QuickSort - C++
приветствую всех любителей и профессионалов по С++. Изучаю Quicksort Мне нужно чтобы программа посчитала число сравнений сделанное при...

Дано натуральное число n. Посчитать S=1+1/2+1/3...+1/n - C++
Дано натуральное число n. Посчитать S=1+1/2+1/3...+1/n.

Дано натуральное число, посчитать последовательность и т.д. - C++
Вобщем нужна помощь, не знаю как решить задачки, точнее подзабыл, если кто поможет хоть 1, буду признателен. 1-Дано натуральное число...

Как посчитать число меньше единицы? - C++
Здравствуйте! Возникла небольшая проблемам, а именно, при написании кода, где нужно целое число делить на тысячу, выдает ошибку...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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