Algoritmo per trovare il valore elemento della sequenza

Question

V'è la seguente sequenza:

101001000100001 ...

Come definire un metodo che prende indice di un elemento della sequenza e restituisce il valore (0 o 1) di questo elemento?

public Element getValue(int index) {} 

Forse c'è bisogno di usare la ricorsione ? Sarei grato per qualsiasi idea!

Answer 1

Piccoli punti indicano che questa serie andrà avanti. Quindi ecco la soluzione:

Consideriamo 1 indice basato. Noti che 1 si verifica all'indice 1, (1 + 2) = 3, (1 + 2 + 3) = 6, (1 + 2 + 3 + 4) = 10 ecc. Abbiamo una formula per questo. È n * (n + 1)/2.

Così, per data indice (ora questo è 0 basa come matrice java inizia in corrispondenza dell'indice 0) effettuare le seguenti operazioni:

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; 

Inoltre non v'è alcuna necessità di ricorsione in quanto questo è O (1) soluzione (non considerando la complessità della funzione radice quadrata)

Answer 2

Ritorno 1 se index + 1 è un triangular number. x è triangolare, se e solo se 8x + 1 è un quadrato. Quindi indice + 1 è triangolare, se e oly se 8 * indice + 9 è un quadrato.

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