FizzBuzz

Q: Was ist die Zeitkomplexität von FizzBuzz?

Die Antwort für eine Zahl hat den Aufwand O(1) : eine feste Anzahl von Restprüfungen und die Umwandlung einer Zahl mit höchstens 10 Ziffern. Die Ausgabe der Folge von 1 bis n hat den Aufwand O(n) .

EinsteigerMathe und Simulation

+10

Beim Zählspiel FizzBuzz zählen die Spieler ab 1 hoch und ersetzen einige Zahlen durch Wörter. Gegeben sei die Zugnummer n. Gib zurück, was ein Spieler in diesem Zug sagt: "FizzBuzz", wenn n sowohl durch 3 als auch durch 5 teilbar ist, "Fizz", wenn sie nur durch 3 teilbar ist, "Buzz", wenn sie nur durch 5 teilbar ist, und andernfalls n selbst als Zeichenfolge, zum Beispiel "7".

Funktion

fizzBuzz(n: integer) → string

ninteger: die Zugnummer, eine positive ganze Zahl
Gibt zurückstring: das Wort oder die Zahl, die im Zug n gesagt wird, als Zeichenkette

Einschränkungen

1 ≤ n ≤ 10⁹
Die Antwort ist immer eine Zeichenkette, selbst wenn sie die Zahl selbst ist.

Beispiele

Eingabe: n = 15
Ausgabe: "FizzBuzz"
Erklärung: 15 geteilt durch 3 ist 5 und 15 geteilt durch 5 ist 3, jeweils ohne Rest, also ist 15 an der Reihe "FizzBuzz".

Eingabe: n = 7
Ausgabe: "7"
Erklärung: 7 lässt bei der Division durch 3 einen Rest von 1 und bei der Division durch 5 einen Rest von 2, daher trifft kein Wort zu und du gibst die Zahl als Text zurück: "7".

Weiterführende Frage

Eine neue Regel macht Vielfache von 7 zu "Bazz", wobei die Wörter der Reihe nach zusammengefügt werden, sodass 105 "FizzBuzzBazz" ist. Wie fügst du sie hinzu, ohne für jede Kombination einen eigenen Fall zu behandeln?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jede Regel ist eine Prüfung des Rests. Der Knackpunkt ist die Reihenfolge: 15 ist durch 3 teilbar, also gibt eine Funktion, die zuerst 3 prüft und sofort zurückkehrt, für 15 "Fizz" zurück. Prüfe entweder zuerst den kombinierten Fall oder setze die Antwort aus beiden Prüfungen zusammen.

Bilde das Wort aus beiden Prüfungen

Idee

Beginne mit einem leeren Wort. Wenn 3 n teilt, füge "Fizz" hinzu; wenn 5 n teilt, füge "Buzz" hinzu. Beide Prüfungen werden immer ausgeführt, sodass ein Vielfaches von 15 beide Teile der Reihe nach sammelt und ohne Sonderfall zu "FizzBuzz" wird. Wenn das Wort noch leer ist, wurde keine der beiden Regeln angewendet, und du gibst die Zahl als Zeichenkette zurück.

Algorithmus

Setze word auf eine leere Zeichenkette.
Wenn n % 3 == 0, hänge "Fizz" an.
Wenn n % 5 == 0, hänge "Buzz" an.
Wenn word leer ist, gib n als Zeichenkette zurück.
Andernfalls gib word zurück.

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

Prüfe 15, dann 3, dann 5

Idee

Eine Zahl, die sowohl durch 3 als auch durch 5 teilbar ist, ist genau eine Zahl, die durch 15 teilbar ist, da 3 und 5 keinen gemeinsamen Faktor haben. Die kombinierte Regel ist also eine einzige Prüfung, n % 15 == 0, und sie kommt zuerst. Wenn sie fehlschlägt, bedeutet ein Treffer bei 3 nur 3 und ein Treffer bei 5 nur 5. Jede Prüfung gibt sofort etwas zurück, und wenn keine zutrifft, gibst du die Zahl als Zeichenfolge zurück.

Algorithmus

Wenn n % 15 == 0, gib "FizzBuzz" zurück.
Wenn n % 3 == 0, gib "Fizz" zurück.
Wenn n % 5 == 0, gib "Buzz" zurück.
Gib andernfalls n als Zeichenfolge zurück, wobei jede Ziffer ausgeschrieben wird.

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

Stolperfallen und Grenzfälle

3 oder 5 vor 15 prüfen und sofort zurückgeben: 15, 30 und 45 werden als "Fizz" ausgegeben.
Die Zahl statt einer Zeichenkette zurückgeben. Die Zahl 7 ist "7".
Große Zahlen in wissenschaftliche Notation umwandeln. In R gibt eine einfache Umwandlung 10^9 als 1e+09 aus; verwende format(n, scientific = FALSE).
Die Antwort ausgeben, statt sie zurückzugeben.

Häufige Fragen3

Warum wird FizzBuzz in Programmier-Vorstellungsgesprächen gefragt?

Es prüft, ob du eine kurze Reihe von Regeln in funktionierenden Code umsetzen kannst: eine Prüfung des Rests, Bedingungen in der richtigen Reihenfolge und den richtigen Rückgabetyp. Für jemanden, der regelmäßig programmiert, dauert es nur wenige Minuten und eignet sich daher als schneller Vorabtest vor schwierigeren Fragen.

Kannst du FizzBuzz ohne den Modulo-Operator lösen?

Ja. Teile mit Ganzzahldivision, multipliziere den Quotienten zurück und vergleiche ihn mit n: Sie sind nur dann gleich, wenn kein Rest bleibt. Wenn du die ganze Folge ausgibst, kannst du außerdem zwei Zähler verwenden, die bei 3 bzw. bei 5 zurückgesetzt werden.

Was ist die Zeitkomplexität von FizzBuzz?

Die Antwort für eine Zahl hat den Aufwand O(1): eine feste Anzahl von Restprüfungen und die Umwandlung einer Zahl mit höchstens 10 Ziffern. Die Ausgabe der Folge von 1 bis n hat den Aufwand O(n).

def fizzBuzz(n):
    # Schreibe hier den Code

Test #1

Test #2

Argument

n = 15

Erwartete Ausgabe

"FizzBuzz"