Wskazówka:
Analiza działania algorytmu dla danych wejściowych z zadania powyżej naprowadza na ogólny wynik obliczany przez algorytm. Teraz należy tylko sformułować prawidłowo i precyzyjnie specyfikację. Dla dwóch tablic A i B posortowanych rosnąco oraz liczby x algorytm sprawdza, czy istnieje suma złożona z dowolnej liczby z tablicy A i dowolnej liczby z tablicy B, która jest równa liczbie x. Algorytm pobiera elementy z tablicy A, począwszy od pierwszego, a z tablicy B, zaczynając od elementu ostatniego. Najpierw sprawdza, czy suma obu elementów jest równa x, jeśli tak, to kończy działanie z wynikiem PRAWDA, w przeciwnym razie sprawdza, czy suma jest mniejsza od x. Jeżeli tak, to bierze do sumy kolejny (większy od poprzedniego) element z tablicy A (indeks i zwiększa się o 1). Jeżeli zaś suma jest większa od x, bierze mniejszy element z tablicy B (indeks j zmniejsza się o 1). Dzięki takim przesunięciom i oraz j nie gubi dobrej sumy.

Przyspieszenie takiego sprawdzania jest możliwe dzięki odpowiedniej kolejności przeglądania tablic (zmienne i, j) oraz pominięciu zbędnych sum, o których wiadomo, że są albo za duże, albo za małe w stosunku do x.
Powrót do pytań