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.

C++C#
Python
  1. def najmniejszaPara(tab):
  2.   if(len(tab) < 2):
  3.     raise Exception("Za mało elementów")
  4.   min1, min2 = sys.maxsize, sys.maxsize
  5.   for x in tab:
  6.     if (x < min1):
  7.       min2 = min1
  8.       min1 = x
  9.     elif (x < min2):
  10.       min2 = x
  11.   return min1 + min2

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:

C++C#
Python
  1. print("Podaj elementy:")
  2. tab = [int(x) for x in input().split()]
  3. try:
  4.   minimum = najmniejszaPara(tab)
  5.   print("Minimalna para wynosi:", minimum)
  6. except Exception as error:
  7.   print(error)