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

Сортировка слиянием. Количество инверсий - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Символьные функции: Преобразовать массив так: стаж работы увеличить на год, если он станет равен 10, то зарплату увеличить в 2 раза, если 15 – в 3 раз http://www.cyberforum.ru/cpp-beginners/thread864909.html
Задан массив. «Фамилия_стаж работы_зарплата». Преобразовать массив так: стаж работы увеличить на год, если он станет равен 10, то зарплату увеличить в 2 раза, если 15 – в 3 раза. Написала программу,...
C++ Не все ветви кода возвращают значение. Как исправить public double Method(double matrix, int n) { //1 int k = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n + 1; j++)... http://www.cyberforum.ru/cpp-beginners/thread864873.html
Программу переписать со структурой! C++
Программа выводит по вводимому номеру порядкового дня число и месяц. Этот код программы нужно переписать со структурой. Помогите, пожалуйста. Код программы: #include "stdafx.h" #include...
Создание класса: Линейные целочисленные массивы произвольного размера с сортировкой вставками C++
Дана задача: Создать Класс: Линейные целочисленные массивы произвольного размера с сортировкой вставками. Проблема: Люди..Не умею работать с Классами и не знаю как их создавать в С++...Вообще...
C++ Медианные фильтры http://www.cyberforum.ru/cpp-beginners/thread864861.html
Всем привет. Кто может объяснить по какому принципу действуют медианные фильтры? Например, вот для такой последовательности { x(i) } = и апертурой 4 какой будет результат?
C++ Массив ( Максимальный из Отрицательных элементов в числовом массиве) Помогите написать метод который будет искать Максимальный из Отрицательных элементов в числовом массиве Я попытался реализовать такой код int iMaxNegativ (0); for ( size_t i (0); i < m_n;... подробнее

Показать сообщение отдельно
Rostislav1
0 / 0 / 0
Регистрация: 04.05.2013
Сообщений: 7

Сортировка слиянием. Количество инверсий - C++

14.05.2013, 18:14. Просмотров 1844. Ответов 0
Метки (Все метки)

Нужно посчитать количество инверсий в последовательности. При больших значениях ~90 - 100 тысяч программа выдает непонятное отрицательно число. Где ошибка?
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
#include <stdio.h>
#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
int tmp = 0;
vector<int> mas;
int merge(vector<int> &mas, int l, int m, int r)
{
    int per = 0;
    vector<int> buffer(r - l + 1);
    int pos1 = l;
    int pos2 = m+1;
    int posB = 0;
 
    while(pos1 <=m && pos2<=r)
    {
        if(mas[pos1] < mas[pos2])
            buffer[posB++] = mas[pos1++];
        else
        {
            buffer[posB++] = mas[pos2++];
            per += m - pos1 + 1;
        }
    }
 
    while (pos1 <=m)
        buffer[posB++] = mas[pos1++];
    while (pos2 <=r)
        buffer[posB++] = mas[pos2++];
    copy(buffer.begin(), buffer.end(), mas.begin()+l);
    return per;
 
}
int merge_sort(vector<int> & mas, int l, int r)
{
    int per = 0;
    if(l == r)
        return per;
    int m = (l + r)/2;
    per +=merge_sort(mas, l,m);
    per +=merge_sort(mas, m+1,r);
    per += merge(mas, l, m, r);
    return per;
}
void input()
{
    cin>>n;
    mas.resize(n);
        for (int j=0;j<n;j++)
            scanf("%d",&mas[j]);
      int per= merge_sort(mas,0,n-1);     
            tmp = per;
}
void output()
{
    printf("%d\n", tmp);
}
int main()
{
    input();
    output();
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru