FizzBuzz Ruby однострочный

Question

Rosettacode.org имеет отличное однострочное решение FizzBuzz в Ruby.

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

Проблема в том, что я не понимаю этого. Часть, которая озадачивает меня, - это «n к степени 4 по модулю -15». У кого-нибудь есть объяснение или ссылка на объяснение? Я хочу использовать этот способ выбора подстрок в других задачах. Для получения дополнительной информации о FizzBuzz см. [https://rosettacode.org/wiki/FizzBuzz]

Answer 1

Я не знаю, как они обнаружили, чтобы поднять до четвертой степени, но -15, потому что FizzBuzz имеет дело с кратными 3 или кратными 5 или кратными как 3, так и 5 (т.е. кратными 15) .. затем отрицание приводит к тому, что он работает с отрицательными показателями довольно хорошо. Мы видим, что он работает с Модульное экспонирование . В разделе Метод с эффективным использованием памяти там написано:

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#[] со строкой '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

Answer 2

Я постараюсь добавить более простое объяснение к превосходному ответу @Simple Lime. Если n кратно 3, давайте обозначим его как 3k, сейчас:

(3k)^4  == 81(k^4)

81 % 15 == 6 и давайте вычтем 15 (так как это по модулю -15), чтобы получить -9.

Аналогично, когда n кратно 5, это 625(k^4) и 625 % 15 == 10, и после вычитания мы получаем -5.

В противном случае n может быть кратно 2, 7, 11 и 13. Во всех этих случаях n ^ 4% 15 будет равно 1 (см. Таблицу Simple Lime), а -15 даст нам -14.

Answer 3

Довольно сложно.

Модуль является периодической функцией. Вы можете получить более периодическую функцию с той же схемой, изменяя показатель степени (k) и делитель (h):

y = x**k % h

Или просто посмотрите пары x, y для случая:

h = 4 # exponent
k = -15 # divisor

xy = []
1.upto 100 do |n|
  i= n**h % k
  xy << [n, i]
end
p xy

Периодичность очевидна при выборе базового примера y = x % 2: k = 1 и h = 2. Вы получаете серию 1, 0, 1, 0, 1, ...

Для визуализации функции, используемой в этом случае, вы можете построить график в ruby, например, используя gem gnuplot.

require 'gnuplot' 

Gnuplot.open do |gp|
  Gnuplot::Plot.new( gp ) do |plot|

    plot.title  "Periodic function for FizzBuzz"

    x = (0..100).collect { |v| v }
    p y = x.collect { |v| v ** 4 % -15 }

    plot.data << Gnuplot::DataSet.new( [x, y] ) do |ds|
      ds.with = "linespoints"
    end
  end
end