Рейтинг:
2
Jochen Arndt
В массивах C/C++ используются нулевые индексы. В результате допустимые индексы для непустых массивов составляют от 0 до размера минус единица. Но вы используете циклы, которые работают до и включая размер. Это может привести к перемещению неопределенных значений в ваши векторы.
Так что вы должны использовать
for(int k = 0; k < input1.size(); k++) {
вместо этого и аналогично для другого цикла.
Поскольку вы собираетесь поменять местами значения, проверяя один элемент за его пределами, вы
мочь необходимо уменьшить количество петель на единицу. Вы также должны повторно инициализировать индексы следующих элементов в циклах вместо их повторного использования:
for(int k = 0; k < input1.size() - 1; k++) {
// Start at next item
int j = k + 1;
while (input1[k] > input1[j]) {
// Swap here using j instead of j+1
}
}
Я также не уверен, что приращение
inv
внутри всех петель находится то, что вы хотите.
[РЕДАКТИРОВАТЬ]
Если вы хотите вычислить инверсию вектора, я предлагаю создать функцию только для этого без сортировки:
int GetInversion(const vector<int>& v)
{
int inv = 0;
for (int i = 0; i < v.size() - 1; i++)
for (int j = i + 1; j < v.size(); j++)
if (v[i] > v[j])
inv++;
return inv;
}
[/РЕДАКТИРОВАТЬ]
Member 13575891
почему для(int k = 0; k < input1.size() - 1; k++) это ??
почему я иду в n-1? Хотя я удалил равенство, но мой ответ тот же.
Мне интересно, что мой ответ изменился, когда я заменил j+1 на j, используя int j = k + 1;
Я понятия не имею, как это происходит. Он должен дать тот же самый ответ, но я получаю другой.
Сначала я получал 123503 а теперь 912619
Jochen Arndt
В вашем коде j инициализируется нулем, а затем только увеличивается. В результате j может уже достичь размера массива, в то время как необходимо выполнить еще несколько циклов. Поэтому он должен быть инициализирован в цикле для каждого запуска.
Поскольку нижние индексы уже отсортированы, j не должен быть установлен в ноль, но может быть установлен в текущий счетчик циклов k. Но вы хотите сравнить со следующим пунктом. Таким образом, он может быть установлен на k+1. Но также необходимо убедиться, что вы не получили доступ к элементу за пределами размера массива (k+1 < size). Это можно сделать, уменьшив количество циклов на единицу, как упоминалось в моем решении.
Member 13575891
Приращение inv даст мне счет инверсии, верно?
Jochen Arndt
В общем, да. Но обычно он учитывается для одного массива / вектора, а не для нескольких.
Вы также подсчитываете и сортируете в пределах одного цикла. В результате вы, вероятно, получите неверный результат.
Я обновлю свой ответ.
Member 13575891
как вы будете суммировать общие инверсии, когда массив сначала делится на два и сортируется рекурсивно, а затем снова объединяется, чтобы получить окончательный сортированный массив?
таким образом, вычисляются три функции: f1(сортировка) + f2(сортировка) + f3(слияние)
Jochen Arndt
Я не могу ответить на этот вопрос, потому что не знаю, что (и почему) вы делаете таким образом. Инверсия вычисляется для одного массива и будет равна нулю после сортировки. Если все, что вам нужно, - это общее значение, просто получите подсчеты для каждого массива перед сортировкой и суммируйте их.
Member 13575891
Это то, что ты хотел сказать? поправьте меня пожалуйста
#include<iostream>
#включить<вектор>
#включить<fstream>
использование пространства имен std;
пустота GetInversion(вектор и Л;int&ГТ;&амп; В1, вектор и Л;int&ГТ;&амп; В2, вектор и Л;int&ГТ;&амп; в инт&амп; инв) {
for (int i = 0; i < v1.size() - 1; i++)
for (int j = i + 1; j < v1.size(); j++)
if (v1[i] > v1[j])
инверсия++;
GetInversion2(вектор и Л;int> В версии v1, вектор и Л;int&ГТ;&амп; В2, вектор и Л;int&ГТ;&амп; в инт инв);
};
пустота GetInversion2(вектор и Л;int&ГТ;&амп; В1, вектор и Л;int&ГТ;&амп; В2, вектор и Л;int&ГТ;&амп; в инт&амп; inv2) {
for (int i = 0; i < v2.size() - 1; i++)
for (int j = i + 1; j < v2.size(); j++)
если (v2[i] > v2[j])
inv2++;
for(int o=0; o<V. size()/2; o++) {
если(v[o] > v[o]) {
inv2++;
}
}
cout << "Total inversions are" << inv2;
};
тап_п(недействительными) {
int count=0;
вектор<int> большой;
вектор<int> один;
вектор<int> Два;
ifstream inFile;
входной_файл.открытые("w2.txt");
если (!inFile) {
cout << "невозможно открыть файл datafile.txt";
}
int значение;
пока(входной_файл &ГТ;&ГТ; ценим) {
big.push_back(значение);
}
for(int i=0; i<big.size()/2; i++) {
один.push_back(большой[я]);
}
для(Int J в=большой.размер()/2; к&ЛТ;большой.размер(); J++в) {
два.push_back(большой[Дж]);
}
GetInversion(один, два, большой, граф);
}
Jochen Arndt
Нет, просто вызовите GetInversion() для каждого массива перед его сортировкой:
int invBig = GetInversion(big);
int invOne = GetInversion(one);
int invTwo = GetInversion(two);
// Sort now
Member 13575891
Я обновил вопрос, если он сделает вас более ясным.
Дело в том, что массив big не предназначен для сортировки, а объединяется из двух массивов, то есть один и два путем сравнения.
Jochen Arndt
"Задача состоит в том, чтобы вычислить количество инверсий в данном файле, где i-я строка файла указывает на I-ю запись массива."
Так почему же вы создаете два массива, сортируете их и объединяете?
Member 13575891
чтобы заставить его работать во времени nlogn в соответствии с сортировкой слияния.
большой массив считывается из файла, а остальные два перерыва большого.
сортировка двух разрывов рекурсивно, а затем сохранение их в новом массиве, для сравнения, дает мне полные инверсии.
Jochen Arndt
Я не думаю, что ваша полная инверсия будет такой же, как для инциального (большого) массива. Особенно при выполнении сортировки (что делает всю операцию намного медленнее).
Member 13575891
проверьте мое новое обновленное неправильное решение в вопросе.
Member 13575891
и положить j = k+1 не получится. В этом нет никакого смысла.
Jochen Arndt
В этом есть смысл. Взгляните на мою функцию GetInversion (), которая работает аналогично. Если вы поищете в интернете, то найдете похожий - если не идентичный - код.
Я думаю, что остановлюсь здесь, потому что я и другие показали вам некоторые основные ошибки в вашем коде. Если вы собираетесь решить проблему более сложным способом по мере необходимости, я желаю Вам удачи.
Рейтинг:
0
OriginalGriff
Мы не знаем, с какими проблемами вы сталкиваетесь, но, глядя на это, первое, что приходит на ум, - это:
for(int k=0; k<=input1.size(); k++) {
while (input1[k] > input1[j+1]) {
Поскольку индексы начинаются с нуля, если у вас есть
n
предметы в
input1
, вы получите доступ к элементам в индексах
0, 1, 2, ... n - 1, n
Таким образом, если у вас есть три элемента, ваши индексы будут:
k = 0
k = 1
k = 2
k = 3
Что явно неправильно.
Member 13575891
Я тебя понял. Это неправильно. но это не поможет, если я удалю равенство в цикле. Я все еще получаю тот же самый ответ.
Но я думаю, что это даст мне ошибку сегментации? не так ли?