Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
egorikftp
0 / 0 / 0
Регистрация: 02.12.2014
Сообщений: 22
1

Как привязать Шаблон к main() для поиска k-ой статистики

23.03.2015, 23:06. Просмотров 286. Ответов 3
Метки нет (Все метки)

//дан массив mas длины n. Найти k-ую по величине порядковую статистику

//основная идея - использовать алгоритм быстрой сортировки
//сложность алгоритма: O(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
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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
template < class T>
 
int main()
{
    int n;
    cout << "Введите размерность: "; cin >> n;
    int *mas = new int[n];
    for (int i = 0; i < n; i++)
        cin >> mas[i];
 
    int k; cout << "Введите k-ый эл-т: "; cin >> k;
 
    system("pause");
    return 0;
}
 
template <class T>
T order_statistics(vector<T> a, unsigned n, unsigned k)
{
    unsigned l, r;
    using std::swap;
    for (l = 1, r = n;;)
    {
 
        if (r <= l + 1)
        {
            // текущая часть состоит из 1 или 2 элементов -
            //   легко можем найти ответ
            if (r == l + 1 && a[r] < a[l])
                swap(a[l], a[r]);
            return a[k];
        }
 
        // упорядочиваем a[l], a[l+1], a[r]
        unsigned mid = (l + r) >> 1;
        swap(a[mid], a[l + 1]);
        if (a[l] > a[r])
            swap(a[l], a[r]);
        if (a[l + 1] > a[r])
            swap(a[l + 1], a[r]);
        if (a[l] > a[l + 1])
            swap(a[l], a[l + 1]);
 
        // выполняем разделение
        // барьером является a[l+1], т.е. медиана среди a[l], a[l+1], a[r]
        unsigned
            i = l + 1,
            j = r;
        const T
            cur = a[l + 1];
        for (;;)
        {
            while (a[++i] < cur);
            while (a[--j] > cur);
            if (i > j)
                break;
            swap(a[i], a[j]);
        }
 
        // вставляем барьер
        a[l + 1] = a[j];
        a[j] = cur;
 
        // продолжаем работать в той части,
        //   которая должна содержать искомый элемент
        if (j >= k)
            r = j - 1;
        if (j <= k)
            l = i;
 
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.03.2015, 23:06
Ответы с готовыми решениями:

Шаблон поиска максимального элемента для многомерного массива
Вечер добрый, помогите разобраться с шаблонами в с++ Нужно найти максимальных...

Написать шаблон функции для поиска среднего арифметического массива
Написать шаблон функции для поиска среднего арифметического значений массива

Шаблон функции для поиска произведения всех элементов одномерного массива
Есть задание: /* Создать функцию-шаблон. Используя эту функцию,...

Написать шаблон функции для поиска среднего арифметического значений массива
Кто знает как решить задачу на С++, при помощи шаблонов функций? Написать...

Написать шаблон функции для поиска среднего арифметического значений массива
#include &lt;iostream&gt; #include &lt;windows.h&gt; using namespace std; template...

3
zss
Модератор
Эксперт С++
7360 / 6769 / 4281
Регистрация: 18.12.2011
Сообщений: 17,882
Завершенные тесты: 1
24.03.2015, 07:01 2
Цитата Сообщение от egorikftp Посмотреть сообщение
template < class T>
int main()
main не может быть шаблоном!
0
egorikftp
0 / 0 / 0
Регистрация: 02.12.2014
Сообщений: 22
24.03.2015, 09:44  [ТС] 3
Тогда как красиво привязать этот шаблон к main()?
0
zss
Модератор
Эксперт С++
7360 / 6769 / 4281
Регистрация: 18.12.2011
Сообщений: 17,882
Завершенные тесты: 1
24.03.2015, 11:22 4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class T>
T order_statistics(vector<T> a, unsigned n, unsigned k); 
 
int main()
{
    int n;
    cout << "Введите размерность: "; 
    cin >> n;
    vector<int> mas(n);
    for (int i = 0; i < n; i++)
        cin >> mas[i];
    int k; cout << "Введите k: "; cin >> k;
    int res=order_statistics(mas, n, k);
    cout<<res; 
    system("pause");
    return 0;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.03.2015, 11:22

Создал шаблон vs но выдаёт ошибку при включении main.cpp
Как решить проблему?

Как написать модульный тест для функции main
имеется функция нахождения максимального из трех целых чисел int main() {...

Шаблон поиска элементов по заданному значению
не находит индекс задаваемого элемента из списка. мне подсказывали убрать node...


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

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

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