비 음성 값을 결정하기위한 알고리즘 선형 디오판틴 방정식에 대한 존재

StackOverflow https://stackoverflow.com/questions/1467907

  •  13-09-2019
  •  | 
  •  

문제

다음과 같은 방정식에 대한 해결책이 있는지 확인하는 방법을 찾고 있습니다.3N1+4N2+5N3 = 456, 어디 N1, N2, N3 긍정적 인 정수입니다.

또는 더 일반 : 거기에 있습니다 0 또는 양수 정수 N1, N2, N3... 방정식을 해결합니다 K1N1+K2N2+K3N3 ... = m 어디 K1, K2, K3... 그리고 중 긍정적 인 정수가 알려져 있습니다.

솔루션을 찾을 필요가 없습니다. 솔루션이 존재하는지 확인하기 위해서.

편집하다:

이 알고리즘의 실제 사용과 관련하여 :

커뮤니케이션 라이브러리에서 메시지를 처리하기 전에 주어진 메시지가 크기에 따라 유효한지 결정하고 싶습니다. 예를 들어 : 메시지에는 제로 또는 맨 3 바이트 요소, 제로 또는 맨 4 바이트 요소 및 제로 또는 5 바이트 요소가 포함되어 있음을 알고 있습니다. 456 바이트의 메시지를 받았으며 내용을 추가로 검사하기 전에 유효성을 결정하고 싶습니다. 물론 메시지의 헤더에는 각 유형의 요소 수가 포함되어 있지만와 같은 것을 전달하여 통신-라이브러리 수준에서 첫 번째 검사를 만들고 싶습니다. pair<MsgType,vector<3,4,5>>.

도움이 되었습니까?

해결책

당신은 정규 표현인지 묻습니다

(xxx | xxxx | xxxxx)*

xx ... x와 일치하며 여기서 x는 456 번 발생합니다.

다음은 O (n+a^2)의 솔루션입니다. 여기서 A는 왼쪽의 숫자 중 가장 작습니다 (이 경우 3).

숫자가 6,7,15라고 가정 해 봅시다. 6x+7y+15z 양식 "사용 가능한"형식으로 표시 가능한 숫자를 호출하겠습니다. 주어진 번호를 사용할 수 있는지 확인해야합니다.

숫자 n을 얻을 수 있다면 반드시 n+6, n+12, n+18- 일반적으로 모든 k> = 0에 대해 n+6k를 얻을 수 있습니다. N-6을 얻을 수 없으면 N-6도 사용할 수 없습니다 (N-6), (N-6)+6 = N을 사용할 수 있습니다). 이것은 N-12를 의미합니다. N-18, N-6K는 사용할 수 없습니다.

15가 사용 가능하지만 9는 그렇지 않다고 판단했다고 가정 해 봅시다. 우리의 경우 15 = 6*0+7*0+15*1이지만 어떤 식 으로든 9를 얻을 수 없습니다. 따라서, 우리의 이전 추론에 의해, 15+6k는 모든 k> = 0에 대해, 모든 k> = 0에 대해 9-6k는 이용 가능하지 않습니다. 6으로 나누는 숫자가 나머지 (3, 9, 15, 21, ...)로 3을 제공하는 숫자가 있다면 신속하게 대답 할 수 있습니다. 숫자 <= 9를 사용할 수없고 숫자> = 15입니다.

가능한 모든 나머지 분열에 대해 6 명 (즉 0,1,2,3,4,5)을 결정하는 것으로 충분합니다. (방금 나머지 3 의이 숫자는 15임을 보여주었습니다).

수행 방법 : 정점 0,1,2,3,4,5로 그래프를 만듭니다. 주어진 모든 숫자 k에 대해 (7,15- 우리는 무시 6) x에서 (x + k) mod 6. 무게를 줘 (x + k) div 6. Dijkstra의 알고리즘 0을 초기 노드로 사용합니다. 알고리즘에서 발견 한 거리는 우리가 찾고있는 숫자입니다.

우리의 경우 (6,7,15) 숫자 7은 0-> 1 (중량 1), 1-> 2 (중량 1), 2-> 3 (중량 1), ..., 5->를 발생시킵니다. 0 (중량 1) 및 숫자 15는 0-> 3 (중량 2), 1-> 4 (중량 2), ..., 5-> 1 (중량 2)을 제공합니다. 0에서 3의 가장 짧은 경로는 하나의 가장자리를 갖습니다 - 무게는 2입니다. 그래서 6*2 + 3 = 15는 3을 나머지로 제공하는 가장 작은 숫자입니다. 6*1 + 3 = 9를 사용할 수 없습니다 (음, 우리는 이전에 손으로 확인했습니다).

그리고 정규 표현과 관련된 것은 무엇입니까? 글쎄, 모든 정규 표현에는 동등한 유한 한 오토마톤이 있으며 그중 하나를 구성했습니다.

