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.
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.
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.
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.
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.
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 1 | El 2 | ∆ | Różnica | Komentarz |
|---|---|---|---|---|
| 1 | 30 | |1 + 30 - 23| = 8 | ∞ | Aktualizacja różnicy, suma większa od x, więc zmniejszamy indeks tab2 |
| 1 | 20 | |1 + 20 - 23| = 2 | 8 | Aktualizacja różnicy, suma mniejsza od x, więc zwiększamy indeks tab1 |
| 4 | 20 | |4 + 20 - 23| = 1 | 2 | Aktualizacja różnicy, suma większa od x, więc zmniejszamy indeks tab2 |
| 4 | 10 | |4 + 10 - 23| = 9 | 1 | Suma mniejsza od x, więc zwiększamy indeks tab1 |
| 5 | 10 | |5 + 10 - 23| = 8 | 1 | Suma mniejsza od x, więc zwiększamy indeks tab1 |
| 7 | 10 | |7 + 10 - 23| = 6 | 1 | Suma 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.
Oto przykładowa funkcja najblizszeElementy(), która realizuje przedstawiony powyżej algorytm.
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.
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.