FizzBuzz

Q: Какова временная сложность FizzBuzz?

Ответ для одного числа — O(1) : фиксированное число проверок остатка и преобразование числа, содержащего не более 10 цифр. Вывод последовательности от 1 до n занимает O(n) .

НовичокМатематика и моделирование

+10

В игре на счёт FizzBuzz игроки считают от 1 и заменяют некоторые числа словами. Для номера хода n верните то, что игрок произносит на этом ходу: "FizzBuzz", если n делится и на 3, и на 5, "Fizz", если оно делится только на 3, "Buzz", если оно делится только на 5, а в остальных случаях — само n, записанное в виде строки, например "7".

Функция

fizzBuzz(n: integer) → string

ninteger: номер хода, положительное целое число
Возвращаетstring: слово или число, произнесённое на ходу n, в виде строки

Ограничения

1 ≤ n ≤ 10⁹
Ответ всегда является строкой, даже если это само число.

Примеры

Ввод: n = 15
Вывод: "FizzBuzz"
Пояснение: 15, делённое на 3, равно 5, а 15, делённое на 5, равно 3 — в обоих случаях без остатка, поэтому на ходе 15 выводится "FizzBuzz".

Ввод: n = 7
Вывод: "7"
Пояснение: При делении на 3 от 7 остается остаток 1, а при делении на 5 — остаток 2, поэтому ни одно слово не подходит, и ты возвращаешь число в виде текста: "7".

Дополнительный вопрос

Новое правило превращает числа, кратные 7, в "Bazz"; слова соединяются по порядку, поэтому 105 — это "FizzBuzzBazz". Как добавить это правило, не создавая отдельный вариант для каждой комбинации?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Каждое правило — это проверка остатка. Здесь легко попасть в ловушку из-за порядка: 15 делится на 3, поэтому функция, которая сначала проверяет деление на 3 и сразу возвращает результат, для 15 выдаст "Fizz". Сначала проверьте комбинированный случай или сформируйте ответ на основе обеих проверок.

Составьте слово, используя обе проверки

Идея

Начни с пустого слова. Если n делится на 3, добавь "Fizz"; если n делится на 5, добавь "Buzz". Обе проверки выполняются всегда, поэтому число, кратное 15, собирает обе части по порядку и становится "FizzBuzz" без особого случая. Если слово всё ещё пустое, ни одно правило не применилось, и ты возвращаешь число в виде строки.

Алгоритм

Задай для word пустую строку.
Если n % 3 == 0, добавь в конец "Fizz".
Если n % 5 == 0, добавь в конец "Buzz".
Если word пустая, верни n, преобразованное в строку.
Иначе верни word.

def fizzBuzz(n):
    word = ""
    if n % 3 == 0:
        word += "Fizz"
    if n % 5 == 0:
        word += "Buzz"
    # An empty word means neither 3 nor 5 divides n.
    if word == "":
        return str(n)
    return word

Проверьте 15, затем 3, затем 5

Идея

Число, которое делится и на 3, и на 5, — это в точности число, делящееся на 15, потому что у 3 и 5 нет общих делителей. Поэтому объединённое правило — это одна проверка: n % 15 == 0, и она выполняется первой. Если она не проходит, совпадение с 3 означает только 3, а совпадение с 5 — только 5. Каждая проверка сразу возвращает результат, а если ни одно условие не совпадает, верните число в виде строки.

Алгоритм

Если n % 15 == 0, верни "FizzBuzz".
Если n % 3 == 0, верни "Fizz".
Если n % 5 == 0, верни "Buzz".
В противном случае верни n, преобразованное в строку, записав каждую цифру словами.

def fizzBuzz(n):
    if n % 15 == 0:
        return "FizzBuzz"
    if n % 3 == 0:
        return "Fizz"
    if n % 5 == 0:
        return "Buzz"
    return str(n)

Ловушки и крайние случаи

Проверка 3 или 5 до 15 и немедленный возврат: для 15, 30 и 45 получается "Fizz".
Возврат числа вместо строки. Для числа 7 получается "7".
Преобразование больших чисел в научную нотацию. В R обычное преобразование выводит 10^9 как 1e+09; используйте format(n, scientific = FALSE).
Вывод ответа вместо его возврата.

Частые вопросы3

Почему FizzBuzz задают на собеседованиях по программированию?

Это проверяет, умеешь ли ты превращать короткий набор правил в работающий код: проверку остатка, условия в правильном порядке и правильный тип возвращаемого значения. Для человека, который регулярно пишет код, это занимает несколько минут, поэтому такое задание подходит для быстрой проверки перед более сложными вопросами.

Сможешь решить FizzBuzz без оператора остатка от деления?

Да. Разделите с помощью целочисленного деления, умножьте частное обратно и сравните его с n: они равны только тогда, когда остатка не остаётся. Когда выводите всю последовательность, можно также использовать два счётчика, которые сбрасываются на 3 и на 5.

Какова временная сложность FizzBuzz?

Ответ для одного числа — O(1): фиксированное число проверок остатка и преобразование числа, содержащего не более 10 цифр. Вывод последовательности от 1 до n занимает O(n).

def fizzBuzz(n):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

n = 15

Ожидаемый вывод

"FizzBuzz"