Podstępne pytanie do wywiadu Google


169

Mój przyjaciel przeprowadza rozmowę kwalifikacyjną o pracę. Jedno z pytań podczas rozmowy kwalifikacyjnej sprawiło, że pomyślałem, po prostu chciałem uzyskać opinię.

Istnieją 2 nieujemne liczby całkowite: i oraz j. Biorąc pod uwagę następujące równanie, znajdź (optymalne) rozwiązanie, aby wykonać iterację po i i j w taki sposób, aby wyniki były sortowane.

2^i * 5^j

Tak więc pierwsze kilka rund wyglądałoby tak:

2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25

Chociaż się staram, nie widzę wzoru. Twoje myśli?


63
Optymalnym algorytmem pod względem czasu programisty jest generowanie za pomocą dwóch zagnieżdżonych pętli, a następnie sortowanie. Dlaczego zadają takie pytania?
Tom Zych

21
Możesz określić punkty przejścia, sprawdzając, która liczba jest większa. 2^2 < 5ale 2^3 > 5w tym momencie zwiększasz j. Myślę, że możesz wygenerować wynik w O (n) zamiast O (nlgn). @ tom-zynch dwie zagnieżdżone pętle to O (n ^ 2). To pytanie jest bardzo ważne
Michaił

1
Jest tylko jedno wyjście, więc optymalnym rozwiązaniem jest O (n). Przeczytaj moje rozwiązanie poniżej
Michaił

3
Podobna kwestia została już wcześniej rozwiązana: stackoverflow.com/questions/4600048/nth-ugly-number .

1
... a OP prawdopodobnie już powinien wybrać odpowiedź. W końcu ma już wiele dobrych.
abeln

Odpowiedzi:


123

Dijkstra wywodzi wymowne rozwiązanie w „Dyscyplinie programowania”. Przypisuje problem Hammingowi. Oto moja implementacja rozwiązania Dijkstry.

int main()
{
    const int n = 20;       // Generate the first n numbers

    std::vector<int> v(n);
    v[0] = 1;

    int i2 = 0;             // Index for 2
    int i5 = 0;             // Index for 5

    int x2 = 2 * v[i2];     // Next two candidates
    int x5 = 5 * v[i5];

    for (int i = 1; i != n; ++i)
    {
        int m = std::min(x2, x5);
        std::cout << m << " ";
        v[i] = m;

        if (x2 == m)
        {
            ++i2;
            x2 = 2 * v[i2];
        }
        if (x5 == m)
        {
            ++i5;
            x5 = 5 * v[i5];
        }
    }

    std::cout << std::endl;
    return 0;
}

18
Odpowiedni link: en.wikipedia.org/wiki/Regular_number#Algorithms . Nawiasem mówiąc, to nie jest dobre pytanie do wywiadu. Oto (odręczny artykuł) autorstwa Dijkstry, w którym podaje i udowadnia algorytm tego problemu: cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF
Elian Ebbing

Gdy celem jest „iteracja po i i j”, potrzebujesz mniejszej pojemności, wystarczy FIFO. Zobacz moje rozwiązanie w języku Python.
GaBorgulya

7
Kiedy celem jest „iteracja po i i j”, nie jest to ten sam problem.
mhum

To naprawdę fajna implementacja, wykorzystująca minimum pamięci. Jest to pamięć liniowa, nawet jeśli chcesz mieć tylko jedną liczbę.
Thomas Ahle

1
@ThomasAhle nie wiem czy widziałeś ten jednak ma kod na końcu, który jest zdolny do obliczania n-ty numer w izolacji. Na przykład miliardowa liczba .
Will Ness

47

tutaj jest bardziej wyrafinowany sposób na zrobienie tego (bardziej wyrafinowany niż moja poprzednia odpowiedź, to znaczy):

wyobraź sobie, że liczby są umieszczone w macierzy:

     0    1    2    3    4    5   -- this is i
----------------------------------------------
0|   1    2    4    8   16   32
1|   5   10   20   40   80  160
2|  25   50  100  200  400  800
3| 125  250  500 1000 2000 ...
4| 625 1250 2500 5000 ...
j on the vertical

co musisz zrobić, to „przejść” po tej macierzy, zaczynając od (0,0). Musisz także śledzić swoje możliwe następne ruchy. Kiedy zaczynasz od, (0,0)masz tylko dwie opcje: albo (0,1)albo (1,0): ponieważ wartość (0,1)jest mniejsza, wybierasz to. następnie zrób to samo przy następnym wyborze (0,2)lub (1,0). Do tej pory, masz następującą listę: 1, 2, 4. Twój następny ruch jest (1,0)taki, że wartość jest mniejsza niż (0,3). Jednak masz teraz trzy możliwości wyboru następnego ruchu: albo (0,3), albo (1,1), albo (2,0).

Nie potrzebujesz matrycy, aby otrzymać listę, ale musisz śledzić wszystkie swoje wybory (tj. Kiedy osiągniesz 125+, będziesz miał 4 opcje).


