Member 13575891 Ответов: 3

Счетная инверсия [получение неправильного ответа]


A file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated.

Task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.


Что я уже пробовал:

#include<iostream>
#include<vector>
#include<fstream>

using namespace std;

void sort(vector<int>& input1, vector<int>& input2, int& inv) {

int temp=0, j=0, temp2=0, z=0;

for(int k=0; k<input1.size(); k++) {
	while (input1[k] > input1[j+1]) {
		temp = input1[k];
		input1[k] = input1[j+1];
		input1[j+1] = temp;
		inv++;
	}
}

for(int p=0; p<input2.size(); p++) {
	
	while (input2[p] > input2[z+1]) {
		temp2 = input2[p];
		input2[p] = input2[z+1];
		input2[z+1] = temp2;
		inv++;
	}
}

for(int o=0; o<input1.size(); o++) {

		if(input1[o] > input2[o]) {
			inv++;
		}
}

cout << "Total inversions are  " << inv;
};


int main(void) {

int count=0;

vector<int> big;
vector<int> one;
vector<int> two;


ifstream inFile;

inFile.open("w2.txt");

if (!inFile) {
	cout << "Unable to open file datafile.txt";	
}

int value;

while(inFile >> value) {
	big.push_back(value);
}


for(int i=0; i<big.size()/2; i++) {
	one.push_back(big[i]);
}
	
	for(int j=big.size()/2; j<big.size(); j++) {
		two.push_back(big[j]);
	}

sort(one, two, count);

}

3 Ответов

Рейтинг:
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 (), которая работает аналогично. Если вы поищете в интернете, то найдете похожий - если не идентичный - код.

Я думаю, что остановлюсь здесь, потому что я и другие показали вам некоторые основные ошибки в вашем коде. Если вы собираетесь решить проблему более сложным способом по мере необходимости, я желаю Вам удачи.

Рейтинг:
1

Patrice T

Существует инструмент, который позволяет вам видеть, что делает ваш код, его имя отладчик Это также отличный инструмент обучения, потому что он показывает вам реальность, и вы можете увидеть, какие ожидания соответствуют реальности.
Когда вы не понимаете, что делает ваш код или почему он делает то, что он делает, ответ таков: отладчик.
Используйте отладчик, чтобы увидеть, что делает ваш код. Просто установите точку останова и посмотрите, как работает ваш код, отладчик позволит вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения.

Отладчик - Википедия, свободная энциклопедия[^]

Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]
Базовая отладка с помощью Visual Studio 2010 - YouTube[^]
Отладчик здесь, чтобы показать вам, что делает ваш код, и ваша задача-сравнить с тем, что он должен делать.
В отладчике нет никакой магии, он не находит ошибок, он просто помогает вам. Когда код не делает того, что ожидается, вы близки к ошибке.


Рейтинг:
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

Я тебя понял. Это неправильно. но это не поможет, если я удалю равенство в цикле. Я все еще получаю тот же самый ответ.

Но я думаю, что это даст мне ошибку сегментации? не так ли?