एल्गोरिथ्म अनुक्रम का तत्व मूल्य खोजने के लिए

Question

निम्नलिखित अनुक्रम है:

101001000100001 ...

कैसे एक विधि है कि अनुक्रम का एक तत्व के सूचकांक लेता है और रिटर्न परिभाषित करने के लिए इस तत्व का मूल्य (0 या 1)?

public Element getValue(int index) {} 

हो सकता है कि वहाँ प्रत्यावर्तन उपयोग करने की आवश्यकता है? मैं किसी भी विचार के लिए आभारी होंगे!

Answer 1

छोटे बिंदुओं से संकेत मिलता है कि यह श्रृंखला जारी रहेगी। तो यहां आपका समाधान है:

आइए 1 आधारित इंडेक्स पर विचार करें। आप देखते हैं कि 1 सूचकांक 1, (1 + 2) = 3, (1 + 2 + 3) = 6, (1 + 2 + 3 + 4) = 10 आदि पर होता है। हमारे पास इसके लिए एक सूत्र है। इसका एन * (एन + 1)/2।

दिए गए इंडेक्स के लिए

तो (अब इस 0 जावा सरणी के रूप में आधारित है सूचकांक 0 में शुरू होता है) निम्न कार्य करें:

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; 

इसके अलावा प्रत्यावर्तन की कोई जरूरत इस हे (1) समाधान (नहीं है के रूप में वहाँ है वर्ग रूट फ़ंक्शन की जटिलता पर विचार करते हुए)

Answer 2

1index + 1triangular number है। एक्स त्रिभुज है, अगर और केवल 8x + 1 एक वर्ग है। तो इंडेक्स + 1 त्रिकोणीय है, अगर 8 और इंडेक्स + 9 एक वर्ग है तो ओली और ओली।

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