Głosowałem za tym, ponieważ myślałem w ten sam sposób, ale w ogólnym przypadku, czy nie byłoby to coś w rodzaju O (i ^ 2 * j)? Będziesz musiał sprawdzić kilka liczb dla każdej wyświetlanej liczby.
Tom Zych

1
@Tom musisz sprawdzić więcej niż jedną liczbę, ale nie jest tak źle: kiedy wypisujesz liczby z zakresu od 125 do 625, musisz spojrzeć na 4 wartości. między 625 a 3025, patrzysz na 5 wartości. tak naprawdę, jsprawdza każde 1 wyjście
vlad

+1: Połącz z tym pytaniem: stackoverflow.com/questions/5000836/search-algorithm i wygląda na to, że mamy rozwiązanie O (n).

@Moron cholera, nie chcę płacić 25 $ za ten algorytm, ale wygląda interesująco.
vlad

1
właściwie j ~ n^0.5dla n-tej wartości w sekwencji, ponieważ nwartości wypełniają obszar na i x jpłaszczyźnie. Zatem tym algo jest O(n^1.5)czas z O(n^0.5)przestrzenią. Ale istnieje liniowy algo czasu z tą samą przestrzenią n^0.5, a algo mini-sterty z odpowiedzi poniżej to O(n*log(n))czas w tej samej n^0.5przestrzeni.
Will Ness

25

Użyj min-sterty.

Umieść 1.

wyciąg-min. Powiedz, że masz x.

Wepchnij 2x i 5x do stosu.

Powtarzać.

Zamiast przechowywać x = 2 ^ i * 5 ^ j, możesz zapisać (i, j) i użyć niestandardowej funkcji porównywania.


1
Sterta dawałaby lg n czasu na swoje operacje, co zwiększa złożoność do n lg n.
corsiKa

@glow: Tak, nie widzę do tej pory żadnych opublikowanych rozwiązań O (n) :-)

@abel: Ten komentarz jest stary :-) Wygląda na to, że on też będzie miał problemy z przejściem z (1,1) do (4,0). Ale postrzeganie tego jako macierzy Younga (patrz odpowiedź Vlad) w rzeczywistości pozwala na algorytm O (n) czasu.

@Moron: Nie sądzę, żeby było coś złego w tym rozwiązaniu. Na pewno nie ma nic złego w pierwszych 30 elementach, które właśnie sprawdziłem (to by pokryło przypadek (1,1) -> (4,0)).
abeln

@abel: Tak właściwie nie próbowałem go uruchomić :-) Może jest też łatwy dowód na jego poprawność. FWIW, ma już moje +1.

13

Rozwiązanie oparte na FIFO wymaga mniejszej pojemności. Kod Pythona.

F = [[1, 0, 0]]             # FIFO [value, i, j]
i2 = -1; n2 = n5 = None     # indices, nexts
for i in range(1000):       # print the first 1000
    last = F[-1][:]
    print "%3d. %21d = 2^%d * 5^%d" % tuple([i] + last)
    if n2 <= last: i2 += 1; n2 = F[i2][:]; n2[0] *= 2; n2[1] += 1
    if n5 <= last: i2 -= 1; n5 = F.pop(0); n5[0] *= 5; n5[2] += 1
    F.append(min(n2, n5))

wynik:

  0.                     1 = 2^0 * 5^0
  1.                     2 = 2^1 * 5^0
  2.                     4 = 2^2 * 5^0
 ...
998. 100000000000000000000 = 2^20 * 5^20
999. 102400000000000000000 = 2^27 * 5^17

6

W O(n)językach funkcjonalnych jest to bardzo łatwe . Lista lz 2^i*5^jnumerami może być po prostu zdefiniowane jako 1, a następnie 2*li 5*lpołączyły. Oto jak to wygląda w Haskell:

merge :: [Integer] -> [Integer] -> [Integer]
merge (a:as) (b:bs)   
  | a < b   = a : (merge as (b:bs))
  | a == b  = a : (merge as bs)
  | b > a   = b : (merge (a:as) bs)

xs :: [Integer]
xs = 1 : merge (map(2*)xs) (map(5*)xs)

mergeFunkcja daje nową wartość w czasie stałym. Tak robi mapi dlatego tak robi l.


Myślę, że „k” nie jest zdefiniowane
Ither

2
unionzamiast tego nazwijmy tę funkcję „merge” , ponieważ usuwa ona duplikaty. merge, jako część mergesort, musi zachować duplikaty pochodzące z obu jego sekwencji wejściowych. Zobacz Data.List.Orderedpakiet dla powiązanych rzeczy.
Will Ness,

1
+1 dla Data.List.Ordered.union. To daje jedną linię:xs = 1 : union (map (2*) xs) (map (5*) xs)
Phob,

