एक रैखिक डायफोंटाइन समीकरण को हल करना (उदाहरणों के लिए विवरण देखें)

Question

मुझे यह स्पष्ट करके बताएं कि (इससे पहले कि आप मुझे बर्खास्त कर दें), यह होमवर्क समस्या नहीं है और मैं विश्वविद्यालय का छात्र नहीं हूं। :)

संपादित @Klas और दूसरों के लिए धन्यवाद, मेरे सवाल का अब नीचे एक गणितीय समीकरण जो प्रोग्राम के रूप में हल किया जा करने की जरूरत है के लिए निर्भर करता है।

मैं एक एल्गोरिदम/कोड ढूंढ रहा हूं जो Linear Diophantine Equation हल करता है। मेरे जैसे कम मनुष्यों के लिए, यहाँ कैसे इस तरह के एक समीकरण की तरह लग रहा है:

उदाहरण 1: 3x + 4y + 5z = 25

उदाहरण 2 (एक्स, वाई, जेड के सभी संभव मूल्यों को खोजने): 10p + 5q + 6r + 11s = 224 (पी के सभी संभव मूल्यों को खोजने , क्यू, आर, रों)

उदाहरण 3: 8p + 9q + 10r + 11s + 12t = 1012 (पी, क्यू, आर, एस, टी के सभी संभव मूल्यों को खोजने)

मैं कोई लाभ नहीं हुआ googling की कोशिश की। मैंने सोचा होगा कि कुछ हल करने के लिए कुछ कोड पहले से ही लिखा जाएगा। अगर आप किसी तरह की लाइब्रेरी में आए हैं जो मुझे पहले ही लागू कर चुका है तो मुझे बताएं। और यदि समाधान जावा में है, तो कुछ भी कूलर नहीं हो सकता है! एल्गोरिदम/छद्म कोड भी करेगा। बहुत धन्यवाद।

Answer 1

ब्रूट-फोर्स रिकर्सन एक विकल्प है, इस पर निर्भर करता है कि आप मूल्य या मूल्यों की संख्या कितनी बड़ी हो जाएंगे।

मानदंड: उपयोगकर्ता इनपुट (गुणक) हमेशा सकारात्मक सकारात्मक पूर्णांक होते हैं। गुणांक पाए जाने वाले गैर-ऋणात्मक पूर्णांक होना चाहिए।

एल्गोरिथ्म:

Of the multiplicands, let M be the largest. 
Calculate C=floor(F/M). 
If F=M*C, output solution of the form (0,0,...,C) and decrement C 
If M is the only multiplicand, terminate processing 
Loop from C down to 0 (call that value i) 
    Let F' = F - i*M 
    Recursively invoke this algorithm: 
    The multiplicands will be the current set minus M 
    The goal value will be F' 
    For each solution output by the recursive call: 
    append i to the coefficient list and output the solution 

Answer 2

यह एक प्रोग्रामिंग के बजाय गणितीय प्रश्न है। एक बार आपके पास उपयुक्त एल्गोरिदम हो जाने के बाद, इसे लागू करना बहुत मुश्किल नहीं होना चाहिए।

मैं आपको डायफोंटाइन समीकरणों पर Google का सुझाव देता हूं।

मुझे आपके लिए explanation मिला।

Answer 3

Klas 'बहुत ही सटीक जवाब देने के लिए पर जोड़ना:

हिल्बर्ट की 10 वीं समस्या से पूछा कि क्या एक एल्गोरिथ्म का निर्धारण एक मनमाना Diophantine समीकरण एक समाधान है कि क्या के लिए अस्तित्व में। इस तरह के एक एल्गोरिदम पहले क्रम डायफोंटाइन समीकरणों के समाधान के लिए मौजूद है। हालांकि, एक सामान्य समाधान प्राप्त करने की असंभव 1970

में यूरी मटियसेविच द्वारा सिद्ध किया गया था से लिया: Wolfram MathWorld

Answer 4

एक जानवर बल एल्गोरिथ्म के रूप में (3 चर मामले) इस प्रकार है:

int sum = 25; 
int a1 = 3; 
int a2 = 4; 
int a3 = 5; 
for (int i = 0; i * a1 <= sum; i++) { 
    for (int j = 0; i * a1 + j * a2 <= sum; j++) { 
     for (int k = 0; i * a1 + j * a2 + k * a3 <= sum; k++) { 
      if (i * a1 + j * a2 + k * a3 == sum) { 
       System.out.println(i + "," + j + "," + k); 
      } 
     } 
    } 
} 

एन परिवर्तनीय मामले के लिए इसे सामान्यीकृत करने के लिए, आपको एक पुनरावर्ती रूप में रूपांतरित करने की आवश्यकता है।

यह एल्गोरिदम f कुछ फ़ंक्शन के लिए O(f(size, a)^N) है।

• हम f पर सीमाएं निम्नानुसार रख सकते हैं: size/MaxValue(a) <= f(size, a) <= size/MinValue(a)।
• सबसे बुरे मामले में (जहां a[i] के सभी 1 हैं) f(size, a)size है।

किसी भी तरह से, N के बड़े मूल्यों के लिए यह बहुत डरावना है। तो जबकि रिकर्सिव एन वेरिएबल एल्गोरिदम अधिक सुरुचिपूर्ण होगा, यह शायद बहुत व्यावहारिक नहीं है।

---

आप स्प्रिंगर वेरलाग 34 यूरो के बाहर कांटा करने को तैयार हैं, तो यहां a link to a paper जो (सार के अनुसार) एन चर मामले को सुलझाने के लिए एक एल्गोरिथ्म शामिल है।

Answer 5

ऐसा कोई कारण नहीं है कि ऐसा कोई लाइब्रेरी क्यों न हो, यह आपको समानता के लिए लाइब्रेरी क्यों नहीं मिलेगी - आप इतना डेटा उत्पन्न करते हैं कि यह संभवतः गलत काम है।

अधिक सटीक, यदि आपके पास n वेरिएबल्स हैं जिनका योग X है, तो आपके पास O(Xn-1) उत्तर होंगे। X और n इस मुद्दे के लिए बहुत बड़ा होने की आवश्यकता नहीं है।

कहा, यहाँ कुछ अजगर कि काफी कुशलता से आवश्यक जानकारी के सभी का पता लगा लेता जवाब एन्कोड करने के लिए है:

def solve_linear_diophantine (*coeff_tuple): 
    coeff = list(coeff_tuple) 
    constant = coeff.pop() 

    cached = [] 
    for i in range(len(coeff)): 
     # Add another cache. 
     cached.append({}) 

    def solve_final (i, remaining_constant): 
     if remaining_constant in cached[i]: 
      return cached[i][remaining_constant] 
     answer = [] 
     if i+1 == len(coeff): 
      if 0 == remaining_constant%coeff[i]: 
       answer = [(remaining_constant/coeff[i], [])] 
     else: 
      for j in range(remaining_constant/coeff[i] + 1): 
       finish = solve_final(i+1, remaining_constant - j*coeff[i]) 
       if finish is not None: 
        answer.append((j, finish)) 
     if 0 == len(answer): 
      cached[i][remaining_constant] = None 
      return None 
     else: 
      cached[i][remaining_constant] = answer 
      return answer 

    return solve_final(0, constant) 

जब मैं कहता हूँ "एनकोड", डेटा संरचना इस तरह दिखता है। प्रत्येक संभावित गुणांक के लिए, हमें (coefficient, [subanswers]) की एक सरणी मिल जाएगी। जब भी संभव हो तो डेटा संरचना को यथासंभव छोटा बनाने के लिए उपनगरों का पुन: उपयोग किया जाता है। यदि आप नहीं कर सकते हैं तो आप इसे पीछे की ओर जवाबों की सरणी में विस्तारित कर सकते हैं, और ऐसा करने में आप बहुत कुशल होंगे। (वास्तव में यह O(nX) है।) आप एक ही तथ्य को बार-बार खोजने के लिए तर्क की बहुत कम दोहराएंगे। (हालांकि लौटाई गई सूची बहुत बड़ी हो सकती है क्योंकि लौटने के उत्तरों की एक बड़ी सूची है।)

Answer 6

या तो कोई, या असीमित कई समाधान हैं। अक्सर यह मामला होता है कि आपके पास अतिरिक्त बाधा है कि समाधान का मिलान होना चाहिए। क्या यह आपकी समस्या में मामला है?

के सबसे सरल स्थिति है जहाँ दो unkowns a*x + b*y = c देखते हैं साथ शुरू करते हैं:

पहला कदम Euclidean algorithm उपयोग कर रहा है a और b की GCD लगता है, चलो यह d फोन करते हैं। बोनस के रूप में, एल्गोरिदम x' और y' प्रदान करता है जैसे कि a*x' + b*y' = d। यदि dc को विभाजित नहीं करता है, तो कोई समाधान नहीं है। अन्यथा, एक समाधान है:

x = x' * (c/d) 
y = y' * (c/d) 

दूसरे चरण के लिए सभी समाधान खोजने के लिए है। इसका मतलब है कि हमें सभी p और q जैसे a*p + b*q = 0 मिलना चाहिए।के लिए अगर दोनों (x,y) और (X, Y), समाधान कर रहे हैं तो

a * (X-x) + b * (Y-y) = 0 

इसका जवाब p = b/d और q = -a/d जहां d = GCD(a,b) है और पहले से ही चरण 1 में गणना की जाती है सामान्य समाधान है:

x = x' * (c/d) + n * (b/d) 
y = y' * (c/d) - n * (a/d) 

जहां n एक पूर्णांक है।

पहला चरण कई चरों तक विस्तार करना आसान है। मैं दूसरे चरण को सामान्यीकृत करने के बारे में निश्चित नहीं हूं। मेरा पहला अनुमान गुणांक के सभी जोड़े के लिए समाधान ढूंढना और इन समाधानों को जोड़ना होगा।

Answer 7

मुझे इसके लिए जावा कोड लिखना पड़ा। कृपया अपनी सहायता स्वयं करें। समाधानों का व्यापक परीक्षण नहीं किया जाता है, लेकिन ऐसा लगता है कि अब तक अच्छी तरह से काम कर रहा है।

package expt.qp; 

import java.util.HashMap; 
import java.util.LinkedHashMap; 
import java.util.Map; 

public class LinearDiophantine { 

    private Map<Integer, Integer> sol = new LinkedHashMap<Integer, Integer>(); 
    private Map<Integer, Integer> coeff = new HashMap<Integer, Integer>(); 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     // Fill up the data 
     // 3x + 4y + 5z + 3a = 25 
     LinearDiophantine ld = new LinearDiophantine(); 
     ld.coeff.put(1, 1);ld.coeff.put(2, 2);ld.coeff.put(3, 3);ld.coeff.put(4, 4); 
     Map<Integer, Integer> coeffCopy = new HashMap<Integer, Integer>(ld.coeff); 
     int total=30; 

     // Real algo begins here 
     ld.findPossibleSolutions(total, coeffCopy); 

    } 

    private void findPossibleSolutions(int total, Map<Integer, Integer> coeff) { 
     int index=returnLargestIndex(coeff); 
     int range = (int) Math.floor(total/coeff.get(index)); 
     if(range*coeff.get(index) == total) { 
      sol.put(index, range); 
      displaySolution(); 
      //System.out.println(); 
      range--; 
     } 
     if(coeff.size() == 1) { 
      return; 
     } 
     while(range>=0) { 
      int remTotal = total - range*coeff.get(index); 
      Map<Integer, Integer> coeffCopy = new HashMap<Integer, Integer>(coeff); 
      coeffCopy.remove(index); 
      sol.put(index, range); 
      findPossibleSolutions(remTotal, coeffCopy); 
      range--; 
     } 
    } 

    private void displaySolution() { 
     int total = 0; 
     for(int i : sol.keySet()) { 
      //System.out.print(coeff.get(i)+"("+sol.get(i)+"), "); 
      total = total + (coeff.get(i)*sol.get(i)); 
     } 
     if(total != 30) 
      System.out.print(total+","); 
    } 

    /** 
    * @param coeff 
    */ 
    private int returnLargestIndex(Map<Integer, Integer> coeff) { 
     int largestKey = coeff.keySet().iterator().next(); 
     for(int i : coeff.keySet()) { 
      if(coeff.get(i)>coeff.get(largestKey)) { 
       largestKey=i; 
      } 
     } 
     return largestKey; 
    } 

} 

Answer 8

यह पर्ल में एक समाधान है। रेगेक्स का उपयोग करके एक हैक।

इस ब्लॉग के बाद post रेगेक्स का उपयोग करके बीजगणित समीकरणों को हल करने के लिए।

हम निम्न स्क्रिप्ट के लिए 3x + 2y + 5z = 40

#!/usr/bin/perl 
$_ = 'o' x 40; 
$a = 'o' x 3; 
$b = 'o' x 2; 
$c = 'o' x 5; 
$_ =~ /^((?:$a)+)((?:$b)+)((?:$c)+)$/; 
print "x = ", length($1)/length($a), "\n"; 
print "y = ", length($2)/length($b), "\n"; 
print "z = ", length($3)/length($c), "\n"; 

उत्पादन का उपयोग कर सकते हैं: एक्स = 11, y = 1, जेड = 1

प्रसिद्ध Oldest plays the piano पहेली एक के रूप में समाप्त होता है 3 परिवर्तनीय समीकरण

यह विधि condition के लिए लागू होती है कि चर वास्तव में सकारात्मक हैं और स्थिर सकारात्मक है।