Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Реверт очереди за линейное время / 25 сообщений из 43, страница 1 из 2
  1  все
11.10.2010, 15:52
    #36892896
umniaxa
umniaxa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Подскажите, как обернуть очередь за линейное время?

Более подробно: на вход подается список, [1,2,3,4] например. На выходе должно получится [4,3,2,1] Использовать можно только! операции чтения с конца в начало и операцию дописывания элемента в начало списка. Программа должна отработать за линейное время
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 16:22
    #36892983
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Рекурсия.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 16:26
    #36892998
umniaxa
umniaxa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Извиняюсь, забыл написать. Свои функции, кроме 2-х оговоренных писать и использовать можно, но они не должны никак использовать рекурсию и основываться на чем-либо кроме 2-х оговоренных функций и лямбда выражений
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 16:33
    #36893025
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Любые лямбда-выражения? Каков язык реализации? Python? Можно прикольнуться и сделать через комбинатор неподвижной точки %))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 16:36
    #36893036
umniaxa
umniaxa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Выполнять собираюсь на F#. Но приемлим любой функциональный язык, Haskel, например
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 17:12
    #36893118
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Эфшарпа нет, есть питон.
Код: plaintext
1.
2.
3.
>>> Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))
>>> reverse = lambda f: lambda l: ([] if l == [] else f(l[ 1 :]) + [l[ 0 ]])
>>> Y(reverse)([ 1 , 2 , 3 , 4 ])
[ 4 ,  3 ,  2 ,  1 ]
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 17:15
    #36893128
umniaxa
umniaxa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Спасибо. Постараюсь разобраться и оттранслировать в том или ином виде на шарпы
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 17:48
    #36893217
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Ещё есть Scheme.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
(require unstable/queue)

(define (reverse-q queue)
  (((lambda (f)
     ((lambda (x)
        (f (lambda (y) ((x x) y))))
      (lambda (x)
        (f (lambda (y) ((x x) y))))))
   (lambda (rev) 
     (lambda (q) 
       (if (queue-empty? q) q
           (let ((x (dequeue! q)))
             (rev q)
             (enqueue! q x))))))
   queue))

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
> (define q (make-queue))
(enqueue! q  1 )
(enqueue! q  2 )
(enqueue! q  3 )
(enqueue! q  4 )
> (reverse-q q)
> (dequeue! q)
 4 
> (dequeue! q)
 3 
> (dequeue! q)
 2 
> (dequeue! q)
 1 
>

Я, впрочем, сильно сомневаюсь, что хотели именно этого. Просто забавный обход ограничения на использование рекурсии.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 17:52
    #36893223
umniaxa
umniaxa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Большое спасибо) Вечером подниму питон поминимуму, разберусь в ваших примерах, надеюсь, что без потери всех условий и роста сложности удастся без проблем портировать.
Еще раз большое спасибо
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 18:18
    #36893273
clihlt
clihlt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
junior idiotЭфшарпа нет, есть питон.
Код: plaintext
1.
2.
3.
>>> Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))
>>> reverse = lambda f: lambda l: ([] if l == [] else f(l[ 1 :]) + [l[ 0 ]])
>>> Y(reverse)([ 1 , 2 , 3 , 4 ])
[ 4 ,  3 ,  2 ,  1 ]


Ох и накрутил )

Не соответствует условию:

umniaxa
Использовать можно только! операции чтения с конца в начало и операцию дописывания элемента в начало списка.


Тут я понимаю на оборот.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 18:26
    #36893287
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Ну да, кручу-верчу, что считать "началом", а что "концом" -- в общем, не принципиально.
Можно и наоборот:
Код: plaintext
>>> reverse = lambda f: lambda l: ([] if l == [] else [l[- 1 ]] + f(l[:- 1 ]))
Результат закономерно тот же.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 18:34
    #36893304
clihlt
clihlt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Формаль ность но всеже :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 23:27
    #36893671
k0rvin
k0rvin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
umniaxaСвои функции, кроме 2-х оговоренных писать и использовать можно, но они не должны никак использовать рекурсию
странное ограничение... а что тогда, цикл?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.10.2010, 23:28
    #36893674
k0rvin
k0rvin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
junior idiotПросто забавный обход ограничения на использование рекурсии.

