FizzBuzz

Q: Qual è la complessità temporale di FizzBuzz?

Rispondere per un numero è O(1) : un numero fisso di controlli del resto e la conversione di un numero con al massimo 10 cifre. Stampare la sequenza da 1 a n è O(n) .

PrincipianteMatematica e simulazione

+10

Nel gioco di conteggio FizzBuzz, i giocatori contano a partire da 1 e sostituiscono alcuni numeri con delle parole. Dato un numero di turno n, restituisci ciò che dice un giocatore in quel turno: "FizzBuzz" se n è divisibile sia per 3 che per 5, "Fizz" se è divisibile solo per 3, "Buzz" se è divisibile solo per 5 e, altrimenti, n stesso scritto come stringa, ad esempio "7".

Funzione

fizzBuzz(n: integer) → string

ninteger: il numero del turno, un numero intero positivo
Restituiscestring: la parola o il numero pronunciato al turno n, come stringa

Vincoli

1 ≤ n ≤ 10⁹
La risposta è sempre una stringa, anche quando è il numero stesso.

Esempi

Input: n = 15
Output: "FizzBuzz"
Spiegazione: 15 diviso per 3 fa 5 e 15 diviso per 5 fa 3, entrambi senza resto, quindi il turno 15 è "FizzBuzz".

Input: n = 7
Output: "7"
Spiegazione: 7 lascia un resto di 1 quando viene diviso per 3 e di 2 quando viene diviso per 5, quindi non si applica nessuna parola e restituisci il numero come testo, "7".

Per approfondire

Una nuova regola fa sì che i multipli di 7 siano "Bazz"; le parole vengono concatenate nell’ordine, quindi 105 è "FizzBuzzBazz". Come puoi aggiungerla senza prevedere un caso per ogni combinazione?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ogni regola è un controllo del resto. La trappola è l’ordine: 15 è divisibile per 3, quindi una funzione che verifica prima 3 e restituisce subito risponde "Fizz" per 15. Verifica prima il caso combinato oppure costruisci la risposta usando entrambi i controlli.

Costruisci la parola a partire da entrambi i controlli

Intuizione

Inizia con una parola vuota. Se 3 divide n, aggiungi "Fizz"; se 5 divide n, aggiungi "Buzz". Entrambi i controlli vengono sempre eseguiti, quindi un multiplo di 15 raccoglie entrambe le parti nell'ordine e diventa "FizzBuzz" senza casi speciali. Se la parola è ancora vuota, nessuna delle due regole si è applicata e restituisci il numero come stringa.

Algoritmo

Imposta word come stringa vuota.
Se n % 3 == 0, aggiungi "Fizz".
Se n % 5 == 0, aggiungi "Buzz".
Se word è vuota, restituisci n convertito in una stringa.
Altrimenti, restituisci 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

Controlla 15, poi 3, poi 5

Intuizione

Un numero divisibile sia per 3 che per 5 è esattamente un numero divisibile per 15, perché 3 e 5 non hanno fattori in comune. Quindi la regola combinata è un unico controllo, n % 15 == 0, e va eseguita per prima. Se non è soddisfatta, una corrispondenza con 3 significa solo 3 e una corrispondenza con 5 significa solo 5. Ogni controllo restituisce subito un risultato e, se nessuno corrisponde, restituisci il numero come stringa.

Algoritmo

Se n % 15 == 0, restituisci "FizzBuzz".
Se n % 3 == 0, restituisci "Fizz".
Se n % 5 == 0, restituisci "Buzz".
Altrimenti restituisci n convertito in una stringa, scrivendo ogni cifra per esteso.

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

Trappole e casi limite

Verificare 3 o 5 prima di 15 e restituire subito: 15, 30 e 45 risultano "Fizz".
Restituire il numero invece di una stringa. Il turno 7 è "7".
Convertire i numeri grandi in notazione scientifica. In R una conversione semplice stampa 10^9 come 1e+09; usa format(n, scientific = FALSE).
Stampare la risposta invece di restituirla.

Domande frequenti3

Perché FizzBuzz viene chiesto nei colloqui di programmazione?

Verifica che tu sappia trasformare un breve insieme di regole in codice funzionante: un test del resto, condizioni nell’ordine giusto e il tipo di valore restituito corretto. Per chi programma regolarmente bastano pochi minuti, quindi è un controllo rapido prima di domande più difficili.

Riesci a risolvere FizzBuzz senza l’operatore modulo?

Sì. Dividi usando la divisione intera, moltiplica di nuovo il quoziente e confrontalo con n: sono uguali solo quando non resta nulla. Quando stampi l’intera sequenza, puoi anche mantenere due contatori che si azzerano ogni 3 e ogni 5.

Qual è la complessità temporale di FizzBuzz?

Rispondere per un numero è O(1): un numero fisso di controlli del resto e la conversione di un numero con al massimo 10 cifre. Stampare la sequenza da 1 a n è O(n).

def fizzBuzz(n):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

n = 15

Output atteso

"FizzBuzz"