Strona główna » Algorytmy » Artykuły » Najmniejsza Suma Dwóch Liczb
 

Najmniejsza Suma Dwóch Liczb

https://mattomatti.com/a0183

Zadanie

Dana jest lista liczb całkowitych. Napisz program, który znajdzie parę liczb, których suma jest najmniejsza ze wszystkich możliwych. Przetestuj napisane rozwiązanie i przeanalizuj złożoność.

Analiza

Para, która będzie miała najmniejszą sumę będzie musiała składać się z dwóch najmniejszych liczb w tablicy. Najprostszym sposobem jest posortowanie tablicy, a następnie zsumowanie dwóch najmniejszych elementów. Nie jest to jednak metoda efektywna, ponieważ tablica może być bardzo duża, a potrzeba tylko dwa najmniejsze elementy.

Znacznie lepszym pomysłem jest znaleźć minimum w tablicy, a następnie powtórzyć to pomijając znaleziony wcześniej elementy. Algorytm liniowo znajdzie w dwóch przejściach po tablicy dwa najmniejsze elementy. Można zaoszczędzić na drugim przejściu poprzez aktualizację na bieżąco dwóch wartości.

Implementacja

Funkcja najmniejszaPara() znajduje w przekazanej tablicy tab sumę dwóch najmniejszych elementów.

  1. int najmniejszaPara(int * tab, int n) {
  2.   if (n < 2) {
  3.     string wyjatek = "Za malo elementow";
  4.     throw wyjatek;
  5.   }
  6.   int min1 = INT_MAX;
  7.   int min2 = INT_MAX;
  8.   for (int i = 0; i < n; i++) {
  9.     if (tab[i] < min1) {
  10.       min2 = min1;
  11.       min1 = tab[i];
  12.     } else if (tab[i] < min2) {
  13.       min2 = tab[i];
  14.     }
  15.   }
  16.   return min1 + min2;
  17. }

Na początku należy upewnić się czy tablica składa się z co najmniej dwóch elementów. Jeśli nie to zwracamy odpowiedni wyjątek. W przeciwnym razie deklarujemy dwie zmienne o największej możliwej wartości i rozpoczynamy przeglądanie kolejnych liczb. Przyjmujemy, że min1 jest zawsze mniejsza od min2, więc kiedy wykryjemy, że kolejny element jest mniejszy od min1 to należy przepisać wartość do min2 i dopiero zaktualizować. Jednak jeśli nowa wartość jest mniejsza tylko od min2 to aktualizujemy zmienną bez dodatkowych czynności. W ten sposób na koniec w zmiennych znajdują się dwie najmniejsze wartości, których sumę należy zwrócić.

Testowanie funkcji

W celu przetestowania funkcji można skorzystać z poniższego fragmentu kodu:

  1. int main() {
  2.   int n;
  3.   cout << "Podaj dlugosc tablicy\n n = ";
  4.   cin >> n;
  5.   cout << "Podaj elementy:\n";
  6.   int * tab = new int[n];
  7.   for (int i = 0; i < n; i++)
  8.     cin >> tab[i];
  9.   try {
  10.     int minimum = najmniejszaPara(tab, n);
  11.     cout << "Minimalna para wynosi: " << minimum;
  12.   } catch (string wyjatek) {
  13.     cout << wyjatek;
  14.   }
  15.   system("pause");
  16.   return 0;
  17. }