arrays - 在方案中找到数组的最小值

Question

想要通过数组移动并记住最小值直到数组结束，然后返回最小的值。但是我不知道如何在计划中做到这一点

int smallest = INT_MAX;
for (int i = 0; i < array_length; i++) {
if (array[i] < smallest) {
    smallest = array[i];
  }
}

如果我想获得数组中的最小值，并且还想要下一个最小值，同时将其保持为数组形式

这将如何在计划中完成？

Answer 1

您可以像往常一样遍历向量/数组：

(define (vector-min v)
  (assert (positive? (vector-length v)))
  (let looping ((i 1) (v-min (vector-ref v 0)))
    (if (= i (vector-length v))
        v-min
        (looping (+ i 1)
                 (min v-min (vector-ref v i))))))

您还可以使用原始 Scheme 函数的组合：

(define (vector-min v)
  (apply min (vector->list v)))

代价是将向量转换为列表。

Answer 2

这取决于实施。

专业程序员会尽量避免重新发明轮子，并使用像min这样的函数，它可以正常工作。

像上面这样的代码可以按“字面意思”翻译，保留 C 代码的含义：

#lang racket
(define smallest +inf.0)
(define an-array (vector 3 1 4 1 5 9 2 6))
(define array-length 8)
(for ([i (in-range 0 array-length)])
  (when (< (vector-ref an-array i)
           smallest)
    (set! smallest (vector-ref an-array i))))
(print smallest)

但对于经验丰富的 Racket 程序员来说，这并不是很好的文体形式。它不仅只适用于向量，而且代码过于关注索引。

为什么不只研究我们关心的事物的元素呢？这是我们改变迭代焦点时的样子：

#lang racket
(define smallest +inf.0)
(define an-array (vector 3 1 4 1 5 9 2 6))
(for ([elt an-array])
  (when (< elt smallest)
    (set! smallest elt)))
(print smallest)

这个好一点。

如果我们要在多个地方做这样的事情，看看我们是否可以再清理一些可能是值得的。在 Racket 中，最好以这样一种方式编写它，以避免一遍又一遍地考虑愚蠢的循环细节。作为如何概括和清理它的具体示例，请参见for/max 此处（或此处）的定义。

关键是，让它在除了数组之外的其他东西上工作，如果你最终做了很多，让它成为你语言的一部分。

Answer 3

你有列表还是向量？

对于列表，该min函数是 R5RS 标准方案的一部分。

(min 5 1 4 23 4)

或者

(apply min '(5 1 3 4 55))

或者你可以自己动手

(define my-min
  (lambda lst
    (let loop ((min (car lst))
               (lst (cdr lst)))
      (if (null? lst)
        min
        (let ((x (car lst)))
          (if (< x min)
            (loop x (cdr lst))
            (loop min (cdr lst))))))))

vector->list对于向量，如果效率不是问题，您仍然可以将这些函数与 一起使用。

Answer 4

以下是一些标准的 R6RS 实现（因为您在标题广告问题中编写了 Scheme 而不是 Racket）。我已经评论了如何让它发挥作用#lang racket

#!r6rs
(import (rnrs base)
        (rnrs lists)
        (rnrs sorting))

;; using vector-sort. Not working in #lang racket
(define (my-min1 vec)
  (if (zero? (vector-length vec))
      +inf.0
      (vector-ref (vector-sort < vec) 0))) 


;; All the rest work on lists. 
;; You may make a wrapper like this (using my-min2 as example)
(define (my-min2-vec vec)
  (my-min2 (vector->list vec)))

;; using min, accepting inexact
(define (my-min2 lst)
   (apply min +inf.0 lst))

;; using base with integers
(define (my-min3 lst)
  (if (null? lst)
      +inf.0
      (apply min lst)))

;; using list-sort. 
;; #lang racket: use sort in place of list-sort and swap arguments.
(define (my-min4 lst)
  (if (null? lst)
      +inf.0
      (car (list-sort < lst))))

;; higher order functions
;; #lang racket: use foldl in place of fold-left 
(define (my-min5 lst)
  (define (min2 x y) 
    (if (< x y) x y))
  (fold-left min2 +inf.0 lst)) 

;; using < and iterating through helper
(define (my-min6 lst)
  (define (my-min6-aux lst min)
    (if (null? lst)
        min
        (my-min6-aux (cdr lst)
                     (let ((cur (car lst)))
                       (if (< cur min) cur min)))))
  (my-min6-aux lst +inf.0))

;; using < and iterating though named let
(define (my-min7 lst)
  (let my-min7-aux ((lst lst)
                    (min +inf.0))
    (if (null? lst)
        min
        (my-min7-aux (cdr lst)
                     (let ((cur (car lst)))
                       (if (< cur min) cur min))))))

(my-min1 '#(3 7 9 1 5))     ; ==> 1
(my-min2-vec '#(3 7 9 1 5)) ; ==> 1.0
(my-min2 '(3 7 9 1 5))      ; ==> 1.0
(my-min3 '(3 7 9 1 5))      ; ==> 1
(my-min4 '(3 7 9 1 5))      ; ==> 1
(my-min5 '(3 7 9 1 5))      ; ==> 1
(my-min6 '(3 7 9 1 5))      ; ==> 1
(my-min7 '(3 7 9 1 5))      ; ==> 1

Answer 5

已经有很多很好的答案，但我认为最直接的（除了直接翻译）是根据球拍支持的 SRFI 43 中提供的矢量折叠来实现矢量最小。

(define (vector-min vec)
 (vector-fold
    (lambda (n v-min next)
      (if (< v-min next) v-min next))
    (vector-ref vec 0)
    vec))

http://srfi.schemers.org/srfi-43/srfi-43.html#vector-fold

不确定代码是否有效，我的方案实现不提供完整的 srfi 43 库。