ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Реверт очереди за линейное время
25 сообщений из 43, страница 1 из 2
  1  все
Реверт очереди за линейное время
    #36892896
umniaxa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
umniaxa
Гость
Подскажите, как обернуть очередь за линейное время?

Более подробно: на вход подается список, [1,2,3,4] например. На выходе должно получится [4,3,2,1] Использовать можно только! операции чтения с конца в начало и операцию дописывания элемента в начало списка. Программа должна отработать за линейное время
...
Рейтинг: 0 / 0
11.10.2010, 15:52
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36892983
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
Рекурсия.
...
Рейтинг: 0 / 0
11.10.2010, 16:22
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36892998
umniaxa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
umniaxa
Гость
Извиняюсь, забыл написать. Свои функции, кроме 2-х оговоренных писать и использовать можно, но они не должны никак использовать рекурсию и основываться на чем-либо кроме 2-х оговоренных функций и лямбда выражений
...
Рейтинг: 0 / 0
11.10.2010, 16:26
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36893025
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Любые лямбда-выражения? Каков язык реализации? Python? Можно прикольнуться и сделать через комбинатор неподвижной точки %))
...
Рейтинг: 0 / 0
11.10.2010, 16:33
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36893036
umniaxa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
umniaxa
Гость
Выполнять собираюсь на F#. Но приемлим любой функциональный язык, Haskel, например
...
Рейтинг: 0 / 0
11.10.2010, 16:36
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #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:12
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36893128
umniaxa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
umniaxa
Гость
Спасибо. Постараюсь разобраться и оттранслировать в том или ином виде на шарпы
...
Рейтинг: 0 / 0
11.10.2010, 17:15
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #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:48
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36893223
umniaxa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
umniaxa
Гость
Большое спасибо) Вечером подниму питон поминимуму, разберусь в ваших примерах, надеюсь, что без потери всех условий и роста сложности удастся без проблем портировать.
Еще раз большое спасибо
...
Рейтинг: 0 / 0
11.10.2010, 17:52
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #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:18
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #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:26
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36893304
clihlt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
clihlt
Участник
Формаль ность но всеже :)
...
Рейтинг: 0 / 0
11.10.2010, 18:34
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36893671
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k0rvin
Участник
umniaxaСвои функции, кроме 2-х оговоренных писать и использовать можно, но они не должны никак использовать рекурсию
странное ограничение... а что тогда, цикл?
...
Рейтинг: 0 / 0
11.10.2010, 23:27
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36893674
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k0rvin
Участник
junior idiotПросто забавный обход ограничения на использование рекурсии.

это не обход, а рекурсия.
...
Рейтинг: 0 / 0
11.10.2010, 23:28
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36893705
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
k0rvinэто не обход, а рекурсия.
Формально -- нет.
Комбинатор неподвижной точки как раз и нужен для того, чтобы рекурсивное определение преобразовать в не рекурсивное.
...
Рейтинг: 0 / 0
12.10.2010, 00:21
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #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, 00:27
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36893729
clihlt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
clihlt
Участник
junior idiot,

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

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

автор
Комбинаторы неподвижной точки позволяют определять анонимные рекурсивные функции.
...
Рейтинг: 0 / 0
12.10.2010, 01:07
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #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, 08:33
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36894436
umniaxa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
umniaxa
Гость
Поясните пожалуйста еще один момент, я правильно понимаю, что в операции
Код: plaintext
l[:- 1 ]
пусть и неявно используется операция удаления с конца списка? точнее на вход список - а на выход - список без последнего эл-та?
...
Рейтинг: 0 / 0
12.10.2010, 12:42
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36894448
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
umniaxa , именно так.
...
Рейтинг: 0 / 0
12.10.2010, 12:45
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36894483
umniaxa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
umniaxa
Гость
Мдя) Тогда к сожалению это и есть то условие - которое делает ваше предложенное решение неприемлимым... сложность задачи как раз и состоит в том, что с любыми списками можно сделать ровно 2 операции: прочитать эл-ты с конца к началу (причем именно прочитать, а не прочитать и удалить) и дописать в существующий список (ну или в некий новый) 1 эл-т в начало
...
Рейтинг: 0 / 0
12.10.2010, 12:57
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36894486
umniaxa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
umniaxa
Гость
Причем все это за линейное время....
...
Рейтинг: 0 / 0
12.10.2010, 12:58
| Ответить | Цитировать | Написать  
Реверт очереди за линейное время
    #36894528
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
umniaxaпрочитать эл-ты с конца к началу (причем именно прочитать, а не прочитать и удалить)
Предположу, что вы таки неверно поняли этот момент условия задачи, так получается совсем нелепица. Очередь -- это вполне чёткая абстракция, на ней определена операция ( dequeue , или иногда pop , хотя это несовсем корректно) " извлечения элемента, который был добавлен раньше всех оставшихся" (называть это "началом" или "концом" -- не принципиально, хотя правильнее, конечно, называть "началом").
Иначе вот какая бессмыслица получается: если элементы не удаляются, а только читаются, то
1) либо очередь сама "помнит" сколько раз был считан крайний элемент и сдвигает счётчик, чтобы в следующий раз выдать следующий элемент; тогда это ничем внешне не отличается от извлечения (удаления элементов);
2) либо можно считывать произвольный элемент очереди в любой момент времени; тогда это не очередь вообще, а список.

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

foldr f arg работает приблизительно так:
foldr (+) 0 [1,2,3,4] = ((((0+4)+3)+2)+1)
...
Рейтинг: 0 / 0
12.10.2010, 14:04
| Ответить | Цитировать | Написать  
25 сообщений из 43, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Реверт очереди за линейное время
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36893036&tid=1342094]:
 0ms
get settings:
 8ms
get forum list:
 14ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 156ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 68ms
get tp. blocked users:
 1ms
others: 198ms
total:  458ms
созд. / загр.: 458ms
x
x
Закрыть


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