जब से मैंने प्रोग्रामिंग शुरू की है, तब से कुछ ऐसा है जो मैं उत्सुक हूं। लेकिन मेरे लिए प्रयास करने के लिए मेरे लिए बहुत जटिल लगता है।अनुक्रम में अगली संख्या को खोजने के लिए एल्गोरिदम
मुझे एक समाधान देखना अच्छा लगेगा।
1, 2, 3, 4, 5 // returns 6 (n + 1)
10, 20, 30, 40, 50 //returns 60 (n + 10)
10, 17, 31, 59, 115 //returns 227 ((n * 2) - 3)
आप जो करना चाहते हैं उसे बहुपद इंटरपोलेशन कहा जाता है। कई विधियां हैं (http://en.wikipedia.org/wiki/Polynomial_interpolation देखें), लेकिन बहुपद की डिग्री और कम से कम यू + 1 मानों पर आपको ऊपरी बाध्य यू होना चाहिए।
यदि आपके पास अनुक्रमिक मान हैं, तो एक सरल एल्गोरिदम है।
अनुक्रम x1, x2, x3, ... को देखते हुए, डेल्टा (x) अंतर x2 - x1, x3 - x2, x4 - x3, ... के अनुक्रम होने दें। यदि आपके पास डिग्री एन बहुपद के लगातार मूल्य हैं, तो डेल्टा का nth पुनरावृत्ति निरंतर अनुक्रम है।
उदाहरण के लिए, बहुपद n^3:
1, 8, 27, 64, 125, 216, ...
7, 19, 37, 61, 91, ...
12, 18, 24, 30, ...
6, 6, 6, ...
अगले मूल्य मिलता है, एक और 6 भरें और फिर पीछे की ओर काम करने के लिए।
6, 6, 6, 6 = 6, ...
12, 18, 24, 30, 36 = 30 + 6, ...
7, 19, 37, 61, 91, 127 = 91 + 36, ...
1, 8, 27, 64, 125, 216, 343 = 216 + 127, ...
उपरोक्त मानों की संख्या पर प्रतिबंध यह सुनिश्चित करता है कि मतभेद करते समय आपका अनुक्रम खाली न हो जाए।
हां, यह वास्तव में बैबेज अंतर इंजन का आधार है। यह पता लगाएं कि एनएच व्युत्पन्न एक स्थिर है, और बस अतिरिक्त आपको अगली संख्या देता है। – EvilTeach
क्षमा निराश है, लेकिन यह काफी संभव नहीं है (सामान्य रूप में), के रूप में वहाँ किसी भी k मूल्यों के लिए दृश्यों की एक अनंत संख्या में हैं। शायद कुछ बाधाओं के साथ ..
आप इस Everything2 पोस्ट पर एक नज़र डाल सकते हैं, जो Lagrange polynomial पर इंगित करता है।
हां बहुत सारी संभावनाएं हो सकती हैं, लेकिन क्या आपको केवल वह नहीं मिला जो दिए गए सरणी के लिए काम करता है और इसका उपयोग करता है? यह हर संभव संभावना को कवर करने की आवश्यकता नहीं है। क्या इसका कोई मतलब है? –
समस्या यह है कि अगली संख्या सचमुच कुछ भी हो सकती है, और आप उस नए पैटर्न को फिट करने के लिए पैटर्न/बहुपद को समझ सकते हैं। उदाहरण के लिए, एक पैटर्न है जो फिट बैठता है, 1, 2, 3, 4, 5, 6, लेकिन 1, 2, 3, 4, 5, 5, 5, 5, 5, 5 .. – Larry
लेकिन मेरा मतलब है कि बस उन 5 संख्याओं को फिट करने के लिए एक सूत्र, फिर 6 वें प्राप्त करने के लिए इसका उपयोग करें। –
मुझे विचार और अनुक्रम पसंद है एक और दो मुझे लगता है कि यह संभव है, लेकिन फिर आप सामान्यीकृत नहीं कर सकते क्योंकि अनुक्रम आधार से पूरी तरह से बंद हो सकता है। जवाब शायद यह है कि आप सामान्यीकृत नहीं कर सकते हैं, आप क्या कर सकते हैं एक विशिष्ट अनुक्रम (एन + 1) या (2 एन + 2) आदि जानने के लिए एक एल्गोरिदम लिखना है ...
एक चीज जो आप कर सकते हैं तत्व I और तत्व i + 1 और तत्व i + 2 के बीच एक अंतर लेता है।
उदाहरण के लिए, अपने तीसरे उदाहरण में:
10 17 31 59 115
अंतर 17 के बीच और 10 7 है, और 31 और 17 के बीच का अंतर 14 है, और 59 और 31 के बीच का अंतर 28 है, और diffeerence 115 और 59 के बीच 56 है।
तो आप ध्यान दें कि यह तत्व I + 1 = i + (7 * 2^n) तत्व बन गया है।
तो 17 = 10 + (7 * 2^0)
और 31 = 17 + (7 * 2^1)
और इसी तरह ...
आप कोशिश कर सकते हैं करने के लिए extrapolation का उपयोग करें। यह आपको दिए गए अनुक्रम का वर्णन करने के लिए सूत्र ढूंढने में मदद करेगा।
मुझे खेद है, मैं आपको और अधिक नहीं बता सकता, क्योंकि मेरी गणित शिक्षा थोड़ी देर पहले हुई थी। लेकिन आपको अच्छी किताबों में और जानकारी मिलनी चाहिए।
इस तरह की संख्या श्रृंखला अक्सर "खुफिया परीक्षण" का हिस्सा होती है, जो मुझे Turing Test से गुज़रने वाले कुछ एल्गोरिदम की शर्तों में सोचने के लिए प्रेरित करती है, जो कुछ हासिल करने में काफी मुश्किल है।
औपचारिक रूप से आंशिक अनुक्रम के लिए कोई अद्वितीय अगला मूल्य नहीं है।
मान लें कि आंशिक प्रदर्शित अनुक्रम, कुछ पैदा नियम विवश सरल संभव नियम निकालना और उत्पन्न अगले मूल्य प्रदर्शन करने के लिए बस के लिए पर्याप्त है: के रूप में समस्या के रूप में आम तौर पर समझ में आ स्पष्ट रूप से कहा जा सकता है।
समस्या "सरलतम" के अर्थ को चालू करती है, और इस प्रकार एल्गोरिदमिक समाधानों के लिए वास्तव में अच्छा नहीं है। यह किया जा सकता है यदि आप समस्या को उत्पन्न करने के लिए कार्यात्मक रूपों के एक निश्चित वर्ग में समस्या को सीमित करते हैं, लेकिन विवरण इस बात पर निर्भर करते हैं कि आप किस रूप में स्वीकार करना चाहते हैं।
पुस्तक Numerical Recipes में इस तरह की चीजें करने के लिए वास्तविक व्यावहारिक एल्गोरिदम के पृष्ठ और पृष्ठ हैं। यह पढ़ने के लायक है!
पहले दो मामलोंआसान कर रहे हैं:
>>> seq1 = [1, 2, 3, 4, 5]
>>> seq2 = [10, 20, 30, 40, 50]
>>> def next(seq):
... m = (seq[1] - seq[0])/(1-0)
... b = seq[0] - m * 0
... return m*len(seq) + b
>>> next(seq1)
6
>>> next(seq2)
60
तीसरे मामले एक गैर रेखीय समारोह के लिए सुलझाने की आवश्यकता होगी।
मनमाने ढंग से कार्य करने के लिए यह नहीं किया जा सकता है, लेकिन आपके प्रत्येक उदाहरण में रैखिक कार्य के लिए यह काफी आसान है।
आपके पास f(n+1) = a*f(n) + b है, और समस्या a और b खोजने के लिए है।
अनुक्रम के कम से कम तीन शर्तों को देखते हुए, आप यह कर सकते हैं (आपको तीन की आवश्यकता है क्योंकि आपके पास तीन अज्ञात हैं - शुरुआती बिंदु, a, और b)। उदाहरण के लिए, मान लें कि आपके पास f(0), f(1) और f(2) है।
हम समीकरणों को हल कर सकते हैं:
f(1) = a*f(0) + b
f(2) = a*f(1) + b
के लिए समाधान है: (। आप अलग से इस मामले में जहां f(0) = f(1) शून्य से भाग से बचने के लिए हल करने के लिए चाहता हूँ)
a = (f(2)-f(1))/(f(1)-f(0))
b = f(1) - f(0)*(f(2)-f(1))/(f(1)-f(0))
एक बार आपके पास a और b हो, तो आप बार-बार किसी भी शब्द को उत्पन्न करने के लिए अपने प्रारंभिक मूल्य पर सूत्र लागू कर सकते हैं quence।
कोई भी एक सामान्य प्रक्रिया लिख सकता है जो किसी भी अनुक्रम में तीन अंक (जैसे चौथा, 7 वां, 23 वां, या जो कुछ भी) दिया जाता है। । । यह सिर्फ एक साधारण उदाहरण है।
फिर भी, हमें कुछ समाधान करना पड़ा कि हमारे समाधान के रूप में क्या होगा। । ।इस मामले में इसे आपके उदाहरण के रूप में रैखिक माना जाता है। उदाहरण के लिए, इसे अधिक सामान्य बहुपद माना जा सकता है, लेकिन उस स्थिति में आपको बहुपद की डिग्री के आधार पर समाधान खोजने के लिए अनुक्रम की अधिक शर्तों की आवश्यकता होती है।
भी देखें अध्याय किताब से "किस स्थान से एक अनुक्रम आता शोध करने के लिए": डगलस होफस्टैड्टर द्वारा
खैर पहले दो "द्रव अवधारणाओं और रचनात्मक उपमा सोचा था की मौलिक तंत्र के कंप्यूटर मॉडल" आसान हैं लेकिन सामान्यीकरण कैसे करें? – JonH
मुझे लगता है कि दूसरी पंक्ति 60 लौटती है ... –
हाँ, मॉरीज़ियो धन्यवाद। याद किया कि। : पी –