算法来确定非负数值解实存的线性不定方程 [英] Algorithm to determine non-negative-values solution existance for linear diophantine equation

问题描述

我寻找一种方法来确定是否有一个解决的方程，例如： 3N1 + 4N2 + 5n3 = 456 的，其中的 N1，N2，N3 的是正整数。

或者更一般的：是否有零或正整数的 N1，N2，N3 的...，解决了方程的 k1n1 + k2n2 + k3n3 ... = M 的，其中的 K1，K2，K3 的...和 M 的已知正整数。

我并不需要找到一个解决方案 - 只是为了确定一个解决方案存在

。

编辑：

关于实际使用这种算法的：

在一个通信库，我要决定是否根据其大小给定的消息是有效的，处理信息之前。 例如：我知道，一个消息包含零或更多的3-字节元件，零或更多的4-字节元素，和零或更多的5字节的元件。我收到的456个字节的消息，我想前进一步检查其内容，以确定其有效性。 当然，邮件的标题包含每种元素的个数，但我想通过传递类似对＆LT，使创检查在通信库水平; MSGTYPE，矢量＆lt; 3,4 ，5个;＆GT;

解决方案

你问如果经常EX pression

（XXX | XXXX | XXXXX）*

匹配XX ... x，其中x发生456次

下面是为O中的溶液（N + A ^ 2），其中一个是最小的左侧的数字（在本例3）。

假设你的号码是6,7,15。我会打电话给一些EX pressible形式6X + 7Y + 15Z可用。你要检查一个给定的数字是可用的。

如果你能够获得一些数n，那么可以肯定你将能够获得N + 6，N + 12，N + 18 - 一般来说，N + 6K对于所有的k> = 0。另一边，如果你不能得到一些数n，则n-6是肯定不会用太（如果你能得到（N-6），然后（N-6）+ 6 = N是可用），这表示正-12，N-18，N-6K不可没有。

假设你已经确定了15可用，但9不是。在我们的情况下，15 = 6 * 0 + 7 * 0 + 15 * 1，但将不能够得到9以任何方式。因此，我们的previous推理，15 + 6K适用于所有的k> = 0和9-6k对于所有的k> = 0是没有的。如果你有一些数字，除以6给出了3作为剩余物（3，9，15，21，...），您可以快速回答：数字＆LT; = 9不适，数> = 15是

这足以确定除以6所有可能的余（即0,1,2,3,4,5）什么是最小的数字，这是可用的。 （我刚已经表明，这个号码对其余3是15）。

如何做到这一点：创建一个顶点0,1,2,3,4,5图。对于您所提供的所有数字K（7,15 - 我们漠视6）从x添加一个边缘（X + K）模6.给它的重量（X + K）DIV 6.使用的Dijkstra's算法使用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不可用（当然，我们检查了previously手）。

什么是连接到正规EX pressions？那么，每一个正前pression具有等效有限自动机，我构建了其中的一个。

这个问题，有多个查询允许，出现在的波兰奥林匹克和我翻译的解决方案。现在，如果你听到现在的人说，计算机科学不是真正的程序员是有用的，打他的脸。

I am looking for a method to determine if there is a solution to equations such as: 3n1+4n2+5n3=456, where n1,n2,n3 are positive integers.

Or more general: are there zero or positive integers n1,n2,n3... that solves the equation k1n1+k2n2+k3n3...=m where k1,k2,k3... and m are known positive integers.

I don't need to find a solution - just to determine if a solution exist.

Edit:

Concerning the practical use of this algorithm:

In a communication library, I want to decide if a given message is valid according to its size, before handling the message. For example: I know that a message contains zero-or-more 3-bytes elements, zero-or-more 4-bytes elements, and zero-or-more 5-bytes elements. I received a message of 456 bytes, and I want to determine its validity before further inspecting its content. Of course the header of the message contains the number of elements of each type, but I want to make a first-inspection in the communication-library level by passing something like pair<MsgType,vector<3,4,5>>.

解决方案

You're asking if the regular expression

(xxx|xxxx|xxxxx)*

matches xx...x, where x occurs 456 times.

Here's a solution in O(n+a^2), where a is the smallest of the numbers on the left side (in this case 3).

Suppose your numbers are 6,7,15. I'll call a number expressible in the form 6x+7y+15z "available". You are to check if a given number is available.

If you're able to get some number n, then surely you will be able to get n+6, n+12, n+18 - in general, n+6k for all k >= 0. On the other side, if you are unable to get some number n, then n-6 is surely not available too (if you could get (n-6), then (n-6)+6=n would be available), this means n-12, n-18, n-6k are not available neither.

Suppose you have determined that 15 is available but 9 is not. In our case, 15=6*0+7*0+15*1 but won't be able to get 9 in any way. So, by our previous reasoning, 15+6k is available for all k >= 0 and 9-6k for all k >= 0 is not. If you've got some number that divided by 6 gives 3 as remainder (3, 9, 15, 21, ...) you can quickly answer: numbers <= 9 are not available, numbers >= 15 are.

It is enough to determine for all possible remainders of division by 6 (that is 0,1,2,3,4,5) what is the smallest number that is available. (I just have shown that this number for the remainder 3 is 15).

How to do it: Create a graph with vertices 0,1,2,3,4,5. For all numbers k that you are given (7,15 - we disregard 6) add an edge from x to (x + k) mod 6. Give it weight (x + k) div 6. Use Dijkstra's algorithm using 0 as the initial node. The distances found by the algorithm will be exactly those numbers we are searching for.

In our case (6,7,15) the number 7 gives rise to 0 -> 1 (weight 1), 1 -> 2 (weight 1), 2 -> 3 (weight 1), ..., 5 -> 0 (weight 1) and the number 15 gives 0 -> 3 (weight 2), 1 -> 4 (weight 2), ..., 5 -> 1 (weight 2). The shortest path from 0 to 3 has one edge - its weight is 2. So 6*2 + 3 = 15 is the smallest number that gives 3 as remainder. 6*1 + 3 = 9 is not available (well, we checked that previously by hand).

And what is the connection to regular expressions? Well, every regular expression has an equivalent finite automaton, and I constructed one of them.

This problem, with multiple queries allowed, appeared on the Polish Olympiad and I translated the solution. Now, if you hear now a person saying computer science is not useful for real programmers, punch him in face.

这篇关于算法来确定非负数值解实存的线性不定方程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！