Strona główna » Algorytmy » Artykuły » Dokładna Suma
 

Dokładna Suma

Zadanie

Dane są dwie, posortowane tablice liczb całkowitych oraz wartość x. Zadanie polega na znalezieniu po jednym elemencie z każdej tablicy, które w sumie najmniej różnią się od zadanej wartości x. Napisz program, który dla wczytanych danych wypisze odpowiednią parę liczb.

Przykład

Weźmy przykładowo następujące tablice: tab1 = [1, 4, 5, 7] oraz tab2 = [10, 20, 30]. Zadana zostaje wartość x = 17. Może zostać uzyskana poprzez wybór 7 z tab1 i 10 z tab2. Jednak suma elementów nie zawsze będzie taka jak podany x. Weźmy tym razem wartość 23. Poprawna odpowiedź to 4 i 20. Uzyskana suma jest o 1 większa od x, ale drugą najbliższą sumą jest 1 + 20 = 21, ale wtedy suma jest odległa od x o 2.

Implementacja

Rozwiązanie proste

Najprostszym rozwiązaniem jest sprawdzenie wszystkich możliwych par liczb i wybranie tej, której suma najmniej różni się od zadanej wartości x. Jest to nieoptymalne rozwiązanie siłowe o złożoności czasowej O(n2). Poniżej został zamieszczony przykładowy kod funkcji. Funkcja najblizszeElementy() przyjmuje kolejno wczytane tablice tab1 i tab2 oraz docelową wartość x.

C++C#
Python
  1. def najblizszeElementy(tab1, tab2, x):
  2.   wynik = (0, 0)
  3.   roznica = sys.maxsize
  4.   for i in range(len(tab1)):
  5.     for j in range(len(tab2)):
  6.       teraz = abs(tab1[i] + tab2[j] - x)
  7.       if (teraz < roznica):
  8.         roznica = teraz
  9.         wynik = (tab1[i], tab2[j])
  10.   return wynik

Algorytm składa się z dwóch pętli. Wybierane są kolejne pary elementów z obu tablic, a następnie obliczania różnica pomiędzy sumą, a wartością x. Jeśli różnica jest mniejsza od poprzednio wyznaczonej (lub domyślnej) to przypisz zmiennej wynik zalezioną parę liczb i zaktualizuj zapamiętaną różnicę. Na koniec zwrócona zostaje para liczb.

Rozwiązanie optymalne

Proces wyszukiwania pary liczb można zoptymalizować poprzez wybór tylko tych par, które rzeczywiście mają szansę uzyskać jak najdokładniejszą sumę. W tym celu należy skorzystać z faktu, że obie tablice są posortowane.

Algorytm rozpoczynamy od ustawienia indeksów na pierwszym elemencie tab1 oraz ostaniego elementu tab2. Dla każdej wybranej pary obliczamy różnicę i aktualizujemy tą zapamiętaną oraz wynik odpowiednio (jak w poprzednim przykładzie). Po aktualizacji różnicy należy odpowiednio zmienić też indeksy. Jeśli obliczona suma jest większa od x to należy zmniejszyć indeks tab2, a w przeciwnym razie zwiększyć tab1. W ten sposób zostaną przejrzane wszystkie możliwe pary. Algorytm kończy się, gdy wybrana ma być element z którejś tablicy, który nie istnieje.

Przykład

Wróćmy do tablic podanych na początku artykułu tab1 = [1, 4, 5, 7] oraz tab2 = [10, 20, 30]. Sprawdźmy działanie algorytmu dla x = 23.

El 1El 2RóżnicaKomentarz
130|1 + 30 - 23| = 8Aktualizacja różnicy, suma większa od x, więc zmniejszamy indeks tab2
120|1 + 20 - 23| = 28Aktualizacja różnicy, suma mniejsza od x, więc zwiększamy indeks tab1
420|4 + 20 - 23| = 12Aktualizacja różnicy, suma większa od x, więc zmniejszamy indeks tab2
410|4 + 10 - 23| = 91Suma mniejsza od x, więc zwiększamy indeks tab1
510|5 + 10 - 23| = 81Suma mniejsza od x, więc zwiększamy indeks tab1
710|7 + 10 - 23| = 61Suma mniejsza od x, więc zwiększamy indeks tab1

W tym momencie algorytm kończy działanie, ponieważ kolejny element tablicy tab1 nie istnieje. Znaleziona została para wcześniej wskazana (4, 20), która różni się od x tylko o 1.

Rozwiązanie

Oto przykładowa funkcja najblizszeElementy(), która realizuje przedstawiony powyżej algorytm.

C++C#
Python
  1. def najblizszeElementy(tab1, tab2, x):
  2.   wynik = (0, 0)
  3.   roznica = sys.maxsize
  4.   i1, i2 = 0, len(tab2) - 1
  5.   while (i1 < len(tab1) and i2 >= 0):
  6.     teraz = abs(tab1[i1] + tab2[i2] - x)
  7.     if (teraz < roznica):
  8.       wynik = (tab1[i1], tab2[i2])
  9.       roznica = teraz
  10.     if (tab1[i1] + tab2[i2] > x):
  11.       i2 -= 1
  12.     else:
  13.       i1 += 1
  14.   return wynik

Algorytm na początku przypisuje indeksy: i1 - indeks tablicy tab1 o początkowej wartości 0, a potem i2 - indeks tablicy i2 ustawiony na jej ostatni element. Następnie w pętli dopóki, któryś z indeksów nie wykroczy poza zakres tablicy: sprawdzana jest wybrana para i aktualizowana różnica i wynik jeśli zajdzie potrzeba. Na koniec każdej pętli zostaje zaktualizowany odpowiedni indeks.

Testowanie funkcji

W celu przetestowania wybranej wersji kodu można skorzystać z poniższego fragmentu kodu, który wczyta odpowiednie dane, a następnie wypisze na ekran wynik.

C++C#
Python
  1. def wczytajListe():
  2.   print("Podaj elementy:")
  3.   return [int(x) for x in input().split()]
  4. tab1 = wczytajListe()
  5. tab2 = wczytajListe()
  6. x = int(input("Podaj sumę do osiągnięcia:\n x = "))
  7. wynik = najblizszeElementy(tab1, tab2, x);
  8. print("Najbliższa para", wynik[0], "i", wynik[1])