может ли кто-нибудь объяснить, используя простой подход для начинающих, такой как подход грубой силы?

#common-lisp

Вопрос:

Мне нужно создать функцию LISP, которая , учитывая входной список целых (x_1 x_2 ... x_n) чисел, вычисляет произведение всех различий между элементами,

 Π (x_i - x_j), where i < j

Например, для списка: (4 3 2) функция должна вычислять: (4-2)(4-3)(3-2) = 2 . Если список пуст, функция должна вернуться 1 .

Это то, что я пытался:

Для пустого списка:

 (defun dprod0 (lst) 
    (if (null lst)
        1))

Для списка с 1 элементом:

 (defun dprod1 (lst)
    (if (= (list-length lst) 1)
        1))

это то, что у меня есть до сих пор

 (defun dprod (lst)
    (cond
     ((null lst) 1)
     ((= (list-length lst) 1) 1)
     (t (let ((a (first lst)) 
              (b (second lst)) 
              (r (cdr lst)))
        (* (- a b) (dprod r))))))

1. Это домашнее задание? Что вы пробовали до сих пор?

2. мне просто нужна помощь, чтобы начать, я не уверен, что было бы хорошим подходом

3. начните с записи определения функции, которая работает только для пустых списков. ты можешь это сделать? если нет, то вы задаете вопрос, который слишком сложен для вашего текущего уровня владения Lisp. если да, пожалуйста, отредактируйте его в своем вопросе. затем определите функцию, которая также работает для списка из 1 элемента. и, возможно, еще один, для списков из 2 элементов.

4. хорошо, я попробую

5. обновил то, над чем я работал до сих пор

Ответ №1:

Обычно мы стараемся не измерять длину всего списка lst без необходимости, если все, что нам нужно знать, является ли он пустым ( (null lst) ) или содержит только один элемент ( (null (cdr lst)) ). Таким образом, ваш код становится

 (defun dprod (lst)
    (cond
     ((null lst) 1)
     ((null (cdr lst)) 1)
     (t (let ((a (first lst)) 
              (b (second lst)) 
              (r (cdr lst)))
        (* (- a b) 
           (dprod r))))))

Теперь это совершенно прекрасный код, но что он вычисляет? Мы приведем несколько примеров, чтобы понять, что происходит. Мы будем использовать {...} для обозначения трансформации:

 { [  ] }  ==>  1
{ [ 2 ] }  ==>  1
{ [ 3, 2 ] }  ==>  (* (- 3 2) { [2] } ) ==> (3-2)*1

пока все хорошо. Далее,

 { [ 4, 3, 2 ] }  ==>  (* (- 4 3) { [3,2] } ) ==> (4-3)*(3-2)*1

и это неправильно. Нам нужно, чтобы это было (4-2)*(4-3)*(3-2)*1 так . Что то же (4-3)*(4-2)*(3-2)*1 самое, что .

Это означает, что при формировании различий ( 4-3 , 3-2 ) мы объединили первый элемент 4 только с тем, который следует за ним, 3 . Но нам нужно соединить его также и со всеми остальными. Ваш код делает это:

 { [ 5, 4, 3, 2 ] }  ==>  (5-4)*(4-3)*(3-2)*1

но он должен сделать это:

 { [ 5, 4, 3, 2 ] }  ==>  (5-4)*(5-3)*(5-2)*
                               (4-3)*(4-2)*
                                     (3-2)*
                                           1

Таким образом, мы должны дополнить его, как

 (defun dprod (lst)
    (cond
     ((null lst) 1)
     ((null (cdr lst)) 1)
     (t (let ((a (first lst)) 
              (b (second lst)) 
              (r (cdr lst)))
        (* (diffs a r)         ;; NB <<<----------
           (dprod r))))))

так что он будет вычислять

 { [ 5, 4, 3, 2 ] }  ==>  (5-4)*(5-3)*(5-2)*    ==  (diffs 5 [4,3,2])*
                               (4-3)*(4-2)*    ==  (diffs 4 [3,2])*
                                     (3-2)*    ==  (diffs 3 [2])*
                                           1   ==  (dprod [2])

Теперь вам нужно написать эту diffs функцию.

После этого вы также сможете упростить код для dprod .