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.

  1. pair<int, int> najblizszeElementy(vector<int> tab1, vector<int> tab2, int x) {
  2.   pair<int, int> wynik = make_pair(0, 0);
  3.   int roznica = INT_MAX;
  4.   for (int i = 0; i < tab1.size(); i++) {
  5.     for (int j = 0; j < tab2.size(); j++) {
  6.       int teraz = abs(tab1[i] + tab2[j] - x);
  7.       if (teraz < roznica) {
  8.         roznica = teraz;
  9.         wynik = make_pair(tab1[i], tab2[j]);
  10.       }
  11.     }
  12.   }
  13.   return wynik;
  14. }

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.

  1. pair<int, int> najblizszeElementy(vector<int> tab1, vector<int> tab2, int x) {
  2.   pair<int, int> wynik = make_pair(0, 0);
  3.   int roznica = INT_MAX;
  4.   int i1 = 0, i2 = tab2.size() - 1;
  5.   while (i1 < tab1.size() && i2 >= 0)  {
  6.     int teraz = abs(tab1[i1] + tab2[i2] - x);
  7.     if (teraz < roznica) {
  8.       wynik = make_pair(tab1[i1], tab2[i2]);
  9.       roznica = teraz;
  10.     }
  11.     if (tab1[i1] + tab2[i2] > x) {
  12.       i2--;
  13.     } else {
  14.       i1++;
  15.     }
  16.   }
  17.   return wynik;
  18. }

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.

  1. vector<int> wczytajListe() {
  2.   int n;
  3.   cout << "Ile elementow ma lista?\n n = ";
  4.   cin >> n;
  5.   cout << "Podaj elementy:\n";
  6.   vector<int> lista; int tmp;
  7.   while (n-- > 0) {
  8.     cin >> tmp;
  9.     lista.push_back(tmp);
  10.   }
  11.   return lista;
  12. }
  13. int main () {
  14.   vector<int> tab1 = wczytajListe();
  15.   vector<int> tab2 = wczytajListe();
  16.   int x;
  17.   cout << "Podaj sume do osiagniecia:\n x = ";
  18.   cin >> x;
  19.   pair<int, int> wynik = najblizszeElementy(tab1, tab2, x);
  20.   cout << "Najblizsza para " << wynik.first << ", " << wynik.second;
  21.   system("pause");
  22.   return 0;
  23. }