球拍杆切割问题，如何在递归函数中使用向量

Question

我想弄清楚为什么我会得到预期的错误向量？和预期的一对？并且如果有办法将向量作为变量并访问向量以解决杆切割问题（类似于背包问题）。

#lang slideshow

; test input: (cutrod 5 #(0 1 2 3 2 2 6 1 2 3 10))

(define (square) (colorize(rectangle 20 15) "red"))
(define (rodpiece n) (apply hc-append(vector->list (make-vector n (square)))))

(define (cutrod n s)
    (rodpiece n)
      (cond
        ((null? s) '())
        (else
         (let
             ([cut (car (vector->list s))]
              [rods (cdr (vector->list s))])
            (cons cut (cutrod (- n (vector-ref s n)) rods))
            (cutrod n rods)
            n))))

这是我用来转换的 C++ PrintSolution 版本：

void PrintSolution(int n, int s[]){
   while(n>0){
      printf(“%d ”, s[n]);
      n = n ‐ s[n];
      }
}

当我尝试将向量转换为列表时发生此错误，它说它需要一个向量：

当我保持矢量原样时会发生此错误，它说它需要一对：

Answer 1

部分问题在于 (rodpiece) return 是一个列表，而不是向量。您可以通过将其更改为：

轻松解决此问题

(define (rodpiece n)
  (make-vector 1
               (apply hc-append
                      (build-list n
                                  (lambda (x)
                                    (square))))))

不需要从矢量开始，但目标是 return 一个。

下一个问题是您在基本上丢弃 return 值的位置调用 (rodpiece)。你想要更接近于此的东西：

(define (cutrod n s)
  (let* ((sn (vector-ref s n))
         (rp (rodpiece sn)))

预先确定了杆件的大小，之后获取当前杆件使用。然后您需要检查递归的基本情况：

    (if (or (<= n 0)
            (> n (vector-length s))) 
        rp

如果 n 为零，或者比剩余向量 s 长，您只需 return 当前杆件。

递归本身累加当前杆件与剩余杆件：

        (vector-append rp (cutrod (- n sn) s)))))

将所有这些放在一起，您有：

#lang slideshow

(define (square)
  (colorize (rectangle 20 20) "red"))

(define (rodpiece n)
  (make-vector 1
               (apply hc-append
                      (build-list n
                                  (lambda (x)
                                    (square))))))

(define (cutrod n s)
  (let* ((sn (vector-ref s n))
         (rp (rodpiece sn)))
    (if (or (<= n 0)
            (> n (vector-length s))) 
        rp
        (vector-append rp (cutrod (- n sn) s)))))

(define cut-vector  #(0 1 2 3 2 2 6 1 2 3 10))

(cutrod 5 cut-vector)
(cutrod 6 cut-vector)
(cutrod 7 cut-vector)
(cutrod 9 cut-vector)
(cutrod 10 cut-vector)

球拍杆切割问题，如何在递归函数中使用向量

Racket rod cutting problem, how to use vectors in recursive functions

lisp

recursion

scheme

functional-programming

racket