@GaBorgulya Tak, zawiera pięć razy listę, [1, 2, 4, 5,...]więc zawiera 5*4.
Thomas Ahle,

1
@Phob Tak, to jest Data.List.Ordered.unionfunkcja. Nie należy tego mylić Data.List.union.
Thomas Ahle

5

Musisz śledzić ich poszczególne wykładniki i jakie będą ich sumy

więc zaczynasz od f(0,0) --> 1 teraz, musisz zwiększyć jeden z nich:

f(1,0) = 2
f(0,1) = 5

więc wiemy, że następna jest 2 - wiemy również, że możemy zwiększać wykładnik i aż do momentu, gdy suma przekroczy 5.

Idziesz w tę iz powrotem w ten sposób, aż osiągniesz określoną liczbę rund.


Tak to jest. Wykonujesz jedną operację O (1) w każdej rundzie. Czasami robisz rundę wcześnie, ale kiedy dojdziesz do tej rundy, nie musisz tego robić, więc wszystko działa.
corsiKa

19
Jak przechodzisz od (1,1) do (4,0)? Opisz dokładnie, jaki jest twój algorytm.

Problem polega na tym, że nie masz tylko dwóch przyrostowych możliwości - np. Nie skończyłeś f(*,2)tylko dlatego, że to znalazłeś f(a1,b+1)>f(a2,b). Podejście przyrostowe ostatecznie wygeneruje nieograniczoną liczbę par sąsiadujących z regionem, który już wygenerowałeś.
nadchodząca burza

@ user515430 dostarczył implementację, która była czymś więcej niż mogłem zrobić podczas przerwy na lunch, ale właśnie do tego próbowałem.
corsiKa

4

Używając programowania dynamicznego możesz to zrobić w O (n). Podstawowa prawda jest taka, że ​​żadne wartości i i j nie mogą dać nam 0, a aby otrzymać 1, obie wartości muszą wynosić 0;

TwoCount[1] = 0
FiveCount[1] = 0

// function returns two values i, and j
FindIJ(x) {
    if (TwoCount[x / 2]) {
        i = TwoCount[x / 2] + 1
        j = FiveCount[x / 2]
    }
    else if (FiveCount[x / 5]) {
        i = TwoCount[x / 2]
        j = FiveCount[x / 5] + 1
    }
}

Za każdym razem, gdy wywołujesz tę funkcję, sprawdź, czy i i j są ustawione, jeśli nie są puste, a następnie wypełnij TwoCountiFiveCount


