Schreiben Sie eine Funktion findSteps12, die alle möglichen Schrittfolgen einer n-stufigen Treppe berechnet. F#

Question

Frage in F#:

a) Schreiben Sie eine Funktion findSteps12, die alle möglichen Schrittfolgen einer n-stufigen Treppe berechnet. In einem Schritt dürfen Sie eine oder zwei Treppenstufen weit hinaufsteigen.

b) Nun betrachten wir eine Treppe mit sehr kleinen Stufen. Sie können entweder eine, drei oder fünf Stufen

in einem Schritt hinaufsteigen. Implementieren Sie die Funktion findSteps135, welche alle möglichen
Schrittfolgen mit den genannten Schrittweiten berechnet.

c) Freiwillige Zusatzaufgabe: Schreiben Sie eine Funktion findSteps, die zusätzlich eine Liste von Schrittweiten erwartet und entsprechend alle damit möglichen Schrittfolgen berechnet.

Answer 1

Antwort mit KI erzeugt

Funktion findSteps12

Um die Funktion findSteps12 in F# zu implementieren, die alle möglichen Schrittfolgen einer \(n\)-stufigen Treppe berechnet, wenn man entweder eine oder zwei Stufen in einem Schritt machen kann, werden wir einen rekursiven Ansatz verwenden. Die Grundidee des Ansatzes ist, dass für jede Stufe Sie entweder mit 1 Schritt darauf treten können oder, falls möglich, 2 Schritte darauf machen können. Die rekursive Funktion ruft sich selbst auf, bis keine Stufen mehr übrig sind.

fsharp
let rec findSteps12 n =
    match n with
    | 0 -> [[]] // Keine Stufen zu besteigen
    | 1 -> [[1]] // Nur ein Weg, eine Stufe zu besteigen
    | _ -> 
        // Wege, die mit einem Schritt beginnen
        let waysWith1Step = findSteps12 (n - 1) |> List.map (fun way -> 1 :: way)
        // Wege, die mit zwei Schritten beginnen
        let waysWith2Steps = findSteps12 (n - 2) |> List.map (fun way -> 2 :: way)
        // Kombinieren der Wege
        waysWith1Step @ waysWith2Steps

findSteps12 3 |> List.iter (fun way -> printfn "%A" way)

Funktion findSteps135

Ähnlich der findSteps12-Funktion wird für findSteps135 ein rekursiver Ansatz verwendet, aber diesmal müssen wir die Möglichkeit berücksichtigen, entweder 1, 3 oder 5 Schritte in einem Zug zu machen.

fsharp
let rec findSteps135 n =
    match n with
    | 0 -> [[]] // Keine Stufen zu besteigen
    | n when n < 0 -> [] // Kein gültiger Weg, da n negativ ist
    | _ -> 
        // Wege für 1, 3 und 5 Schritte kombinieren
        [1; 3; 5]
        |> List.collect (fun step -> 
            if n - step >= 0 then 
                findSteps135 (n - step) |> List.map (fun way -> step :: way)
            else 
                [])
                
findSteps135 3 |> List.iter (fun way -> printfn "%A" way)

Funktion findSteps mit variablen Schrittweiten

Für die freiwillige Zusatzaufgabe, wo die Funktion auch eine Liste von Schrittweiten erwartet, kann man den vorherigen Ansatz generalisieren, indem die Liste der möglichen Schrittweiten als Argument übergeben wird.

fsharp
let rec findSteps steps n =
    match n with
    | 0 -> [[]]
    | n when n < 0 -> []
    | _ -> 
        // Kombinieren der Wege basierend auf den übergebenen Schrittweiten
        steps
        |> List.collect (fun step ->
            if n - step >= 0 then 
                findSteps steps (n - step) |> List.map (fun way -> step :: way)
            else 
                [])
                
findSteps [1;3;5] 3 |> List.iter (fun way -> printfn "%A" way)

Diese Implementierungen zeigen, wie man rekursive Funktionen in F# verwendet, um alle möglichen Schrittfolgen auf einer \(n\)-stufigen Treppe basierend auf gegebenen Schrittweiten zu berechnen.