Вот...хотелось задачки порешать.
После ProjectEuler оказалось - ни о чем. Самое сложное - ждать 10 минут проверки решения...
Разве что задачка про робота неплоха, требует немного подумать, вполне может подойти для интервью.
Вот решение на питоне :
def google_test_robot():
d={}
d[(0,0)]=1
def helper_(a,b):
if a<0 or b<0:
return 0;
if not d.has_key((a,b)):
d[(a,b)] = helper_(a-1,b)+helper_(a,b-1)
return d[(a,b)]
print helper_(41,44)
несмотря на "меморизацию" :) решение далеко не самое оптимальное как с точки зрения используемой памяти так и с точки зрения скорости. Правильнее было бы идти по диагонали...но так писать дольше.
И уж совсем правильнее было бы использовать так называемые Catalan numbers (ну это если повезло и поле квадратное)
Комментариев нет:
Отправить комментарий