На бесконечной лестнице находится робот у которого есть API - подняться вверх. Однако не всякая попытка поднятся вверх заканчивается успехом - робот может как поднятся на верх на 1 ступеньку - функция API вернёт 1 - или съехать ниже на 1 ступеньку - возвращаемое значение -1.
Не используя локальных переменных, циклов и формальных параметров функции написать алгоритм, поднимающий гарантированно робота на 10 ступеней вверх
Не используя локальных переменных, циклов и формальных параметров функции написать алгоритм, поднимающий гарантированно робота на 10 ступеней вверх
Задачка скорее разминка для хвоста в целях попрактиковаться на clojure
18 комментариев:
Очевидно, что никаких "гарантированно" быть при такой постановке задачи не может. Достаточно рассмотреть случай, когда вызов всегда обламывается... Никакой алгоритм не спасёт...
Нужна вероятностная формулировка условия.
void upOneStep(){
if (!robotApiUp()){
upOneStep();
upOneStep();
}
}
void main(){
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
}
http://gist.github.com/305420
(defn up []
(int (Math/pow -1 (inc (.nextInt (new java.util.Random) 2)))))
(defn up-10 []
(->> (repeatedly up)
(take 10)
(apply +)))
(first (filter (partial = 10) (repeatedly up-10)))
Прикольная задача, но никто не дал её решения на Java. Вот моё решение:
http://code.google.com/p/khomutetskiy-project/source/browse/trunk/UNIVER/src/ru/susu/tasks/Robot.java
Роботу дается слегка больший шанс шагнуть вперед, чем назад. Иначе переполнение стека возникает.
Конечно, это не хвостовая рекурсия :-)
@Михаил - ваше решение на java ничем принципиально не отличается от решения migmit'а - решение, для любого императивного языка - такое же можно написать и на javascript, perl, python и т.п, и на clojure в т.ч.
Другое дело - решение Захарджан'а - true functionally programming approach - и действительно бомба.
@Захарджан:
идея - супер, но в реализации ошибка:
попробуйте проверить алгоритм с такую заранее известной последовательностью движений робота: [-1 1 1]
т.е.
(def position (atom 0))
(def movements (cycle [-1 1 1]))
(defn up []
( do
(reset! position (inc @position))
(nth movements @position)
)
)
Владимир, интересна всё таки формальная постановка задачи ^^'
@e.v.e
можно считать, что вероятность подняться у робота больше, чем опустится - нмв - это разумное предположение.
@Владимир Долженко,
а гарантировано, что означает?
с единичной вероятностью?
что робот окажется на ровно на 10 ступенек выше, чем был в начале движения.
@Владимир Долженко
Принципиальное отличие состоит в том, что мое решение работает, в отличии от решения migmit(по-моему это большая разница). Принципиальное ограничение моего решения - это глубина стека рекурсии. На данный момент я не могу сказать можно ли сделать имитацию хвостовой рекурсии на императивном языке при заданных ограничениях на использование циклов, переменных и параметров функции. Я подумаю на этот счет :-)
Кстати, именно сейчас изучаю ФП по видео-лекциям на http://www.intuit.ru/department/pl/funcprog/.
@Михаил
может тогда объясните смысл условия
if (trulyUp() == 1) ?
если единственная точка выхода из trulyUp это return 1;
@Владимир Долженко
Тупанул... Решение у migmit ведь верное. Изменил свой код.
Спасибо, автор, ты наставил меня на путь истинный. Лови однострочник:
http://gist.github.com/305420
(first (filter (partial = 10) (iterate #(+ % (up)) 0)))
@Захарджан
безусловно - эта идея - the best, если чуть приукрасить код (на 1 оператор меньше)
(take-while #(< % 10) (iterate #(+ % (up)) 0))
Хотел быстро написать однострочник на python. Ан нет, одной функции для реализации чистого ФП не хватает. Но если бы она была, выглядело это б примерно так.
map(lambda i:i, takewhile(lambda x: x <10, ireduce(lambda x,y: x+y, imap(lambda x: x(), repeat(api)))))
Где imap, repeat, takewhile - функции модуля itertools, а ireduce определяется следующим образом:
def ireduce(func, iterable, init=None):
if init is None:
iterable = iter(iterable)
curr = iterable.next()
else:
curr = init
for x in iterable:
curr = func(curr, x)
yield curr
ps правда стоит учесть что эти функции в любом случае реализуются через циклы, либо на уровне библиотек питона, либо на уровне c-реализации.
До кучи haskell вариант:
import System.Random
import Control.Monad
up = do
r <- randomIO
print ("doing up: " ++ show(r :: Bool))
return r
upmultiM 0 = return ()
upmultiM steps = do
u <- up
if u then upmultiM (steps - 1) else upmultiM (steps + 1)
main = upmultiM 10
Отправить комментарий