Поиск позиции номера в списке

Question

Эй, ребята, у меня вопрос о домашнем задании, который меня разочаровал! Я должен создать индекс-наименьший, который возьмет непустой список и вернет индекс наименьшего числа в списке. Индекс (car ls) = 0, индекс (car (cdr ls)) = 1 и т. Д.

Необходимо создать помощник, который будет отслеживать текущее положение, наименьшую позицию, наименьшее значение и список. Пока у меня есть эта программа (которая не загружается), которая показывает базовый алгоритм. Но мне сложно отслеживать все и помещать его в код схемы chez.

(define index-helper 
    (lambda (ls current-position least-position least-value) 
    (if (> (car ls) least-value) 
     (add1 (car ls (cdr ls (add1 current-position)))) 
     (car ls (cdr ls (add1 current-position)))))) 

;trace 
;ls: (4231) c-pos: 0 least-value: 5 least-pos: 0 
;ls: (231) c-pos: 1 least-value: 4 least-pos: 1 
;ls: (31) c-pos 2 least-value: 2 least-pos: 2 
;ls: 1 c-pos: 3 l-v: 2 l-pos: 2 
;ls '() c-pos: 4 l-v: 1 l-pos: 4 
;*least-position = current-position 

Я уже гугле это и нашел подобные вопросы питона, но я не понимаю код, потому что я новичок в программировании. : P Если кто-нибудь может дать мне подсказку, я бы очень признателен!

Answer 1

Вы хотите две функции. Первая функция находит наименьший элемент x. Вторая функция находит индекс в элементе x.

Что-то вроде:

(define (find-least xs) 
    (foldl (lambda (e acc) (min e acc)) (car xs) xs)) 

(define (elem-index x xs) 
    (define (elem-index-find x xs ind) 
    (cond 
     ((empty? xs) ind) 
     ((eq? x (car xs)) 
     ind) 
     (else (elem-index-find x (cdr xs) (+ ind 1))))) 
    (if (empty? xs) 
     (error "empty list") 
     (elem-index-find x xs 0))) 

(define (index-of-least xs) 
    (let ((least (find-least xs))) 
    (elem-index least xs))) 

Тест:

> (index-of-least (list 5 8 4 9 1 3 7 2)) 
4 

Или, в один проход:

(define (index-of-least-1-pass xs) 
    (define (index-do least ind-least ind xs) 
    (cond 
     ((empty? xs) ind-least) 
     ((< (car xs) least) 
     (index-do (car xs) (+ ind 1) (+ ind 1) (cdr xs))) 
     (else 
     (index-do least ind-least (+ ind 1) (cdr xs))))) 
    (index-do (car xs) 0 0 (cdr xs))) 

Тест:

> (index-of-least-1-pass (list 5 8 4 9 1 3 7 2)) 
4 

В вспомогательной функции index-do сначала вы проверяете, является ли промежуточный список пустым; это базовый случай, когда мы получили только один элемент int в списке и вернем его индекс.

Следующее условие проверяет, является ли следующий элемент промежуточного списка больше текущего значения least, и если это так, мы вызываем хелпер с новым значением least и его индексом.

выбрано Последнее условие, когда следующий элемент не больше, чем least, и она вызывает вспомогательную функцию, с теми же значениями least и ind-least, и промежуточного список с головным элементом удален, пока нет никаких элементов в список, и мы подошли к базовому случаю, когда в списке нет элементов.

Answer 2

Хороший пример для имени пусть:

(define (index-of-least xs) 
    (let loop ((i 0) (p 0) (x (car xs)) (xs (cdr xs))) 
    (cond ((null? xs) p) 
      ((< (car xs) x) (loop (+ i 1) (+ i 1) (car xs) (cdr xs))) 
      (else (loop (+ i 1) p x (cdr xs)))))) 

(index-of-least (list 5 8 4 9 1 3 7 2)) => 4