Блог

Я написал следующий код на C для рекурсивного решения для данной задачи, которая заключается в том, чтобы взять непустой список целых чисел и целевое значение и вернуть ближайшее положительное значение, не переходя к цели. например, (3 4) с целью 2 должен возвращать 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? Я смутно понимаю, что он контролирует два значения, но итерация, похоже, разбивает мой мозг надвое.

Вам действительно следует научиться «мыслить по схеме», но «мышление по схеме, на 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 -bindings», 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);
}
 

(Как гласит Фундаментальная теорема, любая проблема может быть решена путем добавления уровня косвенности.)

Это может быть сформулировано в 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)))))
 

Вот перевод того, что вы делаете. Я думаю, что главное, что вас сбивает с толку, — это то, как cons car это работает. «Векторы» (или списки) в racket на самом деле выглядят так:

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

что приводит к этому в C

 [1, 2, 3]
 

Итак, как мы получаем i из него элемент th ?! Ну, если вы посмотрите на свою рекурсию, нам на самом деле это не нужно. По сути, мы всегда получаем следующий элемент из списка после того, который мы только что обработали. Мы проходим по списку по одному и не заботимся о том, что мы уже вычислили.

Фактически, в переводе на 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)