Нахождение позиции числа в списке

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

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

Answer 1

Хороший пример для с именем let :

(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

Answer 2

Вы хотите две функции.Первая функция находит наименьший элемент 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 вспомогательной функции сначала вы проверяете, пустой ли промежуточный список;это базовый случай, когда мы получаем только один элемент в списке и возвращаем его индекс.

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

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