Close

Projekt Euler – zadanie 8 – Window sliding technique

Rozwiązuję sobie ostatnio zadania z Projektu Euler i natrafiłam na zadanie 8, które zainspirowało mnie do tej notki.

Największy iloczyn 13 kolejnych cyfr z 1000 cyfrowej liczby 🙂 Można to zrobić najprościej – pętla po wszystkich cyfrach, a potem branie 13 kolejnych cyfr. Wynik dla 4 kolejnych cyfr, który jest podany w treści zadania wykorzystam jako test sprawdzający.

Niestety, nie optymalne, złożoność czasowa aż O(n*k). Dla 4 liczb mamy 4 * 1000 obrotów w pętli, ale dla 13 to już 13000. A gdyby liczba była 10, 100 razy większa? Musi być inny sposób… I jest.

Window sliding technique – technika przesuwanego okienka. Można to sobie wyobrazić jako kalendarz z przesuwanym na taśmie okienkiem:

Dla uproszczenia skupię się na mniejszym przykładzie i poszukam największej sumy z wymyślonej mniejszej liczby. W tym wypadku okienko będzie mieściło w sobie 4 cyfry.

Algorytm wygląda tak:

  1. Wyliczamy początkową sumę w okienku (window_sum) – jest ona w tym momencie również maksymalną sumą (max_sum)
  2. Przesuwamy okienko – wyliczamy kolejną sumę korzystając z poprzednich  wyliczeń:
    1. od window_sum odejmujemy cyfrę, która opuściła okienko
    2. do window_sum dodajemy cyfrę, która trafiła do okieka
  3. Jeśli nowa suma jest większa niż max_sum, to za max_sum przypisujemy window_sum
  4. Jeśli mamy jeszcze jakieś cyfry w “dużej liczbie” to wracamy do punktu 2

W formie graficznej wygląda to mniej więcej tak:

 

 

 

 

 

A kod tak:

Tutaj kroków w pętli jest tyle ile wynosi długość “dużej liczby”, czyli złożoność czasowa O(n). Zupełnie nie zależy to od wielkości okienka.

Ok, ale to było dodawanie, a w zadaniu każą znaleźć największy iloczyn.

Niestety nie można po prostu przenieść wersji z dodawaniem na mnożenie:

Bardzo szybko wypadnie error, że nie wolno dzielić przez 0.

Pierwsze zabezpieczenie: sprawdźmy, czy następny element jest równy 0. Jeśli jest to przeskakujemy go i wyliczamy od nowa sumę w okienku.

Prawie dobrze, ale co w wypadku jeśli w nowym okienku znajdzie się 0, a może nawet dwa, więc omińmy je wszystkie:

Można by się jeszcze pokusić o sprawdzanie, czy w pierwszym okienku jest 0 i trochę refaktoringu. Finalnie program wygląda tak:

Więcej zadań, które można rozwiązać przy pomocy tej techniki można znaleźć tu: https://www.geeksforgeeks.org/tag/sliding-window/

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: