Wydrukuj następny najmniejszy z 2 ^ i * 5 ^ j gdzie i, j> = 0

Zadano mi to pytanie podczas technicznego przeglądu telefonu i nie zrobiłem tego dobrze. Pytanie zostało zawarte dosłownie poniżej.

Generuj {2^i * 5^j | i,j >= 0}posortowaną kolekcję. Ciągłe drukowanie następnej najmniejszej wartości.

Przykład: { 1, 2, 4, 5, 8, 10...}

„Następny najmniejszy” sprawia, że ​​myślę, że wiąże się to z niewielką stertą, ale tak naprawdę nie wiedziałem, dokąd się udać i ankieter nie udzielił żadnej pomocy.

Czy ktoś ma porady, jak rozwiązać taki problem?

Przeredagujmy problem: wypisz każdą liczbę od 1 do nieskończoności, aby liczba nie zawierała żadnych czynników oprócz 2 i 5.

Poniżej znajduje się prosty fragment kodu w języku C #:

for (int i = 1;;++i)
{
    int num = i;
    while(num%2 == 0) num/=2;
    while(num%5 == 0) num/=5;
    if(num == 1) Console.WriteLine(i);
}

Podejście Kiliana / QuestionC jest znacznie bardziej wydajne. Fragment kodu C # przy takim podejściu:

var itms = new SortedSet<int>();
itms.Add(1);
while(true)
{
    int cur = itms.Min;
    itms.Remove(itms.Min);
    itms.Add(cur*2);
    itms.Add(cur*5);
    Console.WriteLine(cur);
}

SortedSet zapobiega duplikowaniu wstawek.

Zasadniczo działa, upewniając się, że następny numer w sekwencji jest w itms.

Dowód, że to podejście jest poprawne:
opisany algorytm zapewnia, że ​​po dowolnej liczbie danych wyjściowych w formularzu 2^i*5^j, zestaw zawiera teraz 2^(i+1)*5^ji 2^i*5^(j+1). Załóżmy, że kolejnym numerem w sekwencji jest 2^p*5^q. Musi istnieć poprzednio wyprowadzony numer formularza 2^(p-1)*5^(q)lub 2^p*5^(q-1)(lub oba, jeśli ani p, ani q nie są równe 0). Jeśli nie, to 2^p*5^qnie jest kolejny numer, ponieważ 2^(p-1)*5^(q)i 2^p*5^(q-1)to zarówno mniejsze.

Drugi fragment wykorzystuje O(n)pamięć (gdzie n jest liczbą wyprowadzonych liczb), ponieważ O(i+j) = O(n)(ponieważ oba i i są mniejsze niż n), i znajdzie n liczb w O(n log n)czasie. Pierwszy fragment znajduje liczby w czasie wykładniczym.

To pytanie jest dość powszechne, dlatego warto znać odpowiedź. Oto odpowiedni wpis w moim osobistym arkuszu łóżeczka:

• do generowania liczb postaci 3 5 ^b 7 ^c , aby rozpocząć się 1, treści wszystkich trzech możliwych programów (3, 5, 7) na konstrukcji pomocniczej, a następnie dodać najmniejszą liczbę od niego liście.

Innymi słowy, potrzebujesz dwuetapowego podejścia z dodatkowym posortowanym buforem, aby rozwiązać to skutecznie. (Dobry dłuższy opis znajduje się w Wywiad Cracking the Coding przeprowadzonym przez Gayle McDowell.

Oto odpowiedź, która działa ze stałą pamięcią, kosztem procesora. To nie jest dobra odpowiedź w kontekście pierwotnego pytania (tj. Odpowiedzi podczas wywiadu). Ale jeśli wywiad trwa 24 godziny, to nie jest tak źle. ;)

Chodzi o to, że jeśli mam n, która jest poprawną odpowiedzią, to następną w sekwencji będzie n razy potęga dwóch, podzielona przez potęgę 5. Albo n razy potęga 5, podzielona przez potęga dwóch. Pod warunkiem, że dzieli się równomiernie. (... lub dzielnikiem może być 1;), w którym to przypadku pomnożymy przez 2 lub 5)

Na przykład, aby przejść z 625 do 640, należy pomnożyć przez 5 ** 4/2 ** 7. Lub, bardziej ogólnie, pomnożyć przez pewną wartość 2 ** m * 5 ** ndla pewnego m, n, gdzie jeden jest dodatni, a drugi ujemny lub zero, a mnożnik dzieli liczbę równomiernie.

Teraz trudną częścią jest znalezienie mnożnika. Wiemy jednak: a) dzielnik musi dzielić liczbę równomiernie, b) mnożnik musi być większy niż jeden (liczby ciągle rosną), c) jeśli wybierzemy najniższy mnożnik większy niż 1 (tj. 1 <f <wszystkie pozostałe f ), to z pewnością będzie nasz następny krok. Kolejny krok będzie najniższym krokiem.

Paskudną częścią jest znalezienie wartości m, n. Możliwości są tylko log (n), ponieważ jest tylko tyle 2 lub 5 do zrezygnowania, ale musiałem dodać współczynnik -1 do +1 jako niechlujny sposób radzenia sobie z zaokrągleniem. Musimy więc tylko iterować przez O (log (n)) na każdym kroku. Więc ogólnie jest to O (n log (n)).

Dobrą wiadomością jest to, że ponieważ wymaga ona wartości i znajduje następną wartość, możesz zacząć w dowolnym miejscu w sekwencji. Jeśli więc chcesz mieć następny po 1 miliardie, możesz go po prostu znaleźć, wykonując iteracje 2/5 lub 5/2 i wybierając najmniejszy mnożnik większy niż 1.

(pyton)

MAX = 30
F = - math.log(2) / math.log(5)

def val(i, j):
    return 2 ** i * 5 ** j

def best(i, j):
    f = 100
    m = 0
    n = 0
    max_i = (int)(math.log(val(i, j)) / math.log(2) + 1) if i + j else 1
    #print((val(i, j), max_i, x))
    for mm in range(-i, max_i + 1):
        for rr in {-1, 0, 1}:
            nn = (int)(mm * F + rr)
            if nn < -j: continue
            ff = val(mm, nn)
            #print('  ' + str((ff, mm, nn, rr)))
            if ff > 1 and ff < f:
                f = ff
                m = mm
                n = nn
    return m, n

def detSeq():

    i = 0
    j = 0
    got = [val(i, j)]

    while len(got) < MAX:
        m, n = best(i, j)

        i += m
        j += n
        got.append(val(i, j))

        #print('* ' + str((val(i, j), m, n)))
        #print('- ' + str((v, i, j)))

    return got

Zweryfikowałem pierwsze 10 000 liczb, które to generuje, względem pierwszych 10 000 wygenerowanych przez posortowane rozwiązanie listy, i działa to przynajmniej tak daleko.

BTW, następny po bilionie wydaje się być 1 024 000 000 000.

...

Hm Mogę uzyskać wydajność O (n) - O (1) na wartość (!) - i zużycie pamięci O (log n) traktując best()jako tabelę odnośników, którą stopniowo rozszerzam. Obecnie oszczędza pamięć, iterując za każdym razem, ale wykonuje wiele zbędnych obliczeń. Trzymając te wartości pośrednie - i listę minimalnych wartości - mogę uniknąć zduplikowanej pracy i bardzo ją przyspieszyć. Jednak lista wartości pośrednich będzie rosła wraz z n, stąd pamięć O (log n).

Brian miał absolutną rację - moja inna odpowiedź była zbyt skomplikowana. Oto prostszy i szybszy sposób na zrobienie tego.

Wyobraź sobie kwadrant I płaszczyzny euklidesowej, ograniczony do liczb całkowitych. Nazwij jedną oś osią i, a drugą oś osią j.

Oczywiście punkty w pobliżu źródła będą wybierane przed punktami daleko od źródła. Należy również pamiętać, że obszar aktywny odsunie się od osi i, zanim odejdzie od osi j.

Kiedy punkt zostanie wykorzystany, nigdy więcej go nie użyje. I punktu można użyć tylko wtedy, gdy punkt znajdujący się bezpośrednio pod nim lub po jego lewej stronie został już użyty.

Zestawiając je razem, możesz wyobrazić sobie „granicę” lub „krawędź wiodącą”, która zaczyna się wokół początku i rozkłada się w górę iw prawo, rozciągając się wzdłuż osi i dalej niż na osi j.

W rzeczywistości możemy dowiedzieć się czegoś więcej: na granicy / krawędzi będzie co najwyżej jeden punkt dla dowolnej wartości i. (Musisz zwiększyć i więcej niż 2 razy, aby równać się przyrostowi j.) Tak więc możemy przedstawić granicę jako listę zawierającą jeden element dla każdej współrzędnej i, zmieniając się tylko ze współrzędną j i wartością funkcji.

Za każdym przejściem wybieramy minimalny element na krawędzi natarcia, a następnie przesuwamy go raz w kierunku j. Jeśli zdarza się, że podnosimy ostatni element, dodajemy nowy ostatni jeszcze element o zwiększonej wartości i i wartości j równej 0.

using System;
using System.Collections.Generic;
using System.Text;

namespace TwosFives
{
    class LatticePoint : IComparable<LatticePoint>
    {
      public int i;
      public int j;
      public double value;
      public LatticePoint(int ii, int jj, double vvalue)
      {
          i = ii;
          j = jj;
          value = vvalue;
      }
      public int CompareTo(LatticePoint rhs)
      {
          return value.CompareTo(rhs.value);
      }
    }


