Algorytm znaleźć wartość elementu sekwencji

Question

Nie ma następującą sekwencję:

101001000100001 ...

Jak zdefiniować metodę, która zajmuje elementu indeks sekwencji i zwraca wartość (0 lub 1) tego elementu?

public Element getValue(int index) {} 

Może nie trzeba używać rekursji? Byłbym wdzięczny za wszelkie pomysły!

Answer 1

Małe kropki wskazują, że seria będzie kontynuowana. Oto twoje rozwiązanie:

Rozważmy 1 oparty indeks. Zauważasz, że 1 występuje w indeksie 1, (1 + 2) = 3, (1 + 2 + 3) = 6, (1 + 2 + 3 + 4) = 10 itd. Mamy na to formułę. Jego n * (n + 1)/2.

Więc dla danego indeksu (obecnie jest to 0 oparciu jako tablicy java zaczyna się w indeksie 0) wykonaj następujące czynności:

index = index + 1; // now it is 1 based index and our formula would fit in nicely. 
index = index * 2; 
sqroot = integer part of square root of index; 
if(sqroot * (sqroot+1) == index) 
    print 1; 
else 
    print 0; 

Również nie ma potrzeby rekursji jest to O (1) rozwiązanie (nie biorąc pod uwagę złożoność funkcji pierwiastka kwadratowego)

Answer 2

Powrót 1 jeśli index + 1 jest triangular number. x jest trójkątne, wtedy i tylko wtedy, gdy 8x + 1 jest kwadratem. Zatem indeks + 1 jest trójkątny, jeśli i oly, jeśli 8 * index + 9 jest kwadratem.

public int getValue(int index) { 
    int i = (int)Math.round(Math.sqrt(8*index + 9)); 
    if (i*i == 8*index+9) 
     return 1; 
    else 
     return 0; 
} 

http://ideone.com/8L9A96