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
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.