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.
Ż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.
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;
}
Szukasz najwiekszej i najmniejszej liczby w ciagu. Jak juz je znajdziesz to masz najwieksza roznice.
Pomoże mi ktoś???
Przecież 0x20 opisał ci całe rozwiązanie.
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
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).
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.
@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...
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.