Odpowiedź w C ++. Przepraszam za zły styl kodowania, ale śpieszę się :(

#include <cstdlib>
#include <iostream>
#include <vector>

int * TwoCount;
int * FiveCount;

using namespace std;

void FindIJ(int x, int &i, int &j) {
        if (x % 2 == 0 && TwoCount[x / 2] > -1) {
                cout << "There's a solution for " << (x/2) << endl;
                i = TwoCount[x / 2] + 1;
                j = FiveCount[x / 2];
        } else if (x % 5 == 0 && TwoCount[x / 5] > -1) {
                cout << "There's a solution for " << (x/5) << endl;
                i = TwoCount[x / 5];
                j = FiveCount[x / 5] + 1;
        }    
}

int main() {
        TwoCount = new int[200];
        FiveCount = new int[200];

        for (int i = 0; i < 200; ++i) {
                TwoCount[i] = -1;
                FiveCount[i] = -1;
        }

        TwoCount[1] = 0;
        FiveCount[1] = 0;

        for (int output = 2; output < 100; output++) {
                int i = -1;
                int j = -1;
                FindIJ(output, i, j);
                if (i > -1 && j > -1) {
                        cout << "2^" << i << " * " << "5^" 
                                     << j << " = " << output << endl;
                        TwoCount[output] = i;
                        FiveCount[output] = j;
                }
        }    
}

Oczywiście możesz użyć innych struktur danych niż tablica, aby dynamicznie zwiększyć pamięć itp. To jest tylko szkic, aby udowodnić, że to działa.


4
To wygląda na interesującą odpowiedź, ale nie widzę, jak to naprawdę działa. Czy mógłbyś dodać więcej szczegółów?
David Brunelle

Po przestudiowaniu tego sam, naprawdę nie wiem, jak to działa. Zakładając, że dzielenie liczb całkowitych da dokładnie taki sam wynik dla 3, jak dla 2. Ponadto, jeśli warunki if są testami na wartość niezerową, to nigdy nie zadziała, ponieważ nie ma wpisów niezerowych.
David Thornley,

Opublikowałem wersję C ++ dla wszystkich, którzy nie mówią. @David Twoje komentarze są poprawne, ale mój oryginalny kod był pseudokodem i myślałem w kategoriach skryptowych, więc dzielenie nie-całkowite i rozróżnianie między wpisem zerowym a wpisem wartości 0
Michaił

ten kod wylicza wszystkie liczby naturalne, więc na komentarz @ThomasAhle do odpowiedzi „Zagubieni w Alabamie” poniżej, potrzebne O(exp(sqrt(n)))jest utworzenie nliczb ciągu. Istnieje algorytm liniowy , np. Podany przez ThomasAhle.
Will Ness,

1
Masz rację. W moim rozumieniu O(n)oznaczało nto ostatnią wartość, a nie liczbę wydrukowanych pozycji, co nie jest poprawne. Nie wiem, jak działają języki funkcjonalne ani jak działa scalanie w ciągłym czasie, ale jego odpowiedź spotkała się z moim uprzejmością
Michaił

2

Spróbuj spojrzeć na to z innej strony. Użyj licznika, aby porównać możliwe odpowiedzi z oryginalną formułą. Przepraszamy za pseudo kod.

for x = 1 to n
{
  i=j=0
  y=x
  while ( y > 1 )
  {
    z=y
    if y divisible by 2 then increment i and divide y by 2
    if y divisible by 5 then increment j and divide y by 5

    if y=1 then print i,j & x  // done calculating for this x

    if z=y then exit while loop  // didn't divide anything this loop and this x is no good 
  }
}

To trwa mniej więcej, O(4^sqrt(n))ponieważ nthliczba sekwencji jest w przybliżeniu taka sama.
Thomas Ahle

2

To jest odpowiedni wpis w OEIS.

Wydaje się, że możliwe jest uzyskanie uporządkowanej sekwencji poprzez wygenerowanie, powiedzmy, pierwszych kilku wyrazów

1 2 4 5

a następnie, zaczynając od drugiego członu, mnożąc przez 4 i 5, aby uzyskać następne dwa

1 2 4 5 8 10

1 2 4 5 8 10 16 20

1 2 4 5 8 10 16 20 25

i tak dalej...

Intuicyjnie wydaje się to poprawne, ale oczywiście brakuje dowodu.


2
Źle :( [1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 625 ] Jednakże 500 <512 = 2 ^ 9 <625
GaBorgulya

1
@NateKerkhofs, 512 jest generowane, ale jest nieczynne, ponieważ 512 to mniej niż już wygenerowane 625; algorytm wymagałby dalszej logiki, aby uporządkować dane wyjściowe - w związku z tym algorytm nie jest tak prosty, jak proponowano i wcale nie jest tym samym algorytmem.
GordonBGood

1

Wiesz, że log_2 (5) = 2,32. Z tego zauważamy, że 2 ^ 2 <5 i 2 ^ 3> 5.

Teraz spójrz na macierz możliwych odpowiedzi:

j/i  0   1   2   3   4   5
 0   1   2   4   8  16  32
 1   5  10  20  40  80 160 
 2  25  50 100 200 400 800
 3 125 250 500 ...

Teraz, w tym przykładzie, wybierz liczby w kolejności. Tam kolejność będzie:

j/i  0   1   2   3   4   5
 0   1   2   3   5   7  10
 1   4   6   8  11  14  18
 2   9  12  15  19  23  27
 3  16  20  24...

Zauważ, że każdy wiersz zaczyna się 2 kolumny za wierszem, który go rozpoczyna. Na przykład i = 0 j = 1 występuje bezpośrednio po i = 2 j = 0.

Algorytm, który możemy wyprowadzić z tego wzorca to zatem (załóżmy j> i):

int i = 2;
int j = 5;
int k;
int m;

int space = (int)(log((float)j)/log((float)i));
for(k = 0; k < space*10; k++)
{
    for(m = 0; m < 10; m++)
    {
        int newi = k-space*m;
        if(newi < 0)
            break;
        else if(newi > 10)
            continue;
        int result = pow((float)i,newi) * pow((float)j,m);
        printf("%d^%d * %d^%d = %d\n", i, newi, j, m, result);
    }
}   

UWAGA: Kod tutaj ogranicza wartości wykładników i i j tak, aby były mniejsze niż 10. Możesz łatwo rozszerzyć ten algorytm, aby pasował do dowolnych innych dowolnych granic.

UWAGA: Czas działania tego algorytmu wynosi O (n) dla pierwszych n odpowiedzi.

UWAGA: Złożoność przestrzeni dla tego algorytmu wynosi O (1)


Napisałeś „każdy wiersz zaczyna się 2 kolumny za wierszem, który go rozpoczyna”. Jednak 2 ^ 9 = 512 i 5 ^ 4 = 625, więc nie jest to prawdą dla wiersza 4.
GaBorgulya

@ user678105 Masz rację. Ten kod nie działa. Przepraszam wszystko. Ten kod nie działa z powodu zaokrąglenia dziennika i mojego założenia, że ​​nie ma to znaczenia.
KLee1

1
Oto jak to naprawić. Na płaszczyźnie (x, y) pełnej punktów o współczynnikach całkowitych narysuj linię od (0,1) do (log2 (5), 0). (0,0) znajduje się w lewym górnym rogu. Oś X idzie w prawo, oś Y idzie w dół. Teraz narysuj linię z punktu początkowego (0,0), który jest prostopadły do ​​pierwszej linii. Teraz przesuń pierwszą linię wzdłuż drugiej, dalej i dalej od początku, i zbierz punkty o współrzędnych całkowitych, gdy zostaną skrzyżowane. Dla sekwencji wygenerowanej {2,3,5} będzie to płaszczyzna poruszająca się w poprzek, w (i, j, k) przestrzeni. Jeśli możesz przetłumaczyć ten pomysł na kod, daj mi znać. :)
Will Ness

1

Moja realizacja opiera się na następujących pomysłach:

  • Użyj dwóch kolejek Q2 i Q5, obie zainicjowane wartością 1. Obie kolejki zostaną utrzymane w posortowanej kolejności.
  • Na każdym kroku zdejmij z kolejki najmniejszy element liczbowy MIN z Q2 lub Q5 i wydrukuj go. Jeśli oba Q2 i Q5 mają ten sam element - usuń oba. Wydrukuj ten numer. Jest to po prostu scalanie dwóch posortowanych tablic - na każdym kroku wybieraj najmniejszy element i przechodź.
  • Umieść w kolejce MIN * 2 do Q2 i MIN * 5 do Q5. Ta zmiana nie przerywa niezmiennika sortowania Q2 / Q5, ponieważ MIN jest wyższe niż poprzednia liczba MIN.

Przykład:

Start with 1 and 1 (to handle i=0;j=0 case):
  Q2: 1
  Q5: 1
Dequeue 1, print it and enqueue 1*2 and 1*5:
  Q2: 2
  Q5: 5
Pick 2 and add 2*2 and 2*5:
  Q2: 4
  Q5: 5 10
Pick 4 and add 4*2 and 4*5:
  Q2: 8
  Q5: 5 10 20
....

Kod w Javie:

public void printNumbers(int n) {
    Queue<Integer> q2 = new LinkedList<Integer>();
    Queue<Integer> q5 = new LinkedList<Integer>();
    q2.add(1);
    q5.add(1);
    for (int i = 0; i < n; i++) {
        int a = q2.peek();
        int b = q5.peek();
        int min = Math.min(a, b);
        System.out.println(min);
        if (min == a) {
            q2.remove();
        }
        if (min == b) {
            q5.remove();
        }
        q2.add(min * 2);
        q5.add(min * 5);
    }
}

0

obliczyć wyniki i umieścić je na posortowanej liście wraz z wartościami iij


To prawdopodobnie da ci dziury w późniejszym końcu twojej sekwencji. Np. Będziesz miał, 2^n*5^nale nie będziesz mieć 2^(n+1)*5^(n-1)mniejszego.
Thomas Ahle,

@Thomas Nie jestem pewien, czy podążam tutaj za twoją logiką. Jeśli obliczysz jedną, dlaczego nie obliczysz również drugiej?
vlad

2
@vlad Musisz mieć ograniczenie swoich ii j, prawda? W przeciwnym razie nigdy nie przejdziesz do stanu sortowania, a zatem nigdy nie zwrócisz pojedynczej wartości. Jednak dla dowolnego wybranego limitu nlista będzie błędna.
Thomas Ahle

@Thomas Twój argument nadal nie ma sensu. OP nigdy nie określił końca swojej listy wyników. Jeśli tak, możesz znaleźć maksimum ii j.
vlad

1
@vlad Kiedy czytam Twoją odpowiedź, najpierw obliczasz „wyniki” / 2^i*5^jwartości, a następnie sortujesz je. Jeśli nie masz ograniczonej liczby „wyników”, jak kiedykolwiek dojdziesz do etapu sortowania?
Thomas Ahle

0

Algorytm zaimplementowany przez user515430 autorstwa Edsgera Dijkstry (http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF) jest prawdopodobnie tak szybki, jak to tylko możliwe. Dzwonię pod każdy numer będący formą 2^i * 5^j„numeru specjalnego”. Teraz odpowiedź vlada byłaby O(i*j)ale z podwójnym algorytmem, jeden do generowania numerów specjalnych, O(i*j)a drugi do ich sortowania (zgodnie z połączonym artykułem równieżO(i*j) .

Ale sprawdźmy algorytm Dijkstry (patrz poniżej). W tym przypadku njest to ilość generowanych przez nas liczb specjalnych, czyli równa i*j. Pętlimy się raz 1 -> niw każdej pętli wykonujemy stałą akcję. Więc ten algorytm też jestO(i*j) . A także z całkiem błyskawiczną stałą.

Moja implementacja w C ++ z GMP (opakowanie C ++) i zależność od tego boost::lexical_cast, chociaż można to łatwo usunąć (jestem leniwy i kto nie używa Boost?). Skompilowane z g++ -O3 test.cpp -lgmpxx -o test. Na Q6600 time ./test 1000000daje Ubuntu 10.10 1145ms.

#include <iostream>
#include <boost/lexical_cast.hpp>
#include <gmpxx.h>

int main(int argc, char *argv[]) {
    mpz_class m, x2, x5, *array, r;
    long n, i, i2, i5;

    if (argc < 2) return 1;

    n = boost::lexical_cast<long>(argv[1]);

    array = new mpz_class[n];
    array[0] = 1;

    x2 = 2;
    x5 = 5;
    i2 = i5 = 0;

    for (i = 1; i != n; ++i) {
        m = std::min(x2, x5);

        array[i] = m;

        if (x2 == m) {
            ++i2;
            x2 = 2 * array[i2];
        }

        if (x5 == m) {
            ++i5;
            x5 = 5 * array[i5];
        }
    }

    delete [] array;
    std::cout << m << std::endl;

    return 0;
}

0

Jeśli narysujesz macierz z i jako wierszem i j jako kolumną, zobaczysz wzór. Zacznij od i = 0, a następnie po prostu przejdź przez macierz, przechodząc o 2 wiersze w górę i 1 kolumnę w prawo, aż osiągniesz szczyt macierzy (j> = 0). Następnie idź i + 1 itd ...

Więc dla i = 7 podróżujesz w ten sposób:

7, 0 -> 5, 1 -> 3, 2 -> 1, 3

A dla i = 8:

8, 0 -> 6, 1 -> 4, 2 -> 2, 3 -> 0, 4

Tutaj jest w Javie idąc do i = 9. Wyświetla pozycję macierzy (i, j) i wartość.

for(int k = 0; k < 10; k++) {

    int j = 0;

    for(int i = k; i >= 0; i -= 2) {

        int value = (int)(Math.pow(2, i) * Math.pow(5, j));
        System.out.println(i + ", " + j + " -> " + value);
        j++;
    }
}

0

Moja intuicja :

Jeśli przyjmę wartość początkową jako 1, gdzie i = 0, j = 0, wtedy mogę utworzyć następne liczby jako (2 ^ 1) (5 ^ 0), (2 ^ 2) (5 ^ 0), (2 ^ 0) * (5 ^ 1), ... czyli 2,4,5 ..

Powiedzmy, że w dowolnym momencie moja liczba to x. następnie mogę utworzyć kolejne liczby w następujący sposób:

  • x * 2
  • x * 4
  • x * 5

Wyjaśnienie :

Since new numbers can only be the product with 2 or 5.
But 4 (pow(2,2)) is smaller than 5, and also we have to generate 
Numbers in sorted order.Therefore we will consider next numbers
be multiplied with 2,4,5.
Why we have taken x*4 ? Reason is to pace up i, such that it should not 
be greater than pace of j(which is 5 to power). It means I will 
multiply my number by 2, then by 4(since 4 < 5), and then by 5 
to get the next three numbers in sorted order.

Testowe uruchomienie

We need to take an Array-list of Integers, let say Arr.

Also put our elements in Array List<Integers> Arr.
Initially it contains Arr : [1]
  • Zacznijmy od x = 1.

    Następne trzy liczby to 1 * 2, 1 * 4, 1 * 5 [2,4,5]; Arr [1, 2, 4, 5]

  • Teraz x = 2

    Następne trzy liczby to [4,8,10] {Ponieważ 4 już wystąpiło, zignorujemy je} [8,10]; Arr [1, 2, 4, 5, 8, 10]

  • Teraz x = 4

    Następne trzy liczby [8,16,20] {8 już wystąpiły, zignoruj ​​to} [16,20] Arr [1,2,4,5,8,10,16,20]

  • x = 5

    Kolejne trzy liczby [10,20,25] {10,20} już więc [25] zostało dodane Arr [1,2,4,5,8,10,16,20,25]

Warunek zakończenia

 Terminating condition when Arr last number becomes greater 
 than (5^m1 * 2^m2), where m1,m2 are given by user.

Analiza

 Time Complexity : O(K) : where k is numbers possible between i,j=0 to 
 i=m1,j=m2.
 Space Complexity : O(K)

0

Byłem tylko ciekawy, czego się spodziewać w przyszłym tygodniu i znalazłem to pytanie.

Myślę, że idea 2 ^ i nie wzrasta w tak dużych krokach jak 5 ^ j. Więc zwiększ i, o ile następny krok j nie będzie większy.

Przykład w C ++ (Qt jest opcjonalne):

QFile f("out.txt"); //use output method of your choice here
f.open(QIODevice::WriteOnly);
QTextStream ts(&f);

int i=0;
int res=0;
for( int j=0; j<10; ++j )
{
    int powI = std::pow(2.0,i );
    int powJ = std::pow(5.0,j );
    while ( powI <= powJ  ) 
    {
        res = powI * powJ;
        if ( res<0 ) 
            break; //integer range overflow

        ts<<i<<"\t"<<j<<"\t"<<res<<"\n";
        ++i;
        powI = std::pow(2.0,i );

    }
}

Wyjście:

i   j   2^i * 5^j
0   0   1
1   1   10
2   1   20
3   2   200
4   2   400
5   3   4000
6   3   8000
7   4   80000
8   4   160000
9   4   320000
10  5   3200000
11  5   6400000
12  6   64000000
13  6   128000000
14  7   1280000000

W tym rozwiązaniu brakuje niektórych kombinacji. Na przykład, nie robi bada sprawę gdzie i = 1, j = 2 każdy przypadek, gdzie i = 1 J> 1 dla tej sprawy ..
Federico

@Federico: Masz rację! Nic dziwnego, że dwukrotnie zawiodłem wywiady w Google z 6-letnią przerwą, ale prawie te same pytania :-)
Valentin Heinitz

0

Oto moje rozwiązanie

#include <stdio.h>
#include <math.h>
#define N_VALUE 5
#define M_VALUE  5

int n_val_at_m_level[M_VALUE];

int print_lower_level_val(long double val_of_higher_level, int m_level)
{
int  n;
long double my_val;


for( n = n_val_at_m_level[m_level]; n <= N_VALUE; n++) {
    my_val =  powl(2,n) * powl(5,m_level);
    if(m_level != M_VALUE && my_val > val_of_higher_level) {
        n_val_at_m_level[m_level] = n;
        return 0;
    }
    if( m_level != 0) {
        print_lower_level_val(my_val, m_level - 1);
    }
    if(my_val < val_of_higher_level || m_level == M_VALUE) {
        printf("    %Lf n=%d m = %d\n", my_val, n, m_level);
    } else {
        n_val_at_m_level[m_level] = n;
        return 0;
    }
 }
 n_val_at_m_level[m_level] = n;
 return 0;
 }


 main()
 {
    print_lower_level_val(0, M_VALUE); /* to sort 2^n * 5^m */
 }

Wynik:

1.000000 n = 0 m = 0
2.000000 n = 1 m = 0
4.000000 n = 2 m = 0
5.000000 n = 0 m = 1
8.000000 n = 3 m = 0
10.000000 n = 1 m = 1
16.000000 n = 4 m = 0
20.000000 n = 2 m = 1
25.000000 n = 0 m = 2
32.000000 n = 5 m = 0
40.000000 n = 3 m = 1
50.000000 n = 1 m = 2
80.000000 n = 4 m = 1
100.000000 n = 2 m = 2
125.000000 n = 0 m = 3
160.000000 n = 5 m = 1
200.000000 n = 3 m = 2
250.000000 n = 1 m = 3
400.000000 n = 4 m = 2
500.000000 n = 2 m = 3
625.000000 n = 0 m = 4
800.000000 n = 5 m = 2
1000.000000 n = 3 m = 3
1250.000000 n = 1 m = 4
2000.000000 n = 4 m = 3
2500.000000 n = 2 m = 4
3125.000000 n = 0 m = 5
4000.000000 n = 5 m = 3
5000.000000 n = 3 m = 4
6250.000000 n = 1 m = 5
10000.000000 n = 4 m = 4
12500.000000 n = 2 m = 5
20000.000000 n = 5 m = 4
25000.000000 n = 3 m = 5
50000.000000 n = 4 m = 5
100000.000000 n = 5 m = 5

0

Wiem, że prawdopodobnie się mylę, ale jest tu bardzo prosta heurystyka, ponieważ nie obejmuje ona wielu liczb, takich jak 2,3,5. Wiemy, że dla każdego i, j 2 ^ i * 5 ^ j następną sekwencją będzie 2 ^ (i-2) * 5 ^ (j + 1). Będąc google q musi mieć proste rozwiązanie.

def func(i, j):
 print i, j, (2**i)*(5**j)

imax=i=2
j=0
print "i", "j", "(2**i)*(5**j)"

for k in range(20):
    func(i,j)
    j=j+1; i=i-2
    if(i<0):
        i = imax = imax+1
        j=0

Daje to wynik jako:

i j (2**i)*(5**j)
2 0 4
0 1 5
3 0 8
1 1 10
4 0 16
2 1 20
0 2 25
5 0 32
3 1 40
1 2 50
6 0 64
4 1 80
2 2 100
0 3 125
7 0 128
5 1 160
3 2 200
1 3 250
8 0 256
6 1 320

może działać do 20 lub 200, ale w pewnym momencie zacznie pomijać niektóre liczby i / lub wyświetla je w złej kolejności.
Will Ness

0

Jeśli przejdziesz przez to, co naprawdę się dzieje, gdy zwiększamy i lub j w wyrażeniu 2^i * 5^j , to albo mnożymy przez kolejne 2 lub kolejne 5. Jeśli powtórzymy problem jako - biorąc pod uwagę określoną wartość i i j, jak znaleźć następną większa wartość, rozwiązanie staje się oczywiste.

Oto zasady, które możemy dość intuicyjnie wyliczyć:

  • Jeśli i > 1w wyrażeniu występuje para 2s ( ), powinniśmy zastąpić je 5, aby otrzymać następną największą liczbę. Tak więc i -= 2i j += 1.
  • W przeciwnym razie, jeśli jest 5 ( j > 0), musimy zastąpić ją trzema 2s. Więc j -= 1i i += 3.
  • W przeciwnym razie wystarczy podać kolejne 2, aby zwiększyć wartość o minimum. i += 1.

Oto program w Rubim:

i = j = 0                                                                       
20.times do                                                                     
  puts 2**i * 5**j

  if i > 1                                                                      
    j += 1                                                                      
    i -= 2                                                                      
  elsif j > 0                                                                   
    j -= 1                                                                      
    i += 3                                                                      
  else                                                                          
    i += 1                                                                      
  end                                                                                                                                                               
end

To nie działa, ponieważ „i” nigdy nie jest większe niż 4, więc wielokrotności 32 (2 ^ 5) nigdy się nie pojawią.
threenplusone

0

Jeśli możemy korzystać z kolekcji java, możemy mieć te liczby w O (n ^ 2)

public static void main(String[] args) throws Exception {
    int powerLimit = 7;  
     int first = 2;
     int second = 5;
    SortedSet<Integer> set = new TreeSet<Integer>();

    for (int i = 0; i < powerLimit; i++) {
        for (int j = 0; j < powerLimit; j++) {
            Integer x = (int) (Math.pow(first, i) * Math.pow(second, j));
            set.add(x);
        }
    }

    set=set.headSet((int)Math.pow(first, powerLimit));

    for (int p : set)
        System.out.println(p);
}

Tutaj powerLimit musi zostać zainicjowany bardzo ostrożnie !! W zależności od tego, ile liczb chcesz.


daje to błędne wyniki: brak 2 ^ 8 = 256 przed 2 ^ 6 * 5 = 320. obszar wyliczenia jest trójkątny, a nie prostokątny.
Will Ness,

@WillNess How ?? Kiedy ustawiam powerLimit = 9, ten fragment kodu zwraca następujące liczby 1 2 4 5 8 10 16 20 25 32 40 50 64
80100125128160200250256320400500

nie, daje 100 liczb. skąd wiesz, gdzie się zatrzymać? musisz to wyjaśnić. --- Odniosłem się do 7 jako obecnego we fragmencie kodu. aby była to prawidłowa odpowiedź, musisz dokładnie wyjaśnić, jak ustawić limit dla danej liczby liczb i ile liczb będzie to nadprodukować .
Will Ness,

0

Oto moja próba ze Scalą:

case class IndexValue(twosIndex: Int, fivesIndex: Int)
case class OutputValues(twos: Int, fives: Int, value: Int) {
  def test(): Boolean = {
    Math.pow(2,  twos) * Math.pow(5, fives) == value
  }
}

def run(last: IndexValue = IndexValue(0, 0), list: List[OutputValues] = List(OutputValues(0, 0, 1))): List[OutputValues] = {
  if (list.size > 20) {
    return list
  }

  val twosValue = list(last.twosIndex).value * 2
  val fivesValue = list(last.fivesIndex).value * 5

  if (twosValue == fivesValue) {
    val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex + 1)
    val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.fivesIndex).fives + 1)
    run(lastIndex, list :+ outputValues)
  } else if (twosValue < fivesValue) {
    val lastIndex = IndexValue(last.twosIndex + 1, last.fivesIndex)
    val outputValues = OutputValues(value = twosValue, twos = list(last.twosIndex).twos + 1, fives = list(last.twosIndex).fives)
    run(lastIndex, list :+ outputValues)
  } else {
    val lastIndex = IndexValue(last.twosIndex, last.fivesIndex + 1)
    val outputValues = OutputValues(value = fivesValue, twos = list(last.fivesIndex).twos, fives = list(last.fivesIndex).fives + 1)
    run(lastIndex, list :+ outputValues)
  }
}

val initialIndex = IndexValue(0, 0)
run(initialIndex, List(OutputValues(0, 0, 1))) foreach println

Wynik:

OutputValues(0,0,1)
OutputValues(1,0,2)
OutputValues(2,0,4)
OutputValues(0,1,5)
OutputValues(3,0,8)
OutputValues(1,1,10)
OutputValues(4,0,16)
OutputValues(2,1,20)
OutputValues(0,2,25)
OutputValues(5,0,32)
OutputValues(3,1,40)
OutputValues(1,2,50)
OutputValues(6,0,64)
OutputValues(4,1,80)
OutputValues(2,2,100)
OutputValues(0,3,125)
OutputValues(7,0,128)
OutputValues(5,1,160)
OutputValues(3,2,200)
OutputValues(1,3,250)
OutputValues(8,0,256)
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.