여러 쿼리가 허용되는이 문제는 폴란드 올림피아드 그리고 나는 해결책을 번역했다. 이제 컴퓨터 과학이 실제 프로그래머에게 유용하지 않다고 말하는 사람이 들리면 그를 때리십시오.

다른 팁

에 따르면 이것, {n1, n2, n3, ...}의 가장 큰 공통 요소가 m의 제수가 아닌 경우 해결책이 없습니다. 이 페이지는 {n1, n2}의 예를 보여 주지만 더 큰 시스템으로 확장됩니다. 새로운 문제는 가장 큰 공통 요소를 찾기위한 알고리즘을 작성하는 것이지만 원래의 문제에 비추어 사소한 것입니다.

따라서 알고리즘의 일부는 gcf ({n1, n2, ...})를 찾으면 m의 계수인지 확인합니다. 그렇지 않으면 해결책이 없습니다. 이것은 솔루션이 존재한다는 것을 완전히 보여주지 않지만, 존재하지 않는다는 것을 신속하게 보여줄 수 있습니다.

정수 제약이있는 불평등 시스템에 대해 이야기하고있는 것 같습니다. 현실은이 시스템을 위해 해결하는 것입니다.

k1n1+k2n2+k3n3...=m
n1 >= 0
n2 >= 0
n3 >= 0

및 N1, N2, N3이 정수라는 추가적인 제약 조건. 그건 선형 프로그래밍 문제. 불행히도, 그러한 시스템을 정수 제약 조건은 NP- 완성됩니다. 그러나 알고리즘을 해결할 많은 알고리즘이 있습니다.

이것은와 관련이 있습니다 Frobenius 동전 문제, N> 3에 대해 해결되지 않았습니다.

무차별 적 접근법 (의사 코드) :

def a = 3
def b = 4
def c = 5
def x = 456

for n1 = a to int(x / a) + 1 step a
  for n2 =b to int(x / b) + 1 step b
    for n3 = c to int(x / c) + 1 step c
      if a * n1 + b * n2 + c * n3 = x then
        print n1, n2, n3

또한보십시오 http://mail.python.org/pipermail/python-list/2000-april/031714.html

편집하다: 커뮤니케이션 라이브러리에서는 즉시 작업해야하므로 의미가 없습니다. OP의 응용 프로그램에서 나는 아마도 일종의 해시를 사용할 것입니다. 그러나 그의 접근 방식은 흥미로운 것 같습니다.

다음은 2 개의 숫자 케이스에 무언가가 있습니다. 나는 그것을 확장하는 방법을 아직 알지 못했습니다.

상대적으로 프라임 정수 x와 y 2 개를 주어 주면 양의 정수 A와 B가 있습니다. ax+by=c 모든 c>=(x-1)(y-1)

기본적으로, 이것은 당신이 가정하는 경우에 작동합니다 x<y, 당신은 모든 정수 모드 x를 (0, y, 2y, 3y, ..., (x-1) y로 표현할 수 있습니다. 이제 X의 양의 배수를 추가하면 (x-1) (x-1) y] 사이의 모든 정수에 도달 할 수 있습니다. 1) 및 (x-1) Y-1은 이전에 발현되었다.

  1. gcd (x, y). C가 여러 사람이 아닌 경우 거짓을 반환하십시오.
  2. gcd (x, y)> 1 인 경우 x, y, c를 GCD로 나눕니다.
  3. C> (x-1) (y-1) 인 경우 true를 반환합니다.
  4. 그렇지 않으면 무자비한 힘

그리고 무자비한 힘을 위해 : 

if int(c/y) >= c*y^(-1) mod x, return true, 
else return false

아마도 다음 정보는 일반적인 상황을 다루지 않기 때문에 무의미 할 것입니다.

문제가 주어진 양의 정수 k를 합으로 형성 할 수 있는지 여부를 결정하는 것이라면 3*n1 + 4*n2 + 5*n3, 비 음성 정수 n1, n2, n3의 경우, 대답은 k> = 3의 경우 "예"입니다.

로젠의 유명한 교과서 개별 수학 및 응용 프로그램, p. 여섯 번째 판의 287 개는 유도를 사용하여 "4 센트 및 5 센트 스탬프를 사용하여 12 센트 이상의 모든 우송료를 형성 할 수 있음을 증명합니다.

기본 단계는 12 센트의 우송료가 3 개의 4 센트 스탬프로 형성 될 수 있다는 것입니다.

유도 단계는 p (k)가 4 센트 스탬프를 사용하는 경우 p (k+1)가 사실임을 보여주기 위해 4 센트 스탬프를 5 센트 스탬프로 대체하는 것으로 간주합니다. P (k)가 4 센트 스탬프를 사용하지 않는 경우, k> = 12이기 때문에 합계를 형성하려면 최소 3 개의 5 센트 스탬프가 필요하며 3 개의 5 센트 스탬프를 4 개의 4 센트로 교체 할 수 있습니다. K+1을 달성하기위한 스탬프.

이 문제에 대한 위의 솔루션을 확장하려면 몇 가지 경우를 더 고려하면됩니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top