Tablica liczb i suma trzech liczb

1

Witam
Mam pytanie w jaki sposób z tablicy np 300 liczb sprawdzić suma których trzech liczb daje zadaną wartość. Zrobiłem to metodą brute force

int result = 0;
			for (int i = 0; i < tab.size(); i++)
				for (int j = 1; j < tab.size(); j++)
					for(int z=2;z<tab.size();z++)
						if (tab.at(i) + tab.at(j)+tab.at(z) == 5000)
							result = tab.at(i)*tab.at(j)*tab.at(z);
			cout << result;

Jest jakiś szybszy sposób?

1
  1. Posortuj oraz wyeliminuj powtórzenia => T1
  2. Stwórz tablice wszystkich możliwych par, posortuj oraz wyeliminuj powtórzenia => T2
  3. Dla każdego elementu w T1 oblicz jaka ma być suma pozostałych dwóch elementów i szukaj tej sumy metoda połowienia w T2
1

Wyglada na zadanie z pierwszego dnia AOC :)
Tez robiłem w podobny sposób. Szybciej na pewno bedzie jak wydzielisz to do metody i zwrócisz rezultat po wejsciu po raz pierwszy do tego if'a

0

Dzięki za odpowiedzi

1

W drugiej pętli możesz w sumie dać if w stylu

if(tab[i]+tab[j] > wynik){break};

Też powinno przyspieszyć.

0

zadanie z pierwszego dnia AOC

Brute-force jest zamierzonym rozwiązaniem.

$ \time -f %e python3 sol.py <1.in
241861950
0.03
$ \time -f %e python3 sol.py <2.in
218767230
0.66
$ 
0

Pełna treść zadania byłaby wskazana, bo może tam kryją się jakieś dodatkowe możliwości.

0
  1. Nie ma uzasadnienia, żeby wywoływać metodę sprawdzającą wielkość tablicy przy każdej iteracji, dlatego lepiej zapamiętać wielkość w zmiennej i jej użyć.
  2. Jak wspomniał kzkzg, warto przerwać działanie po znalezieniu różnicy albo poprzez zwrócenie wartości, albo poprzez zmianę iteratorów na niespełniające warunków pętli.
  3. Nie ma po co sprawdzać, czy indeks mieści się w zakresie tablicy przy każdym odczycie, co robi wywołanie at, skoro jest iteracja w zakresie wielkości tablicy.
  4. w pętlach wewnętrznych wystarczy iterować po elementach występujących po elemencie wskazywanym przez iterator w zewnętrznej pętli. Unika się wielokrotnego i niepotrzebnego sprawdzania tych samych trójek.
  5. Sprawa nie wydajnościowa, ale zadaniowa. Jeżeli masz znaleźć 3 elementy dające daną sumę, to nie może to być jeden i ten sam element (np. szukasz sumy 5000 i tablica zawiera elementy o wartościach 1000 i 2000 występujące po jednym razie).
int result = 0;
int S = tab.size();
			for (int i = 0; i < S; i++)
				for (int j = (i + 1); j < S; j++)
					for(int z=(j + 1);z<S;z++)
						if ((tab[i] + tab[j]+tab[z] == 5000) && (i != j) && (i != z) && (j != z))
						{
							result = tab[i]*tab[j]*tab[z];
							i = S;
							j = S;
							break;
						}
			cout << result;

1 użytkowników online, w tym zalogowanych: 0, gości: 1