एल्गोरिथ्म दो चर

Question

के साथ एकल सरल समीकरण का समाधान सेट गणना करने के लिए मैं प्रपत्र का एक सरल समीकरण है मान लीजिए। यह एकमात्र समीकरण है जो हमें दिया जाता है। संभावित समाधानों में हमें समाधान (एक्स, वाई) की आवश्यकता है जिसमें एक्स सबसे छोटा है। जैसे

7x + 4y = 14, then (2, 0) is the solution 
7x + 4y = 15, then (1, 2) is the solution 
7x + 4y = 32, then (4, 1) and (0, 8) are the possible solutions, 
of which (0, 8) is the correct solution 

मैं कम से कम संभव समय में इसे गणना करने के लिए एक एल्गोरिदम तैयार करना चाहता हूं। वर्तमान एल्गोरिथ्म जो मैं मन में है कुछ इस तरह चला जाता है:

Given an input n 
Calculate max(x) = n/7 
for i = 0 to max(x) 
    If the equation 7*i + 4*y = n holds 
     return value of i and y 
    else 
     continue 

इस एल्गोरिथ्म, मुझे लगता है, सबसे ज्यादा मामले व्यवहार में तक हे (एन) के एक चलने का समय हो सकता है। क्या समाधान की गणना करने के लिए कुछ बेहतर एल्गोरिदम है?

Answer 1

हमें अधिक सामान्य समस्या

• दो coprime धनात्मक पूर्णांक a और b के लिए विचार करना एक सकारात्मक पूर्णांक n दिया, जैसे कि a*x + b*y = n न्यूनतम x साथ गैर नकारात्मक पूर्णांकों की जोड़ी (x,y) खोजते हैं। किसी भी समाधान

  a*x0 + b*y0 = n 
  

  सभी समाधान दिया (यदि वहाँ एक है। वहाँ होने की ज़रूरत नहीं है, जैसे 7*x + 4*y = 5 गैर नकारात्मक x और y साथ कोई हल नहीं है।)

पल के लिए nonnegativity की अनदेखी, कुछ पूर्णांक k के लिए फॉर्म (x0 - k*b, y0 + k*a) है। तो x सापेक्ष b के शेष और y सापेक्ष a के समाधान की एक अपरिवर्तनीय है, और हम

a*x ≡ n (mod b), and b*y ≡ n (mod a) 

तो हम समीकरण a*x ≡ n (mod b) का समाधान करने की जरूरत है - एक दूसरे को इस प्रकार है।

0 < ca*c ≡ 1 (mod b) के साथ एक पूर्णांक बनें।आप इसे विस्तारित यूक्लिडियन एल्गोरिदम, या (समतुल्य) ओ 0 (लॉग बी) चरणों में a/b के निरंतर अंश विस्तार द्वारा उदाहरण के लिए पाते हैं। दोनों एल्गोरिदम प्राकृतिक रूप से उस संपत्ति के साथ अद्वितीय c < b उत्पन्न करते हैं।

फिर x के लिए न्यूनतम उम्मीदवार n*c मॉड्यूल b का शेष x0 है।

समस्या गैर नकारात्मक x और y तभी x0*a <= n अगर साथ एक समाधान है, और फिर x0 न्यूनतम गैर नकारात्मक x nonnegtaive x और y के साथ किसी भी समाधान में प्रदर्शित होने के लिए है।

बेशक

, छोटे a और b 7 और 4 तरह के लिए, जानवर बल नहीं a सापेक्ष b का प्रतिलोम की गणना की तुलना में धीमी है।

Answer 2

हम

7(x-4)+4(y+7)=7x+4y 

तो अगर (एक्स, वाई) एक समाधान है, तो है (एक्स -4, y + 7) भी एक समाधान है। इसलिए यदि कोई समाधान है तो x < 4 के साथ एक है। यही कारण है कि आपको केवल x = 0..3 का परीक्षण करने की आवश्यकता है जो निरंतर समय में चलता है।

इसे फ़ॉर्म कुल्हाड़ी + द्वारा = n के किसी भी समीकरण तक बढ़ाया जा सकता है, आपको केवल x = 0..b-1 का परीक्षण करने की आवश्यकता है।

Answer 3

हे (एन):

y=n/4; 
while((n-4y)%7!=0 && y!=0){ 
y--; 
} 
x=(n-4y)/7; 

Answer 4

मैं Numerical Recipes in C पुस्तक में सिंप्लेक्स विधि बाहर की जाँच की सिफारिश करेंगे। आप आसानी से सी कोड जैसे छद्म कोड का इलाज कर सकते हैं और जावा संस्करण बना सकते हैं। आपके द्वारा इच्छित सरलता का संस्करण "बाधित-सरल" है जो केवल सकारात्मक मानों में कार्य करता है। पुस्तक available online for free है। सेक्शन 10.8 के साथ शुरू करें और आगे पढ़ें।