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

Dokładna Suma

https://mattomatti.com/a0160

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. static Tuple<int, int> najblizszeElementy(int[] tab1, int[] tab2, int x) {
  2.   Tuple<int, int> wynik = new Tuple<int, int>(0, 0);
  3.   int roznica = int.MaxValue;
  4.   for (int i = 0; i < tab1.Length; i++) {
  5.     for (int j = 0; j < tab2.Length; j++) {
  6.       int teraz = Math.Abs(tab1[i] + tab2[j] - x);
  7.       if (teraz < roznica) {
  8.         roznica = teraz;
  9.         wynik = new Tuple<int, int>(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 2∆RóżnicaKomentarz
130|1 + 30 - 23| = 8∞Aktualizacja 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. static Tuple<int, int> najblizszeElementy(int[] tab1, int[] tab2, int x) {
  2.   Tuple<int, int> wynik = new Tuple<int, int>(0, 0);
  3.   int roznica = int.MaxValue;
  4.   int i1 = 0, i2 = tab2.Length - 1;
  5.   while (i1 < tab1.Length && i2 >= 0) {
  6.     int teraz = Math.Abs(tab1[i1] + tab2[i2] - x);
  7.     if (teraz < roznica) {
  8.       wynik = new Tuple<int, int>(tab1[i1], tab2[i2]);
  9.       roznica = teraz;
  10.     }
  11.     if (tab1[i1] + tab2[i2] > x) {
  12.       i2--;
  13.     }
  14.     else {
  15.       i1++;
  16.     }
  17.   }
  18.   return wynik;
  19. }

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. static int[] wczytajListe() {
  2.   Console.WriteLine("Podaj elementy:");
  3.   string[] dane = Console.ReadLine().Split(' ');
  4.   int[] lista = new int[dane.Length];
  5.   for(int i = 0; i < dane.Length; i++) {
  6.     lista[i] = Convert.ToInt32(dane[i]);
  7.   }
  8.   return lista;
  9. }
  11. static void Main(string[] args) {
  12.   int[] tab1 = wczytajListe();
  13.   int[] tab2 = wczytajListe();
  14.   Console.Write("Podaj sumę do osiągnięcia:\n x = ");
  15.   int x = Convert.ToInt32(Console.ReadLine());
  16.   Tuple<int, int> wynik = najblizszeElementy(tab1, tab2, x);
  17.   Console.WriteLine("Najbliższa para {0}, {1}", wynik.Item1, wynik.Item2);
  18.   Console.ReadKey();
  19. }