Scheme-Funktion, die prüft, eine Liste für Duplikate
Schreiben brauche ich eine Scheme-Funktion, die prüft, eine Liste auf doppelte Einträge. Ich glaube, ich habe den workflow auf dem Papier, ich brauche nur Hilfe, um es aus dem Papier in code.
Zuerst muss ich prüfen, ob es eine leere Liste. Also ich habe...
(define (checkDupe mylist)
(if (null? mylist)
()
(checkDupeB mylist)
)
)
Dann habe ich diese Art der "doppelten Rekursion", wo ich den ersten Nummer-gegen den rest der Liste, dann mit der zweiten Reihe gegen den rest der Liste, und so weiter, und wenn es eine übereinstimmung findet, es spuckt eine #t
, wenn es trifft am Ende und keine übereinstimmung findet, wird das Ergebnis der Funktion ist #f
. Das problem ist nur ich kann nicht umbrochen, mein Kopf herum diese Rekursion Zeug. Dies ist eine Hausaufgaben-Frage, aber ich bin geniunely interessiert, dieses Zeug, though.
Kann jemand werfen einige code bei mir und helfen mir, die Arbeit durch diese?
- Möchten Sie vielleicht einen Blick auf den Entwurf von, Wie Design-Programme, 2nd edition, vor allem ab etwa Kapitel 4: ccs.neu.edu/home/matthias/HtDP2e/htdp2e-part2.html. Das Kapitel behandelt, wie die methodische Herangehensweise an diese Art der Liste Probleme.
- um zu verstehen, Rekursion müssen Sie nur verstehen, zählen. wir rechnen mit natürlichen zahlen. was ist eine Natürliche Zahl? es ist entweder 0 oder eine mehr als eine Natürliche Zahl ist. Stell dir vor, du bist ein wizard in eine Mitte von einem heißen trockenen Wüste. kennen Sie eine Richtung, um jede Stadt in der Nähe, wie Sie sich entscheiden, zu gehen? Sie wollen finden Sie die nächste ein. wie können Sie wissen, eine Entfernung zu einer Stadt, ohne tatsächlich dorthin zu gehen? du bist ein Assistent; erstellen Sie eine Kopie von sich selbst, einen Schritt näher an die Stadt, und Fragen Sie, für die Antwort. Da er einen Assistenten zu, er wiederholt den Vorgang.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Hier ist es ein Weg,
Ich vermute, das ist eine Hausaufgabe. Es ist ein einfaches Verfahren, aber Ihnen fehlt ein Fall in Ihrem Navigations-Fluss, wie drei Fälle betrachtet werden müssen:
member
Verfahren die nützlich sein könnten)Als weitere Hilfe, hier ist die Allgemeine Vorstellung, füllen Sie die Felder aus:
Durchlaufen erneut die gesamte Liste für jedes Element zu prüfen, Duplikate können teuer sein - O(n^2). Die Prüfung für angrenzenden Duplikate ist viel billiger -- O(n). Wenn Sie nichts dagegen haben, ändern Sie die Reihenfolge der Elemente in der Liste, können Sie alle Duplikate benachbarten durch Sortieren der Liste ersten. Die Liste muss aus Elementen, die verglichen werden können, einige > operator.
Vorteil dieses Ansatzes ist, dass er sich auf ein standard-fold-operator, anstatt benutzerdefinierten Rekursion. Da dies Hausaufgaben gehe ich aus, eine definition von
cons-if-not-duplicate
.Gibt es mehr als einen Weg, um das problem zu lösen. Hier ist eine Anregung.
schreiben Sie eine helper-Funktion (is-element-in-Liste? x l),
die gibt true zurück, wenn x in der Liste l und sonst false.
Füllen Sie die Lücken in
Dies ist meine Lösung, die zwar ungetestet, sollte funktionieren,
Algorithmus mit lauter Stimme:
Wenn das erste Auto gleich das nächste Auto? Chop erste und gehen wieder, oder andere, halten Sie es, dann gehen Sie. So halten wir nur Unikate, nicht alles mit einem Nachbarn Geschwister