242 / 120 / 14
Регистрация: 15.10.2010
Сообщений: 395
1

Вывести минимальное значение функции на заданном интервале и соответствующее ему значение аргумента.

29.08.2011, 22:53. Показов 3135. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Решил такое задание: Задан интервал и шаг изменения аргумента. Вывести минимальное значение функции https://www.cyberforum.ru/cgi-bin/latex.cgi?y=2{x}^{2}+5x-7 на заданном интервале и соответствующее ему значение аргумента.
Решил двумя способами - через рекурсию и через циклы. Вот решения:
Рекурсия:
Lisp
1
2
3
4
5
6
7
8
9
(defun arg (x)
    (- (+ (* 2 (* x x)) (* 5 x)) 7))
        
(defun lab (a b step &optional L)
    (if (> a b) L
        (lab (+ a step) b step 
            (if (OR (NULL L) (< (arg a) (second L)))
                (list a (arg a)) 
                L))))
С помощью DO:
Lisp
1
2
3
4
5
(defun foo (a b step)               
(do ((y (arg a) (arg a))
     (x a (if (< y (arg x)) a x)))
    ((> a b) (list x (arg x)))
     (setf a (+ step a))))
Запускаю:
Lisp
1
2
CL-USER 7 > (foo -1000 1000 0.1)
(-1.1999999998411286 -10.119999999968226)
Lisp
1
2
3
4
5
CL-USER 10 > (lab -1000 1000 0.1)
 
Stack overflow (stack size 16000).
  1 (abort) Return to level 0.
  2 Return to top loop level 0.
я так понимаю, при запуске рекурсивной функции при маленьком интервале и большом количестве шагов, произошло переполнение стека вызовов. Тогда как, функции с второй функции с DO практически всё по зубам. Как же тогда быть в данной ситуации программисту, признающему только "Чистый" Лисп? Как решить эту задачу, именно при таких исходных данных, с помощью рекурсии?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.08.2011, 22:53
Ответы с готовыми решениями:

Найти не только минимальное значение функции, но и соответствующее ему значение аргумента
Написать функцию пользователя, позволяющую находить минимум произвольной функции одного...

Вычислить минимальное по абсолютной величине значение функции и соответствующее значение аргумента
Составить программу табулирования и исследования функции f(x) на заданном диапазоне изменения...

Вычислить минимальное по абсолютной величине значение функции и соответствующее значение аргумента
Необходимо составить блок-схему и программу табулирования и исследования функции F(x) на диапазоне...

Взять минимальное значение из таблицы и соответствующее ему текстовое значение
Подскажите, пожалуйста, как взять минимальное значение из таблицы и соответствующее ему текстовое...

3
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
30.08.2011, 05:48 2
Дело в том, что оптимизация хвостовых вызовов (tail-call optimization) не входит в стандарт языка Common Lisp. Поэтому это зависит от реализации языка, будут ли хвостово-рекурсивные (tail-recursive) процедуры оптимизированы (специальный вид рекурсивных процедур; вкратце, если рекурсивный вызов процедуры - это последняя операция, то можно провести следующую оптимизацию: заменить рекурсивный вызов на безусловный переход, таким образом, чтобы не выделялся новый фрейм стека, а вычисления производились в постоянном объеме памяти). Например, sbcl использует tail-call optimization, и следующий код (как и твой, собственно) будет у меня работать:
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
(defun min-value-and-corresponding-arg (fun left-threshold right-threshold step)
  (labels ((iter (l-t prev-min)
         (if (> l-t right-threshold)
         prev-min
         (iter (+ l-t step)
               (let ((prev-val (cdr prev-min))
                 (new-arg l-t)
                 (new-val (funcall fun l-t)))
             (if (< new-val prev-val)
                 (cons new-arg new-val)
                 prev-min))))))
    (iter (+ left-threshold step) (cons left-threshold
                    (funcall fun left-threshold)))))
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
CL-USER> (min-value-and-corresponding-arg #'(lambda (x)
                          (+ (* 2 x x) (* 5 x) (- 7)))
                      -1000
                      1000
                      0.1)
(-1.2971125 . -10.120561)
CL-USER> ; увеличиваем диапазон и уменьшаем шаг - все опять работает:
; No value
CL-USER> (min-value-and-corresponding-arg #'(lambda (x)
                          (+ (* 2 x x) (* 5 x) (- 7)))
                      -10000
                      10000
                      0.01)
(-1.2509372 . -10.124998)
Так что если пишешь на Common Lisp, то предпочтение следует отдавать не рекурсивным функциям, а конструкциям циклов типа do, dolist, loop etc.
1
242 / 120 / 14
Регистрация: 15.10.2010
Сообщений: 395
10.09.2011, 20:27  [ТС] 3
Спасибо большое за ответ. Возник еще один вопрос:
А допустим я пишу на Haskell, который во многих статьях о функциональном программировании характеризуется как "чистый" функциональный язык? я так понимаю там не предусмотрено циклических конструкций? Только рекурсия. Там тоже оптимизация хвостового вызова, то есть замена на GOTO? Так какой же он тогда "чисто" функциональный?
P.S. Честное слово ничего не открывал по Haskell, просто интересно.
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
11.09.2011, 05:20 4
Цитата Сообщение от RUSya82 Посмотреть сообщение
я так понимаю там не предусмотрено циклических конструкций? Только рекурсия
верно.

Цитата Сообщение от RUSya82 Посмотреть сообщение
Там тоже оптимизация хвостового вызова
верно

Цитата Сообщение от RUSya82 Посмотреть сообщение
...то есть замена на GOTO? Так какой же он тогда "чисто" функциональный?
а это уже относится не к самому языку, а к его реализации, и чистоте языка никак не вредит, - ты же не можешь явно использовать в haskell'е конструкцию GOTO - ее там нет (вообще, термин "чистоты" языка относится к отсутствию в нем т.н. деструктивных модификаций, т.е. присваиваний).
В haskell'е есть свои аспекты работы с рекурсивными функциями, связанные с особенностями ленивого вычисления, которые проявляются в том, что написанная на первый взгляд через хвостовые вызовы функция на самом деле будет падать с переполнением стека. И это связанно именно с ленивым вычислением, а не с хвостовой рекурсией (внимательно смотрим первый комментарий):
http://muaddibspace.blogspot.c... st-in.html
0
11.09.2011, 05:20
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.09.2011, 05:20
Помогаю со студенческими работами здесь

Найти минимальное значение функции на заданном интервале
х изменяется в интервале -15 до 12 необходимо минимальное значение найти. y=(x-9)! -8&lt;=x&lt;=3...

Найти наименьшее положительное значение функции и соответствующее значение аргумента
как найти наименьшее положительное значение функции и соответствующий х? (т.е. каждый шаг h новое...

Вычислить и вывести на экран значение функции на заданном интервале
Помогите Плиз))) задача во вложение. Ознакомьтесь, пожалуйста, с правилами форума. п. 5.18...

Найти и вывести среднее арифметическое значение функции на заданном интервале.
Y=cos(a - x 2 ) +b x 2 (x изменяется от 1 до 3 с шагом 0.3) Найти и вывести среднее...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru