Wie erhalten Sie die größten n Elemente einer Liste mit Scheme?

Question

Ich stecke auf eine Hausaufgabe und könnte irgendwelche Hinweise oder Vorschläge verwenden. Ich muss die n größten Zahlen in einer Liste mit Scheme finden. Ich versuche dies zu tun, indem ich Hilfsfunktionen erzeuge, die von der Hauptfunktion aufgerufen werden. Bisher habe ich dies:

(define (get_max_value L) 
    (if (null? L) 
     '() 
     (apply max L) 
) 

(define (biggest_nums L n) 
    (if (null? n) 
     '() 
     (cons (get_max_value L) (biggest_nums L (- n 1))) 
    ) 
) 

Wenn ich tippe (biggest_num ‚(3 1 4 2 5) 3) an der Eingabeaufforderung DrRacket hängt nur und nicht einmal eine Fehlermeldung zurück. Wo gehe ich falsch?

Answer 1

Sortieren Sie die Liste und geben Sie die ersten n Elemente zurück.

Wenn jedoch die Liste sehr lang ist und n nicht sehr groß ist, dann möchten Sie wahrscheinlich nicht zuerst die ganze Liste sortieren. In diesem Fall würde ich so etwas wie dies vorschlägt:

(define insert-sorted 
    (lambda (item lst) 
    (cond ((null? lst) 
      (list item)) 
      ((<= item (car lst)) 
      (cons item lst)) 
      (else 
      (cons (car lst) (insert-sorted item (cdr lst))))))) 

(define largest-n 
    (lambda (count lst) 
    (if (<= (length lst) count) 
     lst 
     (let loop ((todo (cdr lst)) 
        (result (list (car lst)))) 
      (if (null? todo) 
       result 
       (let* ((item (car todo)) 
        (new-result 
         (if (< (car result) item) 
          (let ((new-result (insert-sorted item result))) 
          (if (< count (length new-result)) 
           (cdr new-result) 
           new-result)) 
          result))) 
       (loop (cdr todo) 
         new-result))))))) 

Answer 2

Zwei Netzprobleme mit Ihrem Code:

1. L immer gleich bleibt. L nimmt nicht ab, wenn Sie den rekursiven Aufruf durchführen, daher ist die max bei jedem rekursiven Aufruf immer gleich.
2. Sie überprüfen nie n, um sicherzustellen, dass es die richtige Anzahl von Zahlen enthält, bevor Sie die Antwort zurückgeben.

Um diese beiden Probleme in der banalsten Art und Weise möglich, lösen Sie eine (< n 1) Bedingung in der if setzen, und so etwas wie (cdr L) verwenden, indem ein Element jedes Mal L Abnahme der Größe in jedem rekursiven Aufruf zu machen. So

(define (biggest-nums n L) 
     (if (or (empty? L) 
       (< n 1)) 
      '() 
      (cons (apply max L) (biggest-nums (- n 1) (cdr L))))) 

, wenn wir es laufen:

> (biggest-nums 3 '(1 59 2 10 33 4 5)) 

Welche sollte die Ausgabe sein?

'(59 33 10) 

Was ist der tatsächlichen Ausgang?

'(59 59 33) 

OK, also haben wir Ihren Code ausgeführt, aber es gibt immer noch einige Probleme damit. Weißt du, warum das passiert? Können Sie den Code durchgehen, um herauszufinden, was Sie tun könnten, um das Problem zu beheben?

Answer 3

Die einfachste Lösung ist, zuerst die Nummern in aufsteigender Reihenfolge zu sortieren und dann zuerst die n zu nehmen. Dies führt wahrsten Sinne des Wortes in Racket-Code:

(define (biggest_nums L n) 
    (take (sort L >) n)) 

Es funktioniert wie erwartet:

(biggest_nums '(3 1 4 2 5) 3) 
=> '(5 4 3)