LINUX.ORG.RU

Racket Scheme. Вычислить и представить в виде списка полином Лежандра.

 ,


2

3

Здравствуйте, делал математические вычисления на scheme. И у меня возникла потребность вывести результаты вычисления в виде списка, на чем я собственно и застрял.

Задание: Вычислить и представить в виде списка полином Лежандра Pk: P0 = 1, P1 = x, Pn+1 = ((2n + 1)xPn − nPn−1)/(n + 1).

Я переделал формулу для просто Pn-ого члена для удобства вычисления. Pn = ((2n-1)*x*P[n-1] - (n-1)*P[n-2])/(n). Формула в виде картинки, Pn-ого члена, которая получилась

Код который у меня получился правильно находит значения полинома.

Вот код, который получился до того как я пытался вывести результаты вычисления в список.

#lang scheme

(define (P0 n)
  1
  )

(define (P1 x)
  x
  )

(define (Pn x n)
  (if (= n 0)
      (P0 x)
      (if (= n 1)
          (P1 x)
          (/ (- (* (- (* 2 n) 1) x (Pn x (- n 1))) (* (- n 1) (Pn x (- n 2)))) n)
          )
      )
  )
;(lambda (x n) (/ (- (* (- (* 2 n) 1) x (Pn x (- n 1))) (* (- n 1) (Pn x (- n 2)))) n))

