Rozważ następujący problem:
Niech będzie skończonym podzbiorem liczb naturalnych.
Niech | gdzie jest największy wspólny dzielnik z i
Znajdź element maksymalny w .
Problem ten można rozwiązać, biorąc największy wspólny dzielnik z każdej pary za pomocą algorytmu Euclid i śledząc największy.
Czy istnieje bardziej skuteczny sposób na rozwiązanie tego problemu?
algorithms
number-theory
Tommy
źródło
źródło
Odpowiedzi:
Oto wydajny algorytm (w języku Python ). Poniżej znajdziesz wyjaśnienie.
Objaśnienie powyższego fragmentu kodu:
W tym problemie obserwujemy:
max(S)
S
max
wszystkie takie liczby z wyżej wymienioną właściwością.Dzięki tym obserwacjom program wykonuje następujące czynności:
set
z listy. Ponieważ zestawy można efektywnie przeszukiwaćO(log(n))
m
.m
kasy1
, znajdź pierwszą liczbę, która ma dwa lub więcej wielokrotności w zestawie. Pierwszy taki znaleziony numer jest wynikiem.Mam nadzieję, że to jasne. Daj mi znać, jeśli potrzebujesz bardziej szczegółowych wyjaśnień.
źródło
i
rozpoczynający sięm
aż1
sprawdzamy, czy dwie lub więcej wielokrotności zi
znajdują się w zestawie. W tym przykładzie dwie wielokrotności liczby 2 znajdują się w zestawie „2 i 4”. więc odpowiedź brzmi 2. Wewnętrznawhile
pętla sprawdza wszystkie wielokrotnościi
tillm' as
m` jest masx listy.