    class Program
    {
        static void Main(string[] args)
        {
            LatticePoint startPoint = new LatticePoint(0, 0, 1);

            var leadingEdge = new List<LatticePoint> { startPoint } ;

            while (true)
            {
                LatticePoint min = leadingEdge.Min();
                Console.WriteLine(min.value);
                if (min.j + 1 == leadingEdge.Count)
                {
                    leadingEdge.Add(new LatticePoint(0, min.j + 1, min.value * 2));
                }
                min.i++;
                min.value *= 5;
            }
        }
    }
}

Spacja: O (n) w liczbie wydrukowanych do tej pory elementów.

Wstawki Speed: O (1), ale nie są wykonywane za każdym razem. (Czasami dłuższy, gdy List<>musi rosnąć, ale nadal amortyzuje się O (1)). Zlewem czasowym jest poszukiwanie minimum, O (n) w liczbie wydrukowanych do tej pory elementów.

Rozwiązanie oparte na zestawie było prawdopodobnie tym, czego szukał twój ankieter, ma jednak niefortunną konsekwencję posiadania O(n)pamięci i O(n lg n)całkowitego czasu na sekwencjonowanie nelementów.

Trochę matematyki pomaga nam znaleźć rozwiązanie dotyczące O(1)przestrzeni i O(n sqrt(n))czasu. Zauważ to 2^i * 5^j = 2^(i + j lg 5). Znalezienie pierwszych nelementów {i,j > 0 | 2^(i + j lg 5)}sprowadza się do znalezienia pierwszych nelementów {i,j > 0 | i + j lg 5}, ponieważ funkcja (x -> 2^x)jest ściśle monotonicznie rośnie, więc jedynym sposobem dla niektórych a,bto 2^a < 2^bjest, jeśli a < b.

Teraz potrzebujemy algorytmu, aby znaleźć sekwencję i + j lg 5, gdzie i,jsą liczby naturalne. Innymi słowy, biorąc pod uwagę naszą bieżącą wartość tego i, j, co minimalizuje następny ruch (tj. Daje nam następną liczbę w sekwencji), następuje pewien wzrost jednej z wartości (powiedzmy j += 1) wraz ze spadkiem drugiej ( i -= 2). Jedyną rzeczą, która nas ogranicza, jest to i,j > 0.

Są tylko dwa przypadki do rozważenia - iwzrosty lub jwzrosty. Jeden z nich musi wzrosnąć, ponieważ nasza sekwencja rośnie, i oba nie rosną, ponieważ w przeciwnym razie pomijamy termin, w którym mamy tylko jeden i,jwzrost. W ten sposób jeden wzrasta, a drugi pozostaje taki sam lub maleje. W języku C ++ 11 cały algorytm i jego porównanie z zestawem rozwiązań są dostępne tutaj .

Osiąga to stałą pamięć, ponieważ w metodzie jest tylko stała liczba obiektów, oprócz tablicy wyjściowej (patrz link). Metoda osiąga czas logarytmiczny przy każdej iteracji, ponieważ dla dowolnej danej (i,j), przechodzi do najlepszej pary (a, b), która (i + a, j + b)jest najmniejszym wzrostem wartości i + j lg 5. To przejście to O(i + j):

Attempt to increase i:
++i
current difference in value CD = 1
while (j > 0)
  --j
  mark difference in value for
     current (i,j) as CD -= lg 5
  while (CD < 0) // Have to increase the sequence
    ++i          // This while will end in three loops at most.
    CD += 1
find minimum among each marked difference ((i,j) -> CD)

Attempt to increase j:
++j
current difference in value CD = lg 5
while (j > 0)
  --i
  mark difference in value for
     current (i,j) as CD -= 1
  while (CD < 0) // have to increase the sequence
    ++j          // This while will end in one loop at most.
    CD += lg 5
find minimum among each marked difference ((i,j) -> CD)

Każda iteracja próbuje inastępnie zaktualizować ji idzie w parze z mniejszą aktualizacją obu.

Ponieważ ii jjesteśmy najwyżej O(sqrt(n)), mamy całkowity O(n sqrt(n))czas. ii jrosną z szybkością kwadratu nod tego czasu dla dowolnych maksymalnych wartości imaxi jmaxistnieją O(i j)unikalne pary, z których można utworzyć naszą sekwencję, jeśli nasza sekwencja jest nwyrażeniami, ii jrosną w obrębie pewnego stałego współczynnika względem siebie (ponieważ wykładnik składa się z liniowego połączenie dwóch), wiemy o tym ii jsą O(sqrt(n)).

Nie trzeba się zbytnio przejmować błędem zmiennoprzecinkowym - ponieważ warunki rosną wykładniczo, musielibyśmy poradzić sobie z przepełnieniem, zanim błąd flopa nas dopadnie, o kilka wielkości. Dodam do tego więcej dyskusji, jeśli będę miał czas.