это не обход, а рекурсия.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2010, 00:21
    #36893705
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
k0rvinэто не обход, а рекурсия.
Формально -- нет.
Комбинатор неподвижной точки как раз и нужен для того, чтобы рекурсивное определение преобразовать в не рекурсивное.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2010, 00:27
    #36893708
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Немного поясню.
Дело в том, что это можно "собрать" в одну строчку:
Код: plaintext
1.
>>> (lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg))))(lambda f: lambda l: ([] if l == [] else [l[- 1 ]] + f(l[:- 1 ])))([ 1 , 2 , 3 , 4 ])
[ 4 ,  3 ,  2 ,  1 ]
То есть, без определения функций вообще. А "рекурсивность" -- это именно свойство определения функции. Нет определения, нет смысла даже говорить о "рекурсии".
В Scheme то же самое.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2010, 01:03
    #36893729
clihlt
clihlt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
junior idiot,

Я не очень шарю в лябда выражениях... но для меня этот пример выглядит, как способ вызова из функции самой себя при условии, что "свое" имя она не знает.
Да и выражение типа "lambda g: ............. " - разве ж это не определение функции ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2010, 01:07
    #36893731
clihlt
clihlt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
clihlt,

О первая ссылка ,что попалась
Тынц

автор
Комбинаторы неподвижной точки позволяют определять анонимные рекурсивные функции.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2010, 08:33
    #36893851
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
clihltдля меня этот пример выглядит, как способ вызова из функции самой себя при условии, что "свое" имя она не знает.
Как она тогда себя вызывает?

clihltДа и выражение типа "lambda g: ............. " - разве ж это не определение функции ?
Скорее запись функции. Чтобы она стала определением , функцию надо поименовать, то есть, строго говоря, "определяется" не сама функция, а её имя, связываясь с конкретным лямбда-выражением.
http://en.wikipedia.org/wiki/Definition]A definition is a passage that explains the meaning of a term (a word, phrase or other set of symbols), or a type of thing. The term to be defined is the definiendum (plural definienda).
Впрочем, это не более чем игра слов. Потому я и сказал, что, видимо, от ТС ждут другого решения.
Хотя ни одного определения рекурсии, в котором не использовалось бы слово "definition", то есть относящегося также и к анонимным функциям, я не нашёл.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2010, 12:42
    #36894436
umniaxa
umniaxa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Поясните пожалуйста еще один момент, я правильно понимаю, что в операции
Код: plaintext
l[:- 1 ]
пусть и неявно используется операция удаления с конца списка? точнее на вход список - а на выход - список без последнего эл-та?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2010, 12:45
    #36894448
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
umniaxa , именно так.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2010, 12:57
    #36894483
umniaxa
umniaxa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Мдя) Тогда к сожалению это и есть то условие - которое делает ваше предложенное решение неприемлимым... сложность задачи как раз и состоит в том, что с любыми списками можно сделать ровно 2 операции: прочитать эл-ты с конца к началу (причем именно прочитать, а не прочитать и удалить) и дописать в существующий список (ну или в некий новый) 1 эл-т в начало
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2010, 12:58
    #36894486
umniaxa
umniaxa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Причем все это за линейное время....
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2010, 13:09
    #36894528
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
umniaxaпрочитать эл-ты с конца к началу (причем именно прочитать, а не прочитать и удалить)
Предположу, что вы таки неверно поняли этот момент условия задачи, так получается совсем нелепица. Очередь -- это вполне чёткая абстракция, на ней определена операция ( dequeue , или иногда pop , хотя это несовсем корректно) " извлечения элемента, который был добавлен раньше всех оставшихся" (называть это "началом" или "концом" -- не принципиально, хотя правильнее, конечно, называть "началом").
Иначе вот какая бессмыслица получается: если элементы не удаляются, а только читаются, то
1) либо очередь сама "помнит" сколько раз был считан крайний элемент и сдвигает счётчик, чтобы в следующий раз выдать следующий элемент; тогда это ничем внешне не отличается от извлечения (удаления элементов);
2) либо можно считывать произвольный элемент очереди в любой момент времени; тогда это не очередь вообще, а список.

Короче, приведите интерфейс этой "очереди"; если он "классический", то предложенное решение (особенно для Scheme -- там вообще один-в-один) вполне корректно с точки зрения используемых операций.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.10.2010, 14:04
    #36894691
umniaxa
umniaxa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Реверт очереди за линейное время
Полностью условие звучит так: Используя только операцию foldr и лямбда выражения ревертнуть список не использую рекурсивных функций за линейное время

foldr f arg работает приблизительно так:
foldr (+) 0 [1,2,3,4] = ((((0+4)+3)+2)+1)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Реверт очереди за линейное время / 25 сообщений из 43, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 529ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1342094]:
 0ms
get settings:
 10ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 172ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 72ms
get tp. blocked users:
 1ms
others: 240ms
total:  529ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]