确定线性不定方程的非负值解存在性的算法

Question

我正在寻找一种方法来确定是否存在方程的解,例如: 3n1 + 4n2 + 5n3 = 456,其中n1,n2,n3是正整数.

或者更一般:是零或正整数n1,n2,n3 ......解决方程k1n1 + k2n2 + k3n3 ... = m其中k1,k2,k3 ......和m是已知的正整数.

我不需要找到解决方案 - 只是为了确定是否存在解决方案.

编辑:

关于这个算法的实际使用:

在通信库中,我想在处理消息之前根据其大小决定给定消息是否有效.例如:我知道消息包含零个或多个3字节元素,零个或多个4字节元素和零个或多个5个字节元素.我收到了456字节的消息,我想在进一步检查其内容之前确定其有效性.当然,消息的标题包含每种类型的元素数量,但我想通过传递类似的东西在通信库级别进行第一次检查pair<MsgType,vector<3,4,5>>.

Answer 1

你问的是正则表达式

(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 - 一般来说,n + 6k所有k> = 0.另一方面,如果你无法获得一些数字n,那么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和9-6k所有k> = 0不是.如果你有一些除以6的数字给3作为余数(3,9,15,21,...)你可以快速回答:数字<= 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不可用(好吧,我们先前手工检查过).

与正则表达式的连接是什么？好吧,每个正则表达式都有一个等价的有限自动机,我构造了其中一个.

这个问题,允许多个查询,出现在波兰奥林匹克运动会上,我翻译了解决方案.现在,如果你现在听到一个人说计算机科学对真正的程序员没用,那就打他一下吧.