从 C 转换为 Racket 方案

Question

我写了下面的 C 代码来递归解决给定的问题，即取一个非空的整数列表和一个目标值，return 最接近的正值而不超过目标。例如(3 4) with target 2 should return 1. 唯一的组合是-3 + 4 = 1.:

int closest(int arr[], int target, int i, int n)
{
    
    if (i == n)
        return 0; 

    int sum1 = arr[i] + closest(arr, target - arr[i], i + 1, n); 
                                                                
    int sum2 = -1 * arr[i] + closest(arr, target + arr[i], i + 1, n); 

    if (abs(sum1 - target) < abs(sum2 - target))
    {
        return sum1; 
    }
    else
    {
        return sum2;
    }
}

不幸的是，这个问题本来是要用 Racket 写的，限制是使用 car + cdr 而不是使用 let 为 sum1/sum2 创建变量，我遇到了很大的困难。

到目前为止：

(define closest (lambda (l target i n)
  (cond
    ((= i n)0) 
   )
  )
  )

我的问题是：如何将 arr[i] 和指针转换为 car/cdr 逻辑？我隐约知道它控制两个值，但迭代似乎把我的大脑分成两半。

Answer 1

这是您正在做的翻译。我认为让您感到困惑的主要问题是 cons car 的工作原理。球拍中的“向量”（或列表）实际上是这样的：

(cons 1 (cons 2 (cons 3 empty)))

在 C

中翻译成这个

[1, 2, 3]

那么我们如何从中获取第 i 个元素呢？！好吧，如果你看看你的递归，我们实际上 不需要 。实际上，我们总是在我们刚刚处理的元素之后从列表中获取下一个元素。我们一次一个地遍历列表，不关心我们已经计算的内容。

实际上，转换为 C，我们在 racket 中所做的是进行指针运算以获取下一个元素并将该指针作为我们的新 arr 传递回函数。列表的其余部分只是在我们无法访问的意义上被“遗忘”。到目前为止我们所做的计算仍然被记住。

我相信您正在使用 i 和 n 来跟踪我们在数组中的位置，因此我们可以删除它们，因为我们不需要实际跟踪我们在哪个元素上：

#lang racket
(require test-engine/racket-tests)

(define (closest arr target)
  (define sum1 (if (or (null? arr)) 0 (+ (car arr) (closest (cdr arr) (- target (car arr))))))
  (define sum2 (if (or (null? arr)) 0 (+ (* -1 (car arr)) (closest (cdr arr) (+ target (car arr))))))
  (if (< (abs (- sum1 target)) (abs (- sum2 target)))
      sum1
      sum2))

(check-expect (closest '(3 4) 2) 1)
(test)

Answer 2

你真的应该学习如何“用 Scheme 思考”，但是“用 Scheme 和 C 思考”也很有价值。

首先，使用指针运算而不是数组索引。
如果你仔细观察，你会发现 *p 有点像 (car p) - “第一个元素” - 而 p + 1 有点像 (cdr p) - “其余部分”元素”。
然后你倒数到零而不是倒数到 n（也就是说，你问“还有多少元素要做？”而不是“我们完成了多少元素？”）。

int closest(int *arr, int target, int n)
{
    if (n == 0)
        return 0; 
    /* I rearranged these two slightly in order to emphasize the symmetry. */
    int sum1 = closest(arr + 1, target - *arr, n-1) + *arr; 
    int sum2 = closest(arr + 1, target + *arr, n-1) - *arr; 
    if (abs(sum1 - target) < abs(sum2 - target))
    {
        return sum1; 
    }
    else
    {
        return sum2;
    }
}

现在我们需要摆脱“let-绑定”、sum1 和 sum2。
我们可以通过引入一个函数来做到这一点：

int pick(int target, int sum1, int sum2)
{
    return abs(sum1 - target) < abs(sum2 - target) ? sum1 : sum2;
}

int closest(int *arr, int target, int n)
{
    if (n == 0)
        return 0; 
    return pick(target,
                closest(arr + 1, target - *arr, n-1) + *arr,
                closest(arr + 1, target + *arr, n-1) - *arr);
}

（正如the Fundamental Theorem所说，任何问题都可以通过增加一个间接级别来解决。）

这可以在 Scheme 中以一种非常直接的方式表达——主要是改变标点符号。
请注意，我们不再需要计数器，因为我们可以从列表本身得知我们已经到达终点：

(define (pick target sum1 sum2)
    (if (< (abs (- sum1 target)) (abs (- sum2 target)))
        sum1
        sum2))

(define (closest arr target)
    (if (null? arr)
        0
        (pick target
              (+ (closest (cdr arr) (- target (car arr))) (car arr))
              (- (closest (cdr arr) (+ target (car arr))) (car arr)))))

现在我们可以“内联”pick，删除 target 参数，因为它在周围上下文中可用：

(define (closest arr target)
    (if (null? arr)
        0
        ((lambda (sum1 sum2)
             (if (< (abs (- sum1 target)) (abs (- sum2 target))) sum1 sum2))
         (+ (closest (cdr arr) (- target (car arr))) (car arr))
         (- (closest (cdr arr) (+ target (car arr))) (car arr)))))

从 C 转换为 Racket 方案

Converting from C to Racket Scheme

c

recursion

scheme

code-translation

racket