Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Lisp] Интересная задача - NEED HELP! ;-), Ай нид ю хелп :dash1 :sample :wacko  
:(
    Опции темы
dorfe
  Дата 30.9.2007, 12:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 30.9.2007

Репутация: нет
Всего: нет
Я в Лиспе пока ньюб :-(, но стоит такая задача: преобразовать произвольный многоуровневый список вида (a b ((c d) e f) g (h)) в (a b ((c d 2) e f 3) g (h 1) 5), т.е. добавить к каждому подсписку кол-во его элементов, которое должно вычисляться рекурсивно _этой же_ функцией.

Проблема в том, что должна быть _одна_ рекурсивная функция, которая все это делает... Ай нид ю хелп  smile  smile  smile 
PM MAIL   Вверх
adejneka
Дата 30.9.2007, 19:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 105
Регистрация: 8.7.2005
Где: Москва, Россия

Репутация: 2
Всего: 11
Вместо функции (recursive-add-lengths list), которая делает то, что Вы описали, определите функцию (recursive-add-lengths-from list shift), которая добавляет ко всем внутренним спискам, как и прежняя, их длины, а в конец списка верхнего уровня добавляет длину, увеличенную на shift (старая функция является частным случаем новой с SHIFT=0).
PM MAIL   Вверх
dorfe
  Дата 30.9.2007, 23:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 30.9.2007

Репутация: нет
Всего: нет
Гм, спасибо конечно, но не совсем понял: это будет одна функция или две? или одна, но дважды перегруженая? Если можно - кодом, плз.
PM MAIL   Вверх
adejneka
Дата 1.10.2007, 07:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 105
Регистрация: 8.7.2005
Где: Москва, Россия

Репутация: 2
Всего: 11
Цитата
это будет одна функция или две?

Одна.
Цитата
или одна, но дважды перегруженая?

Что это значит?

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

Кстати, не нужно "ю" заменить на "йо"?
PM MAIL   Вверх
mrco
Дата 1.10.2007, 11:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 43
Регистрация: 4.10.2006

Репутация: нет
Всего: 1
Код

(defun ф(сп) (if (listp сп) (append (loop for эл in сп collect (ф эл)) (list (length сп))) сп))


Это сообщение отредактировал(а) mrco - 1.10.2007, 11:57
PM MAIL   Вверх
dorfe
Дата 1.10.2007, 12:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 30.9.2007

Репутация: нет
Всего: нет
2adejneka: да, задачу нужно решить одной рекурсивной функцией.

Цитата

Кстати, не нужно "ю" заменить на "йо"? 


Тут не понял, смотря где smile

mrco, спасибо, вроде то что нужно, т.е. без цикла тут все равно никуда...
PM MAIL   Вверх
adejneka
Дата 1.10.2007, 14:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 105
Регистрация: 8.7.2005
Где: Москва, Россия

Репутация: 2
Всего: 11
Цитата(dorfe @  1.10.2007,  12:28 Найти цитируемый пост)
без цикла тут все равно никуда

Любую программу с циклом можно тривиально переписать с рекурсией. Правда, цикл при этом заменяется вложенной функцией.
PM MAIL   Вверх
VH_
Дата 1.10.2007, 15:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 182
Регистрация: 31.10.2006

Репутация: 1
Всего: 11
Код

(defun F (L)
 (cond
  ((null L) (cons 0 nil))
  (T
   ((lambda (result)
     (append (butlast result) (list (1+ (car (last result)) )))) ; для версий в которых (last) возвращает список
    (cons
     ((lambda (head)
       (if (atom head) head (F head)))
      (car L))
     (F (cdr L)))))))

Код

(defun F (L)
 (cond
  ((null L) (cons 0 nil))
  (T
   ((lambda (result)
     (append (butlast result) (list (1+ (last result) )))) ; для версий в которых (last) возвращает не список
    (cons
     ((lambda (head)
       (if (atom head) head (F head)))
      (car L))
     (F (cdr L)))))))
PM MAIL   Вверх
mrco
Дата 1.10.2007, 19:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 43
Регистрация: 4.10.2006

Репутация: нет
Всего: 1
Цитата(adejneka @  1.10.2007,  14:34 Найти цитируемый пост)
Любую программу с циклом можно тривиально переписать с рекурсией. Правда, цикл при этом заменяется вложенной функцией. 

Достаточно и двухуровневой рекурсии:
Код

(defun ф(сп дл) 
   (cond
      ((null сп) (list дл))
      ((listp сп) (append (list (ф (first сп) 0)) (ф (cdr сп) (+ 1 дл))))
      (t сп)))
PM MAIL   Вверх
adejneka
Дата 1.10.2007, 21:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 105
Регистрация: 8.7.2005
Где: Москва, Россия

Репутация: 2
Всего: 11
Цитата(mrco @  1.10.2007,  11:55 Найти цитируемый пост)

(defun ф(сп) (if (listp сп) (append (loop for эл in сп collect (ф эл)) (list (length сп))) сп))

Здесь есть неприятный момент: делается три прохода по списку верхнего уровня: считается длина списка, собирается список рекурсивных применений Ф, затем он копируется и в конец приписывается длина. Можно собирать список применений в обратном порядке, а затем его инвертировать, либо воспользоваться нестандартным макросом COLLECT, имеющимся, например, в CMUCL и SBCL:
Код

(defun ф(сп)
  (if (listp сп)
      (let ((result '())
            (length 0))
        (dolist (эл сп)
          (push (ф эл) result)
          (incf length))
        (push length result)
        (nreverse result))
      сп))

(defun ф(сп)
  (if (listp сп)
      (sb-int:collect ((result)
                       (len 0 +))
        (dolist (эл сп)
          (result (ф эл))
          (len 1))
        (result (len))
        (result))
      сп))
PM MAIL   Вверх
dorfe
Дата 1.10.2007, 21:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 30.9.2007

Репутация: нет
Всего: нет
mrco, такой вариант вроде не подходит - выдает (a b ((c d 2) e f 3) g (h 1) 10 ) например  smile 
Спасибо за все остальные варианты!  smile 
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1145 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.