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

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

Войти
Регистрация
Восстановить пароль
 
egorikftp
0 / 0 / 0
Регистрация: 02.12.2014
Сообщений: 22
#1

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

23.03.2015, 23:06. Просмотров 269. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Как привязать Шаблон к main() для поиска k-ой статистики (C++):

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

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

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

Написать шаблон функции для поиска среднего арифметического значений массива - C++
#include &lt;iostream&gt; #include &lt;windows.h&gt; using namespace std; template &lt;typename T&gt; int arifm( T mas, int size) { int...

Как написать модульный тест для функции main - C++
имеется функция нахождения максимального из трех целых чисел int main() { int a, b, c, mx; printf (&quot;Insert numbers:\n&quot;); ...

Шаблон функции поиска максимального элемента - C++
Шаблон функции поиска максимального элемента массива задается след.образом: template &lt;typename T&gt; T max(T *x, int len) { T max=x; ...

3
zss
Модератор
Эксперт С++
6864 / 6426 / 2147
Регистрация: 18.12.2011
Сообщений: 16,885
Завершенные тесты: 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
Модератор
Эксперт С++
6864 / 6426 / 2147
Регистрация: 18.12.2011
Сообщений: 16,885
Завершенные тесты: 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
Привет! Вот еще темы с ответами:

Шаблон поиска элементов по заданному значению - C++
не находит индекс задаваемого элемента из списка. мне подсказывали убрать node *cur = head-&gt;next; из цикла, т.к. он определен в начале,...

Шаблоны функций, Ошибка: для использования класса шаблон требуется список аргументов шаблон - C++
Есть у меня 3 структуры Трамвай , Троллейбус , Автобус. Для автобуса определены функции (работают) Троллейбус и Трамвай одинаковые поля...

Как назначить другой шаблон для результатов поиска? - Joomla
Есть 2 шаблона: для главной и для остальных (внутренних) страниц. И есть поле поиска по сайту в шапке каждого шаблона. Необходимо чтобы...

Шаблон для main метода - JAVA IDE
Как быстро написать в Эклипсе public static void main ?


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

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

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