我正在寻找一种方法来确定是否有方程式的解,例如: 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>>。
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,那么n-6也肯定不可用(如果您可以得到(n-6),则(n-6)+ 6 = n将可用),这意味着n-12, n-18,n-6k都不可用。
假设您确定15个可用,但9个不可用。在我们的情况下,15 = 6 * 0 + 7 * 0 + 15 * 1,但无法以任何方式获得9。因此,根据我们先前的推理,对于所有k> = 0可用15 + 6k,而对于所有k> = 0则可用9-6k。如果您有一些数字被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)mod6。为其赋予权重(x + k)div6。使用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不可用(嗯,我们之前手动检查过)。
与正则表达式的关系是什么?好吧,每个正则表达式都有一个等效的有限自动机,我构造了其中一个。
波兰奥运会上出现了允许多次查询的问题,我翻译了解决方案。现在,如果您现在听到有人说计算机科学对真正的程序员没有用,那就打个招呼。