Wyznaczenie maksymalnej różnicy.

0

Jak wyznaczyć największą różnicę z ciągu liczb całkowitych? Bardzo proszę o podanie rozwiązania w języku C++. Problem jest w tym, że program musi wykonywać się bardzo szybko. Na tyle szybko aby móc znaleźć tą największą różnicę w ciągu o wielkości nawet 10^9.

0

Że niby mamy za ciebie odrobić pracę domową? o_O Posortuj sobie ciąg wejściowy a potem odejmij najmniejszą liczbę od największej. Za wolne? Pomyśl.

0

Za wolne. Mój kod wygląda tak:

#include<iostream>
#include<cstdio>
using namespace std;
int n;
void qsort(int *tab, int left, int right)
{
	if(left<right)
	{
		int m=left;
		for(int i=left+1; i <=right; i++)
			if(tab[i]<tab[left])
				swap(tab[++m], tab[i]);
		swap(tab[left], tab[m]);
		qsort(tab, left, m-1);
		qsort(tab,m+1,right);
	}
}
int main()
{
	cin >> n;
	int *wsk = new int [n];
	for (int i = 0; i < n; i++)
	{
		cin >> wsk[i];
	}
	qsort(wsk, 0, n-1);
	cout << wsk[n-1] - wsk[0];
    cin.ignore();
    getchar();
    return 0;
}
0

Szukasz najwiekszej i najmniejszej liczby w ciagu. Jak juz je znajdziesz to masz najwieksza roznice.

0

Pomoże mi ktoś???

0

Przecież 0x20 opisał ci całe rozwiązanie.

0

No sorry bardzo, możesz mi powiedzieć gdzie? On tylko przepisał treść zadania. Potrzebuje konkretów. Mogę oczywiście przelecieć całą tablicę w poszukiwaniu tych elementów ale to za wolne rozwiązanie. Potrzebuje S Z Y B K I E G O

0

Primo:
Nie musisz mieć żadnej tablicy. Minimum i maksimum możesz wyznaczać na bieżąco podczas wczytywania.

Secundo:
Przelecenie tablicy to Theta(n). Przelecenie jej 5 razy to dalej Theta(n). Samo wczytanie n elementów to Theta(n). QuickSort to w średnim przypadku Theta(n lg n).

0

Wiem, że QuickSort ma złożoność n log n, ale mimo to sprawdzarka (program napisany przez mojego nauczyciela informatyki, który na danych testach sprawdza poprawność działania testowanego programu) zwraca 0 punktów w teście na największych liczbach. No cóż. Może jednak wina leży po stronie sprawdzarki.

PS: a propoS twojego primo. Jak to możliwe, żeby od razu na wejściu wyznaczyć min i max? Możesz podać fragment kodu realizujący coś takiego? Pierwszy raz słyszę o czymś takim.

0

@Valiors o_O normalnie, w trakcie czytania liczb pamiętasz aktualnie największą i najmniejszą. W ogóle nie musisz tu nic tablicować.Ot, jeśli nowa liczba jest większa od aktualnego maxa to zapamiętujesz ją jako max, a jak mniejsza od mina to zapamiętujesz jako min...

0

Bez jaj :D. Dzięki za pomoc.

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.