FizzBu​​zz Ruby单线程

Question

Rosettacode.org在Ruby中提供了这个出色的单行FizzBu​​zz解决方案.

1.upto(100){|n|puts'FizzBuzz '[i=n**4%-15,i+13]||n}

麻烦的是,我不明白.令我困惑的部分是"4模数-15的力量".有没有人有解释或参考解释？我想用这种方法在其他问题中选择子串.有关FizzBu​​zz的更多信息,请参阅[ https://rosettacode.org/wiki/FizzBu​​zz ]

Answer 1

我不知道他们是如何发现提升到第四种力量的,但-15是因为FizzBu​​zz处理3的倍数或5的倍数或3和5的倍数(即15的倍数)......然后否定它最终与负面指数很好地合作.我们可以看到它适用于Modular Exponentiation.那里的内存效率方法部分说:

c mod m =(a·b)mod m
c mod m = [(a mod m)⋅(b mod m)] mod m

在我们的例子中,c是我们的n,所以我们有

c ** 4 % m

使用指数定律,我们知道(c ** e1) * (c ** e2) = c ** (e1 + e2),所以c ** 4 = (c ** 2) * (c ** 2),我们现在有一个a和一个b,两个都是c ** 2.从而:

(c ** 4) % m = ((c ** 2) * (c ** 2)) % m
             = (((c ** 2) % m) * ((c ** 2) % m)) % m
             = (((c ** 2) % m) ** 2) % m

并按照相同的步骤再次:

(c ** 2) % m = (c * c) % m
             = ((c % m) * (c % m)) % m
             = ((c % m) ** 2) % m

最后:

(c ** 4) % m = ((((c % m) ** 2) % m) ** 2) % m

什么时候m = -15,唯一的值c % m是(-14..0),我们可以构建一个简单的表来查看.由于我们只对模数的结果进行操作,因此我们只需要能够证明这15个数字是有效的:

c%m    **2     %m    **2     %m
-14 => 196 => -14 => 196 => -14
-13 => 169 => -11 => 121 => -14
-12 => 144 => -06 =>  36 => -09
-11 => 121 => -14 => 196 => -14
-10 => 100 => -05 =>  25 => -05
-09 =>  81 => -09 =>  81 => -09
-08 =>  64 => -11 => 121 => -14
-07 =>  49 => -11 => 121 => -14
-06 =>  36 => -09 =>  81 => -09
-05 =>  25 => -05 =>  25 => -05
-04 =>  16 => -14 => 196 => -14
-03 =>   9 => -06 =>  36 => -09
-02 =>   4 => -11 => 121 => -14
-01 =>   1 => -14 => 196 => -14
 00 =>   0 =>  00 =>   0 =>  00

现在,查看我们的表,所有3的倍数-09的值是,所有5的倍数的值是-05,并且3和5的倍数的值被设置为00; 其他一切都是-14(如果我们使用15而不是-15,我们将分别有6,10,0和1,并且需要查找将其转换为字符串索引).将String#[]字符串中的start参数插入'FizzBuzz '为我们提供:

'FizzBuzz '[-9] # => 'F'
'FizzBuzz '[-5] # => 'B'
'FizzBuzz '[0]  # => 'F'
'FizzBuzz '[-14]# => nil

并为这些数字添加13以获得长度:

'FizzBuzz '[-9, 4]   # => "Fizz"
'FizzBuzz '[-5, 8]   # => "Buzz "
'FizzBuzz '[0, 13]   # => "FizzBuzz "
'FizzBuzz '[-14, -1] # => nil