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

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

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

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

16.06.2014, 23:27. Просмотров 221. Ответов 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");
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.06.2014, 23:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Посчитать число рекурсий (C++):

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.06.2014, 23:27
Привет! Вот еще темы с ответами:

Даны натуральное число 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.


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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