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(n²). 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.

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. }
14. int main () {
15.   vector<int> tab1 = wczytajListe();
16.   vector<int> tab2 = wczytajListe();
17.   int x;
18.   cout << "Podaj sume do osiagniecia:\n x = ";
19.   cin >> x;
20.   pair<int, int> wynik = najblizszeElementy(tab1, tab2, x);
21.   cout << "Najblizsza para " << wynik.first << ", " << wynik.second;
22.   system("pause");
23.   return 0;
24. }

• Kod źródłowy Proste rozwiązanie
• Kod źródłowy Optymalne rozwiązanie