FizzBuzz Ruby一线 [英] FizzBuzz Ruby one-liner
问题描述
Rosettacode.org在Ruby中具有出色的单行FizzBuzz解决方案.
Rosettacode.org has this excellent one-line FizzBuzz solution in Ruby.
1.upto(100){|n|puts'FizzBuzz '[i=n**4%-15,i+13]||n}
麻烦是,我不明白.使我感到困惑的部分是"n以4模-15的幂".有人有解释或对解释的引用吗?我想在其他问题中使用这种选择子字符串的方式. 有关FizzBuzz的详细信息,请参阅[ https://rosettacode.org/wiki/FizzBuzz ] >
The trouble is, I don’t understand it. The part that puzzles me is the "n to the power of 4 modulo -15". Does anyone have an explanation or a reference to an explanation? I want to use this way of selecting substrings in other problems. For more information on FizzBuzz, see [https://rosettacode.org/wiki/FizzBuzz]
推荐答案
我不知道他们是如何发现提高到第四幂的,但是-15是因为FizzBuzz处理的是3的倍数或5的倍数或5的倍数. 3和5(即15的倍数)中的一个...然后取反,最终可以很好地处理负指数.我们可以看到它与模块化幂一起使用.此处的内存有效方法部分显示:
I don't know how they discovered to raise to the fourth power, but the -15 is because FizzBuzz deals with multiples of 3 or multiples of 5 or multiples of both 3 and 5 (ie, multiples of 15)...then negating it ends up working with negative indices quite well. We can see that it works with Modular Exponentiation. The Memory-efficient method section there says:
c mod m =(a⋅b)mod m
c mod m = [(a mod m)⋅(b mod m)] mod m
c mod m = (a ⋅ b) mod m
c mod m = [(a mod m) ⋅ (b mod m)] mod m
在我们的例子中, c 是我们的 n ,所以我们有
In our case, the c is our n, so we have
c ** 4 % m
使用指数定律,我们知道(c ** e1) * (c ** e2) = c ** (e1 + e2)
,所以c ** 4 = (c ** 2) * (c ** 2)
,所以我们现在有一个a
和b
,它们都是c ** 2
.因此:
using the law of exponents, we know that (c ** e1) * (c ** e2) = c ** (e1 + e2)
, so c ** 4 = (c ** 2) * (c ** 2)
, so we now have an a
and a b
, which are both c ** 2
. Thus:
(c ** 4) % m = ((c ** 2) * (c ** 2)) % m
= (((c ** 2) % m) * ((c ** 2) % m)) % m
= (((c ** 2) % m) ** 2) % m
并再次执行相同的步骤:
and following the same steps, again:
(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个数字是有效的:
When m = -15
, the only values for c % m
are (-14..0)
and we can build a simple table to look at. Since we only ever operate on the result of a modulo, we only need to be able to prove these 15 numbers work:
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#[]
的开始参数中字符串'FizzBuzz '
可以给我们:
Now, looking at our table, the values for all multiples of 3 are -09
, the values for all multiples of 5 are -05
, and things that are multiples of 3 and 5 are set to 00
; everything else is -14
(If we had used 15 instead of -15, we'd have 6, 10, 0, and 1, respectively, and would need a look up to turn that into string indices). Plugging those in for the start parameter of String#[]
with the string 'FizzBuzz '
gives us:
'FizzBuzz '[-9] # => 'F'
'FizzBuzz '[-5] # => 'B'
'FizzBuzz '[0] # => 'F'
'FizzBuzz '[-14]# => nil
并在这些数字上加13以得到长度:
and adding 13 to those numbers to get the length:
'FizzBuzz '[-9, 4] # => "Fizz"
'FizzBuzz '[-5, 8] # => "Buzz "
'FizzBuzz '[0, 13] # => "FizzBuzz "
'FizzBuzz '[-14, -1] # => nil
这篇关于FizzBuzz Ruby一线的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!