正则表达式计数 3s [英] Regex Counting By 3s

问题描述

我正在自学正则表达式，并找到了一个测验网站，该网站一直帮助我找到更多适用于它们的应用程序，并一直帮助我扩展对它们工作原理的了解.

I'm teaching myself regular expressions, and found a quizzing site that has been helping me find more applications for them and has been helping me expand my knowledge of how they work.

我发现了一个问题，要求我形成一个正则表达式来匹配 3 的倍数的 10 位数字.我能想到的唯一方法是让正则表达式识别数字的值并能够以数学方式操纵它们.这怎么可能?

I found a question asking me to form a regex to match 10 digit numbers that are multiples of 3s. The only way I can think of doing this is by having the regex recognise numbers' values and be able to manipulate them mathematically. How is this possible?

换句话说，什么正则表达式会匹配

In other words, what regex would match

0003
0006
0351
1749

但不匹配

0005
0011
0361
4372

推荐答案

首先你需要从一个数能被 3 整除的规则开始，当且仅当它的数字之和能被 3 整除(证明这需要一个很少有数论，但它有助于看到 9、99、999 等都是 3 的倍数，因此 1、10、100、1000 等在除以 3 时对一个数的余数的贡献相同).

First you need to start with the rule that a number is divisble by three if and only if the sum of its digits is divisible by three (proving this takes a little number theory, but it helps to see that 9, 99, 999 etc. are all multiples of three and therefore 1, 10, 100, 1000, etc. all contribute the same amount to the remainder of a number when divided by three).

然后，注意有三种数字:

Then, notice that there are three kinds of digits:

• 三的倍数:0、3、6 和 9.它们等价于 0 (mod 3).
• 3 的倍数的一个多:1、4 和 7.它们等价于 1(mod 3).
• 比三的倍数多两个:2、5 和 8.它们等价于 -1 (mod 3).通常这个类被命名为 2，但 -1 对我们更有用.因为 1 + 2 = 0 (mod 3)，-1 是 2 的合法名称.

• The multiples of three: 0, 3, 6, and 9. These are equivalent to 0 (mod 3).
• One more than multiples of three: 1, 4, and 7. These are equivalent to 1 (mod 3).
• Two more than multiples of three: 2, 5, and 8. These are equivalent to -1 (mod 3). Conventionally this class is named 2, but -1 is more useful to us. Because 1 + 2 = 0 (mod 3), -1 is a legitimate name for 2.

那么，数字 0、3、6 和 9 是 3 的倍数.如果我们在任何地方添加 0 类中的任意数量的数字，该数字仍然是三的倍数(因此 33、999 和 963 都是三的倍数).如果我们在任何地方添加 1 类的数字，我们需要添加另一个 -1 类的数字，或者再添加两个 1 类的数字> 将余数带回 0.同样，如果我们在任何地方添加 -1 类的数字，我们要么需要添加另一个 1 类的数字，或者再添加两个-1 类的数字将余数带回 0.

Then, the numbers 0, 3, 6, and 9 are multiples of three. If we add any number of digits from class 0 anywhere, the number remains a multiple of three (so 33, 999, and 963 are all multiples of three). If we add a digit from class 1 anywhere, we need to either add another digit of class -1, or add two more digits of class 1 to bring the remainder back to 0. Likewise if we add a digit from class -1 anywhere, we either need to add another digit of class 1, or add two more digits of class -1 to bring the remainder back to 0.

这是 wcp 的答案，格式为 perl /x 正则表达式以提高可读性:

Here's wcp's answer, formatted as a perl /x regex for readability:

/
(   [0369] # 0
  | [147] [0369]* [258] # 1 + 0 + -1 = 0
  | (   [258] # -1
      | [147] [0369]* [147] # 1 + 0 + 1 = -1
    ) # -1
    (   [0369] # 0
      | [258] [0369]* [147] # -1 + 0 + 1 = 0
    )* # 0
    (   [147] # 1
      | [258] [0369]* [258] # -1 + 0 + -1 = 1
    ) # 1 ... -1 + 0 + 1 = 0
)+
/x

正则表达式匹配余数为 0 的数字组.第一个分支只匹配 0 类的数字；第二个分支匹配余数上升到 1 然后回到 0 的组；并且第三个分支匹配余数下降到 -1 然后返回到 0 的组.它的构建方式有一些巧妙(我认为打高尔夫球的正则表达式有五个主要分支而不是三个)，但评论应该足以让你跟随它.

The regex matches groups of digits having remainder of 0. The first branch matches only digits of class 0; the second branch matches groups where the remainder goes up to 1 and then back to 0; and the third branch matches groups where the remainder goes down to -1 and then back to 0. There's some cleverness in how it's constructed (a less-golfed regex would have five major branches instead of three, I think), but the comments should be enough to let you follow it.

这篇关于正则表达式计数 3s的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！