Все публикации подряд (habrahabr_ru) wrote,
Все публикации подряд
habrahabr_ru

Category:

[Перевод] Решение Fizzbuzz при помощи теоремы Эйлера

https://habr.com/ru/post/547892/?utm_source=habrahabr&utm_medium=rss&utm_campaign=547892

image

FizzBuzz — это известная задачка на программирование, которую обычно дают в технической части собеседований. Она формулируется примерно так:

Напишите функцию, выводящую список целых чисел от 1 до 100, но вместо каждого числа, кратного 3, она должна выводить «Fizz», а вместо каждого числа, кратного 5, выводить «Buzz». Вместо чисел, кратных и 3, 5, программа должна выводить «FizzBuzz»; все остальные числа должны выводиться без изменений.

Можно написать функцию, вообще не использующую условную логику и вместо этого разделяющую целые числа на 4 возможные категории (обычное решение оставим в качестве упражнения заинтересованному читателю):

  1. Имеющие делитель 3, но не 5
  2. Имеющие делитель 5, но не 3
  3. Имеющие делитель и 3, и 5
  4. Не имеющие делитель 3 и 5

Нам нужна функция, которая будет возвращать:

  • «Fizz», если $n \equiv 0 \pmod 3$ и $n$ является взаимно простым с 5
  • «Buzz», если $n \equiv 0 \pmod 5$ и $n$ является взаимно простым с 3
  • «FizzBuzz», если $n \equiv 0 \pmod 3$ и $n \equiv 0 \pmod 5$
  • $n$ во всех остальных случаях.

Рассмотрим реализацию такой функции на Python:

[(lambda n: { 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" }[n**4%15])(n+1) for n in range(100)]

Та же функция на Ruby:

(1..100).map{|n| {1 => n, 6 => "Fizz", 10 => "Buzz", 0 => "FizzBuzz"}[n**4%15] }

Как мы и ожидали, каждая из этих функций возвращает список целых чисел от 1 до 100 с подставленными в нужные места «Fizz», «Buzz» и «FizzBuzz».

Но почему? Откуда взялись постоянные значения 0, 6, 10 и 1? Почему $n^4 \mod 15$ возвращает 6 для чисел, кратных 3, но не 5, 10 для чисел, кратных 5, но не 3, 0 для чисел, кратных 5 и 3 и 1 во всех остальных случаях? И самое важное — справедливо ли это для любого $n$, которое мы выберем?
Читать дальше →
Subscribe
  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments