Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Lisp
Перезагрузить страницу Необходимо оптимизировать программу так чтоб она работала с четырехзначными числами
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
dudeviper dudeviper вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 21.11.2008
По умолчанию Необходимо оптимизировать программу так чтоб она работала с четырехзначными числами - 30.11.2008, 14:53

Необходимо оптимизировать программу так чтоб она работала с четырехзначными числами(с числами больше 4000 выдает ошибку MEMORY FULL), если не возможно то объяснить почему.
Вот сама задача
Сформировать список простых множителей данного числа

Код:
(defun simple(m l)
    (cond     ((null l) t) ((= 0 (rem m (car l))) nil)
        (t (simple m (cdr l)))))
(defun search (n m)
    (if (= 2 m) (setq tmp nil) (setq tmp (search n (- m 1))))
    (cond ((and (= 0 (rem n m)) (simple m tmp)) (cons m tmp)) (t tmp)))
(defun find (n)(search n n))

(find 3500)

(7 5 2)
прошу вас не оставаться равнодушными
Ответить с цитированием
  (#2 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 30.11.2008, 16:21

Во-первых, укажите точное название и версию реализации Лиспа.

Проблема, которую я вижу, состоит в том, что функция SEARCH использует неконцевую рекурсию и требует линейного по N стека. Можно ее переписать так:

Код:
(defun search-prime-divisors-from (n m found)
  (if (>= m n)
      found
      (search-prime-divisors-from n (+ m 1)
                                  (if (and (= 0 (rem n m)) (simple m found))
                                      (cons m found)
                                      found))))

(defun find-prime-divisors (n)
  (search-prime-divisors-from n 2 nil))
Ответить с цитированием
  (#3 (permalink)) Старый
dudeviper dudeviper вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 21.11.2008
По умолчанию 30.11.2008, 20:55

Программа создавалась для MULISP-85 если не ошибся с годом.
В вашей версии программы, уважаемый Alexey Dejneka, программа работает с числами примерно до 5300, неужели это зависит от количества выделяемой Mulispу памяти?
Ответить с цитированием
  (#4 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 30.11.2008, 21:58

Где ж вы такое старье находите...

Похоже, что muLISP не умеет заменять концевую рекурсию на итерацию, в результате программа сталкивается с ограничением на размер стека. Можно ей помочь: использовать итерацию более явно.

Код:
(defun find-prime-divisors (n)
  ((lambda (found m)
     (loop
        ((> m n) found)
        (if (and (= 0 (rem n m)) (simple m found))
            (setq found (cons m found)))
        (setq m (+ m 1))))
   nil 2))
Ответить с цитированием
  (#5 (permalink)) Старый
Lisenok Lisenok вне форума
Member
 
Сообщений: 443
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.01.2007
По умолчанию 01.12.2008, 14:06

Цитата:
Где ж вы такое старье находите...
Оффтоп, конечно, но, как правило, такие старые компиляторы есть в универах их и искать не надо. Именно такие компиляторы, интерпретаторы дают в универе для решения лабораторных!
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
dudeviper dudeviper вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 21.11.2008
По умолчанию 01.12.2008, 16:53

Спасибо Огромное, без Вас я бы никак... Преподаватель наконец-то сдался и зачел Лисп.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Необходимо написать программу для ЖКХ vladeeque Задания за деньги 4 26.04.2011 16:28
Как создать программу шифрования чтоб в ней присутствовали метод цезаря сеня Delphi 1 20.04.2011 21:38
Необходимо написать программу проверки емейлов. romtitar Работа 0 17.03.2011 11:56
Необходимо заполнить одномерный массив случайными числами Irenka Visual Basic 2 14.03.2011 19:18
Как написать программу в С++ что бы работала в Delphi mazila406 Вопросы начинающих программистов 2 22.11.2010 05:23
Разработать программу для реализации указанных действий над целыми числами Juli.ya92 Вопросы начинающих программистов 5 26.09.2010 22:45
Необходимо на Lisp написать программу olik567 Lisp 0 07.05.2009 19:42
Можно ли сделать чтоб программу нельзя было запустить 2 раза vain Visual C++ 26 11.07.2006 15:56
Необходимо вывести данные в отчете, таким образом, чтоб все выглядело одинаков TOPT Delphi 8 11.02.2006 18:41
Как оптимизировать написанную программу вручную progzz Вопросы начинающих программистов 25 16.11.2005 04:28
Как сделать чтоб написанная мной програмка работала без помощи Borlan C++ Builder Anonymous C++ Builder 9 29.12.2003 14:16
Какими именно знаниями необходимо владеть чтоб начать "рубить" DirectX Tox Программирование графики 2 23.11.2003 15:00



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов