Thuật toán tìm giá trị phần tử của dãy

Question

Có trình tự sau đây:

101001000100001 ...

Làm thế nào để xác định một phương pháp mà phải mất một phần tử index của chuỗi và trả về giá trị (0 hoặc 1) của phần tử này?

public Element getValue(int index) {} 

Có thể cần phải sử dụng đệ quy? Tôi sẽ biết ơn đối với bất kỳ ý tưởng nào!

Answer 1

Dấu chấm nhỏ cho biết chuỗi này sẽ tiếp tục. Vì vậy, đây là giải pháp của bạn:

Cho phép xem xét chỉ mục dựa trên 1. Bạn nhận thấy rằng 1 xảy ra tại chỉ số 1, (1 + 2) = 3, (1 + 2 + 3) = 6, (1 + 2 + 3 + 4) = 10 v.v. Chúng ta có một công thức cho việc này. N * (n + 1)/2 của nó.

Vì vậy, cho chỉ số nhất định (bây giờ điều này là 0 dựa như mảng java bắt đầu từ chỉ số 0) làm như sau:

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; 

Cũng không có nhu cầu về đệ quy như thế này là O (1) giải pháp (không xem xét sự phức tạp của chức năng gốc hình vuông)

Answer 2

Trả lại 1 nếu index + 1 là triangular number. x là hình tam giác, nếu và chỉ khi 8x + 1 là hình vuông. Vì vậy, chỉ số + 1 là hình tam giác, nếu và oly nếu 8 * index + 9 là một hình vuông.

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