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

Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Найти сумму ряда http://www.cyberforum.ru/cpp-beginners/thread1210081.html
Здравствуйте уважаемые форумчане! Нуждаюсь в помощи. Имеется ряд http://firepic.org/images/2014-06/16/4mby1f0q9sec.png Необходимо найти его сумму. Visual C++, консольное приложение. Желательно с комментариями, чтобы разобраться :) Заранее огромное спасибо за помощь!
C++ Алгоритм Фибоначчи Пользователь вводит любые два числа и количество операций, программа должна два числа сложить и результат записать в конец, после сложить два последних числа и так же записать в конец, и так определённое количество раз, которое задавалось в начале и равное количеству операций. Решить рекурсивным методом. Например, если пользователь вводит 4, 7 и 5, то на выводе должно получится: 4 7 11 18 29... http://www.cyberforum.ru/cpp-beginners/thread1210048.html
Блок-схемы C++
Кто может нарисовать 7 блок-схем, не сложные по видимому, но надо поскорее кто сечет отпишите плиз
C++ Набор инструментов для инди с мультиплеером по ip
Подскажите какие библиотеки подключать для создания игр в стиле контры, марио, battle toads... Только с поддержкой качественной графики и возможностью игры с аппонентами через локальную сеть, интернет. Имеется Visual Studio 2012 ULT
C++ Сохранение результатов в текстовый документ http://www.cyberforum.ru/cpp-beginners/thread1210039.html
Добрый день. Нужна помощь, в данный код нужно добавить возможность сохранения результатов в текстовый документ. #include <iostream> using namespace std; int main() { double x, y, o; string c; char z; printf("Vvedite 1 chislo:");
C++ Библиотеки glut.lib и glut32.lib не могу найти Здравствуйте товарищи, помогите с очередной дилеммой. На днях начал изучать программирование, скачал Dav C++, но для дальнейших уроков нужны библиотеки - glut.h , glut32.blut , glut.bll , glut32.lib. Некоторые скачал, но к примеру glut.lib и glut32.lib не могу найти. Помогите ссылкой пожалуйста подробнее

Показать сообщение отдельно
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
17.06.2014, 13:14     Какую сортировку массива применить, чтобы посчитать количество перестановок двух соседних элементов?
вот попробуй пошли вот это!
я там ее еще дебагал поэтому дофига комментов!
я не уверен что правильно, но просто интересно проверить!


UPD::
да это верно! я на другом сайте послал - полное решение!))

C++ (Qt)
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <vector>
 
using namespace std;
 
const int dxh[] = {-2, -2, 2, 2, -1, -1, 1, 1};
const int dyh[] = {-1, 1, -1, 1, -2, 2, -2, 2};
 
long long int inv = 0;
int a[555555], b[555555];
int n;
 
void merge(int l, int r)
{
    //cout << "ranges == " << l << ' ' << r << endl;
    int sz = r - l + 1;
    if(sz == 1)
        return;
    if(sz == 2)
    {
        if(a[l] > a[r])
        {
            int t = a[l];
            a[l] = a[r];
            a[r] = t;
            inv++;
        }
 
        return;
    }
 
    int mid = sz / 2;
    
    //vector<int> b, c;
 
    merge(l, l + mid - 1);
    merge(l + mid, r);
 
    //for(int i = mid; i < a.size(); i++)
        //c.push_back(a[i]);
 
    //vector<int> a1 = merge(b);
    //vector<int> a2 = merge(c);
 
    //int n = l + mid - 1 - l + 1;
    //int m = r - (l + mid) + 1;
 
    //vector<int> s;
 
    /*cout << "first vector == " << endl;
    for(int i = 0; i < n; i++)
        cout << a1[i] << ' ';
    cout << endl;
 
    cout << "second vector == " << endl;
    for(int i = 0; i < m; i++)
        cout << a2[i] << ' ';
    cout << endl;*/
 
    //int sz1 = (n - 1) - l + 1;
    int n = l + mid;
    int m = r + 1;
    /*int sz1 = (n - 1) - l + 1;
 
    cout << "befor sliv == " << endl;
    for(int i = l; i < n; i++)
        cout << a[i] << ' ';
    cout << endl;
    for(int i = l + mid; i < m; i++)
        cout << a[i] << ' ';
    cout << endl;*/
    int i = l, j = l + mid;
    //cout << "segments == " << i << ' ' << n - 1 << ' ' << j << ' ' << m - 1 << endl;
 
    int id = 0;
    long long cur = 0;
 
    while(i < n || j < m)
    {
        //cout << i << ' ' << j << endl;
        if(i < n)
        {
            if(j >= m || a[i] <= a[j])
            {
                b[id] = a[i];
                id++;
                //s.push_back(a[i]);
                i++;
            }
            else
            {
                b[id] = a[j];
                id++;
                //s.push_back(a[j]);
                j++;
                inv += (n - 1) - i + 1;
                cur += (n - 1) - i + 1;
                
            }
        }
        else
        {
            b[id] = a[j];
            id++;
            //s.push_back(a[j]);
            j++;
        }
    }
 
    int idx = 0;
    for(int i = l; i <= r; i++)
        a[i] = b[idx], idx++;
 
    /*cout << "after sliv == " << endl;
    for(int i = l; i <= r; i++)
        cout << a[i] << ' ';
    cout << endl;
    cout << "cur == " << cur << endl;*/
 
    //return s;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    int val = 1000000;
    for(int i = 0; i < n; i++)
    {
        int ch;
        scanf("%d", &ch);
        //ch = val;
        val--;
        a[i] = ch;
    }
 
    /*cout << "begin" << endl;
    for(int i = 0; i < n; i++)
        printf("%d ", a[i]);
    cout << endl;*/
    //vector<int> res = merge(mas);
    merge(0, n - 1);
 
    /*cout << "res == " << endl;
    for(int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");*/
    printf("%lld\n", inv);
    return 0;
}
 
Текущее время: 16:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru