선형 디오 판틴 방정식을 풀어 라. (예를 들어 설명 참조)

Question

내가 너희를 해산하기 전에 숙제 문제가 아니고 나는 대학생이 아니라는 것을 분명히함으로써 시작하자. :)

EDIT @Klas와 다른 사람들 덕분에, 이제 내 질문은 프로그래밍 방식으로 해결되어야하는 수학적 방정식으로 바뀝니다.

Linear Diophantine Equation을 해결하는 알고리즘/코드를 찾고 있습니다. 이러한 식은 어떻게 보이는지 나 같은 낮은 인간 용 은 여기 :

예 1 3x + 4y + 5z = 25

예 2 (X, Y, Z의 모든 가능한 값 찾기) 10p + 5q + 6r + 11s = 224 (p의 모든 가능한 값을 찾기 , Q, R, S)

예 3 8p + 9q + 10r + 11s + 12t = 1012 (P, Q, R, S, T의 모든 가능한 값을 찾기)

난 소용 인터넷 검색을 시도했다. 나는 이것을 해결하기 위해 이미 몇몇 코드가 작성되었을 것이라고 생각했을 것이다. 너희들이 이미 이것을 구현 한 어떤 종류의 도서관을 발견했다면 나에게 알려주기 바란다. 그리고 만약 솔루션이 자바라면 아무 것도 더 시원 할 수 없습니다!. 알고리즘/의사 코드도 수행합니다. 감사합니다.

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

이것은 프로그래밍 문제가 아닌 수학적 질문입니다. 일단 당신이 적당한 알고리즘을 가지고 있다면, 그것을 impelementing 너무 열심히해서는 안됩니다.

나는 디오 판틴 방정식에 당신을 권합니다.

나는 explanation을 찾았습니다.

Answer 3

는 : 알고리즘은 임의의 디오 판 투스 방정식이 솔루션이 있는지 여부를 결정하기 위해 존재한다면

힐버트의 10 번째 문제는 물었다. 이러한 알고리즘은 1 차 디오 판틴 방정식의 해를 구하기 위해 존재합니다. 그러나, 일반적으로 용액을 얻는 것이 불가능 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); 
      } 
     } 
    } 
} 

이것을 N 변수의 경우에 대해 일반화하려면 재귀 양식으로 변환해야합니다.

이 알고리즘은 일부 기능이 f 인 경우 O(f(size, a)^N)입니다.

• 에 경계를 배치 할 수 있습니다. size/MaxValue(a) <= f(size, a) <= size/MinValue(a).
• 최악의 경우 (여기서 a[i]은 모두 1 임) f(size, a)은 size입니다.

어느 쪽이든, 이것은 N의 큰 값에 대해서는 꽤 끔찍합니다. 재귀 N 변수 알고리즘이 더 우아 할지라도, 아마도 매우 실용적이지는 않을 것입니다. 당신이 스프링 출판사에 34 유로의 밖으로 포크하고자하는 경우

---

, 여기 (추상에 따른)을 N 변수 사건을 해결하기위한 알고리즘을 포함 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])의 배열이 생성됩니다. 가능할 때마다 하위 사용자를 재사용하여 데이터 구조를 가능한 작게 만듭니다. 만약 당신이 cant를 반복적으로 대답의 배열로 다시 확장 할 수 있으며 그렇게함으로써 당신은 매우 효율적입니다. (실제로는 O(nX)입니다.) 동일한 사실을 반복해서 찾아내는 논리는 거의 반복하지 않습니다. 반환되는 목록은 매우 많아 질 수 있습니다.

Answer 6

없거나 무한히 많은 해결책이 있습니다. 솔루션이 일치해야하는 추가 제한 조건이있는 경우가 종종 있습니다. 이 문제가 귀하의 문제입니까?

이의 두 unkowns a*x + b*y = c가 가장 간단한 상황으로 시작 해보자 : 첫 번째 단계는 a 및 b의 GCD를 찾기 위해 Euclidean algorithm을 사용

이의이 d를 호출 할 수 있습니다. 보너스로 알고리즘은 a*x' + b*y' = d과 같이 x' 및 y'을 제공합니다. d이 c을 나누지 않으면 해결책이 없습니다. 그렇지 않으면 해결책은 다음과 같습니다.

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

두 번째 단계는 모든 해결책을 찾는 것입니다. 즉, 과 q이 모두 a*p + b*q = 0이되도록해야합니다.두 (x,y) 및 (X, Y) 다음

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

솔루션 인 경우이 대답은 p = b/d와 d = GCD(a,b)q = -a/d이고 일반적인 솔루션은 이제 이미 단계에서 계산된다

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

여기서 n 정수입니다.

첫 번째 단계는 여러 변수로 쉽게 확장 할 수 있습니다. 나는 두 번째 단계를 일반화하는 것에 대해 확신하지 못한다. 내 첫 번째 추측은 계수의 모든 쌍에 대한 해를 찾고 이러한 솔루션을 결합하는 것입니다.

Answer 7

이 경우 Java 코드를 작성했습니다. 제발 도와주세요. 솔루션은 광범위하게 테스트되지는 않았지만 지금까지는 잘 작동하는 것 같습니다.

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

이것은 Perl의 해결책입니다. Regex를 사용하여 오히려 해킹.

정규식을 사용하여 대수 방정식을 풀기 위해이 블로그 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"; 

출력 다음 스크립트를 사용하여, X = 11, Y가 = 1, Z = 1

유명한 Oldest plays the piano 퍼즐은로 끝난다 3 변수 방정식

이 방법은 변수가 실제로 양수이고 상수가 양수인 condition에 적용됩니다.