查找列表中数字的位置

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 中找到了类似的问题，但我不理解代码，因为我是编程新手。 ：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 辅助函数中，首先检查中间列表是否为空；这是一种基本情况，当我们在列表中只有一个元素时，并返回其索引。

下一个条件检查中间列表的下一个元素是否大于当前的 least 值，如果是，我们使用新的 least 值及其索引调用 helper。

当下一个元素不大于 least 时，选择最后一个条件，并使用相同的 least 和 ind-least 值调用辅助函数，删除头元素的中间列表，直到列表中没有元素为止，当列表中没有元素时，我们接近基本情况。

Answer 2

名为 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