一道面试题，觉得有更优化解 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道面试题，觉得有更优化解

一道面试题，觉得有更优化解# JobHunting - 待字闺中

r*o2013-12-12 08:12

1 楼

Given a target number and a set of numbers, using only addition,
multiplication, division and subtraction and the set of numbers get as near
to the target as possible
楼主想到的一个解法是用5向递归。具体代码怎么factor才简洁不知道~
function : void getNearest(numbers,target,tempTarget,path,re,visited)
base case :
tempRe = target;

getNearest( .. ,target/current, ...)
getNearest( .. ,target*current, ...)
getNearest( .. ,target+current, ...)
getNearest( .. ,target-current, ...)
getNearest( .. ,target, ...)
呵呵，欢迎大家讨论更简洁的算法！

s*z2013-12-12 08:12

2 楼

可以递归的都可以保存状态, 推荐用DP~~~

l*82013-12-12 08:12

3 楼

数字可以重用吗？

near

【在 r**********o 的大作中提到】

: Given a target number and a set of numbers, using only addition,
: multiplication, division and subtraction and the set of numbers get as near
: to the target as possible
: 楼主想到的一个解法是用5向递归。具体代码怎么factor才简洁不知道~
: function : void getNearest(numbers,target,tempTarget,path,re,visited)
: base case :
: tempRe = target;
:
: getNearest( .. ,target/current, ...)
: getNearest( .. ,target*current, ...)

a*02013-12-12 08:12

4 楼

dp找钱那题的引申吧

near

【在 r**********o 的大作中提到】

x*n2013-12-12 08:12

5 楼

It seems that more constraints will be needed.
Otherwise, the below recursion is infinite:
function : void getNearest(numbers,target,tempTarget,path,re,visited)
base case :
tempRe = target;

getNearest( .. ,target/current, ...)
getNearest( .. ,target*current, ...)
getNearest( .. ,target+current, ...)
getNearest( .. ,target-current, ...)
getNearest( .. ,target, ...) <========== Infinite recursion