(define (legendre n)
  (do ((i #e-1
          (+ i #e0.1)
          ))
    ((= i #e1) i)
    (println (exact->inexact (Pn i n)))
    )
  )

(legendre 2)

А вот костыльный код, в котором я вывожу результаты вычисления в список.

#lang scheme

(define (P0 n)
  1
  )

(define (P1 x)
  x
  )

(define (Pn x n)
  (if (= n 0)
      (P0 x)
      (if (= n 1)
          (P1 x)
          (/ (- (* (- (* 2 n) 1) x (Pn x (- n 1))) (* (- n 1) (Pn x (- n 2)))) n)
          )
      )
  )

(define (P0lst n)
  '(1)
  )

(define (P1lst x)
  (append (P0lst x) (list x))
  )

(define (Pnlst x n)
  (if (= n 0)
      (P0lst x)
      (if (= n 1)
          (P1lst x)
          (/ (- (* (- (* 2 n) 1) x (Pn x (- n 1))) (* (- n 1) (Pn x (- n 2)))) n)
          )
      )
  )

(define resLst (list))

(define add
  (let ((the-list resLst))
    (lambda (new-item)
      (set! resLst
            (cons new-item resLst))
      the-list)))

(define (legendre n)
  (do ((i #e-1
          (+ i #e0.1)
          ))
    ((= i #e1) i)
    (add (exact->inexact (Pnlst i n)))
    )
  )



(legendre 2)
resLst

В связи с плохими знаниями функционального программирования и scheme в частности, у меня возник вопрос, а можно ли найти способ более элегантно занести результаты в список?



Последнее исправление: stzky (всего исправлений: 4)

Не знаю, что такое полиномы лежандра, а вникать лень. Но могу посоветовать улучшить форматирование. Вместо

(define (Pnlst x n)
  (if (= n 0)
      (P0lst x)
      (if (= n 1)
          (P1lst x)
          (/ (- (* (- (* 2 n) 1) x (Pn x (- n 1))) (* (- n 1) (Pn x (- n 2)))) n)
          )
      )
  )

лучше делать

(define (Pnlst x n)
  (if (= n 0)
      (P0lst x)
      (if (= n 1)
          (P1lst x)
          (/ (- 
	      (* (- 
		  (* 2 n) 1) 
		 x (Pn x (- n 1)))
	      (* 
	       (- n 1) 
	       (Pn x (- n 2))))
	     n))))
ugoday ★★★★★
()
Ответ на: комментарий от ugoday

Спасибо, выглядит и правда читабельнее.

stzky
() автор топика
Ответ на: комментарий от ugoday

лучше делать

мешанина из табов и пробелов

anonymous
()

Попробуй так. Проверь только на корректность, вдруг я что-то потерял. В твоем варианте со списком, кстати, отбрасывался первый полином. println лучше не использовать, он поддерживается только в racket scheme, вместо него лучше брать display. Полагаю, для текущего задания это неважно, но chez scheme и guile scheme значительно быстрее racket scheme.

#lang scheme

(define (Pn x n)
  (cond ((= n 0) 1)
        ((= n 1) x)
        (else (let* ((Pn-1 (Pn x (- n 1)))
                     (Pn-2 (Pn x (- n 2)))
                     (a (* (- (* 2 n) 1) x Pn-1))
                     (b (* (- n 1) Pn-2)))
                     (/ (- a b) n)))))

(define (iterate-while f c i)
  (if (c i)
      (list i)
      (cons i (iterate-while f c (f i)))))

(define (legendre n)
  (map (lambda (i) (exact->inexact (Pn i n)))
       (iterate-while (lambda (i) (+ i #e0.1)) (lambda (i) (= i #e1)) #e-1)))
(display (legendre 2))
Siborgium ★★★★★
()
Последнее исправление: Siborgium (всего исправлений: 1)
Ответ на: комментарий от stzky

Вычисление полиномов я просто переписал чуть покрасивее с помощью let*. iterate-while f c i создает список '(i, f(i), f(f(i)), ...), пока условие c не выполнится для очередного элемента. В качестве условий я подставляю условия из вашего списка, так получая аналог цикла. Затем я для каждого элемента полученного списка вычисляю соответствующий полином, получая список полиномов от соответствующих элементов. Можно было бы написать ленивую версию, чтобы генерировать список i по мере необходимости, но это не имеет большого смысла, раз вы все равно будете хранить весь список полиномов.

Siborgium ★★★★★
()
Последнее исправление: Siborgium (всего исправлений: 1)
Ответ на: комментарий от Siborgium

Мой вариант. Рекурсия вычисляет каждый Pn один раз, а не экспонециально.

Используется стандартная функция iota вместо своего велосипеда.

#lang scheme
(require srfi/1)

(define (Pn x target-n)
  (define (rec Pn-2 Pn-1 n)
    (define Pn (/ (- (* (- (* 2 n) 1) x Pn-1)
                     (* (- n 1) Pn-2))
                  n))
    (if (= target-n n)
        Pn
        (rec Pn-1 Pn (add1 n))))
  (case target-n
    ((0) 1)
    ((1) x)
    (else (rec 1 x 2))))

(define (legendre n)
  (map (lambda (i) (exact->inexact (Pn i n)))
       (iota 21 #e-1 #e0.1)))
(display (legendre 2))
monk ★★★★★
()
Последнее исправление: monk (всего исправлений: 1)
Ответ на: комментарий от monk

Все хорошо, но iota я считаю плохим выбором. Если тс нужно будет поменять шаг, то ему придется менять шаг и перерасчитывать количество. Велосипед ничем не хуже библиотечной функции, но не требует библиотеки (камон, подключать всю srfi ради одной функции), при этом при необходимости достаточно просто поменять шаг.

С рекурсией трюк красивый. Я не додумался. Хотя вообще оно через ряды с обычной хвостовой рекурсией должно считаться нормально, судя по формулам.

Siborgium ★★★★★
()
Ответ на: комментарий от Siborgium

то ему придется менять шаг и перерасчитывать количество

Если предполагается, что нужно будет менять количество шагов и оно будет неизвестно (но будет известен шаг и границы), то можно сделать расчётно:

(define (iota* start stop step)
  (iota (/ (- stop start) step) step))
...

(iota* #e-1 #e1 #e0.1)

Велосипед ничем не хуже библиотечной функции, но не требует библиотеки (камон, подключать всю srfi ради одной функции)

Спорно. Чтение проще с известными библиотечным функциями. Даже первый вариант с

(do ((i #e-1 (+ i #e0.1)))
    ((= i #e1) i)
    (displayln (exact->inexact (Pn i n)))))

читается проще, чем

(map (lambda (i) (displayln (exact->inexact (Pn i n))))
     (iterate-while (lambda (i) (+ i #e0.1)) 
                    (lambda (i) (= i #e1))
                    #e-1)))

если принципиально собрать список, то

(map (lambda (i) (exact->inexact (Pn i n)))
     (do ((i #e-1 (+ i #e0.1))
          (l null (cons i l)))
         ((= i #e1) (reverse l))))

На полстрочки больше, чем с iterate-while, зато сразу понятно, что этот кусок делает.

P.S. В Си тоже вместо strcpy(a,b); будете писать {char *t1 = a, *t2 = b; while(*t1++ = *t2++); } чтобы весь string.h не подключать?

monk ★★★★★
()
Последнее исправление: monk (всего исправлений: 1)
Ответ на: комментарий от Siborgium

Хотя вообще оно через ряды с обычной хвостовой рекурсией должно считаться нормально, судя по формулам.

Где хвостовая рекурсия в

        (else (let* ((Pn-1 (Pn x (- n 1)))
                     (Pn-2 (Pn x (- n 2)))

???

А у меня как раз хвостовая рекурсия и есть, так как вызов (rec …) является хвостовым.

monk ★★★★★
()
Ответ на: комментарий от monk

string.h

Это разные вещи. string.h – часть стандартной библиотеки, которая есть в любой реализации языка С. Статус поддержки srfi можешь загуглить сам, поддерживают его не все и не полностью. Само подключение модулей в схеме вообще городят кто во что горазд.

если принципиально собрать весь список

Именно ради того, чтобы собрать весь список, оно и писалось. Безусловно, в этом нет нужды если использовать do и вычислять поэлементно.

Где хвостовая рекурсия в

Здесь ее нет. Про полиномы Лежандра советую все же почитать вики, там и соответствующие формулы для вычисления через ряды есть.

А у меня как раз хвостовая рекурсия

Я не спорю, что у вас хвостовая рекурсия. В моем предложении ударение должно было ставиться на «через ряды», а не так, как вы прочитали.

Siborgium ★★★★★
()
Последнее исправление: Siborgium (всего исправлений: 4)
Ответ на: комментарий от Siborgium

там и соответствующие формулы для вычисления через ряды есть

Теперь понял. Те формулы вычислительно сложнее. Рекурсивная даёт три умножений, три вычитания, одно деление на элемент. Через ряды, как минимум, вычисление степени.

monk ★★★★★
()
Ответ на: комментарий от monk

Спасибо за помощь, немного сложновато было, но вроде суть понял.

stzky
() автор топика
Ответ на: комментарий от Siborgium

Спасибо за пояснение, так гораздо понятнее.

stzky
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.