Najmniejsza Suma Dwóch Liczb

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. static int najmniejszaPara(int[] tab) {
2.   if (tab.Length < 2)
3.     throw new Exception("Za mało elementów");
4.   int min1 = int.MaxValue;
5.   int min2 = int.MaxValue;
6.   for (int i = 0; i < tab.Length; i++) {
7.     if (tab[i] < min1) {
8.       min2 = min1;
9.       min1 = tab[i];
10.     } else if (tab[i] < min2) {
11.       min2 = tab[i];
12.     }
13.   }
14.   return min1 + min2;
15. }

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. static void Main(string[] args) {
2.   Console.WriteLine("Podaj elementy:");
3.   string[] data = Console.ReadLine().Split(' ');
4.   int[] tab = new int[data.Length];
5.   for (int i = 0; i < data.Length; i++)
6.     tab[i] = Convert.ToInt32(data[i]);
7.   try {
8.     int minimum = najmniejszaPara(tab);
9.     Console.WriteLine("Minimalna para wynosi: {0}", minimum);
10.   } catch (Exception ex) {
11.     Console.WriteLine(ex.Message);
12.   }
13.   Console.ReadKey();
14. }

• Kod źródłowy Implementacja