‘Suma dwóch liczb’ to kolejne zadanie, które, ćwiczy nasze zdolności programistyczne oraz pojawia się na rozmowach rekrutacyjnych. A brzmi ono następująco:
Zbadaj czy na liście licz A, znajdują się dwie liczby – a i b, których suma wynosi liczbę L.
Czyli przykładowo, mamy podaną listę A = [1,3,5,2,11,7] . Należy sprawdzić czy suma, którychkolwiek liczb na liście wynosi 9. W tym prostym przykładnie już ‘na oko’ widzimy że będą to liczby 2 oraz 7. No dobrze, ale zastanówmy się jak mógłby wyglądać nasz algorytm.
Rozwiązanie 1 – najprostsze.
1. Przeszukujemy listę, za pomocą pętli For.
2. Dla każdej liczby z listy, powtarzamy przeszukiwanie całego łańcucha i sprawdzamy czy jest w nim liczba, która po zsumowaniu wynosi tyle co nasza liczba L.
3. Po znalezieniu, przerywamy.
Tak samo jak w sortowaniu bąbelkowym, mamy tutaj do czynienia, z pętlami zagnieżdżonymi.
Przykładowe kody:
Python
Rozwiązanie 2
Rozwiązanie 2, zostawiamy w rękach czytelnika, natomiast my damy tylko wskazówkę.
W ćwiczeniu dotyczącym zliczania liter w Python, zastosowaliśmy słownik, jako 'hash table’, gdzie kluczem była litera, natomiast, jako wartość, ilość razy jaka występuje.
Jak możemy zastosować tę samą ideę, do rozwiązania naszego zadania?
A możemy przejściu przez listę liczb za pomocą pętli for, wykonywać operacje:
- dodawać obecną liczbę do hash table
- sprawdzać czy liczba, której szukamy istnieje w hash table
- jeżeli tak, to kończymy, jeżeli nie to kontynuujemy naszą pętle for
W ten sposób, nie potrzebowali byśmy zagnieżdzonej pętli for, a tylko i wyłącznie przejrzeć listę raz.
Ćwiczenia Python, dla początkujących
- Wstęp do kursu
- FizzBuzz
- Najmniejsza i największa liczba
- Zliczanie liter
- Sortowanie bąbelkowe
- Suma dwóch liczb <– bieżąca lekcja
- Wyszukiwanie binarne
- Gra w orła i reszkę
- Podsumowanie oraz dalsze kroki
