一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 511|回复: 3
收起左侧

[算法题] 大家来刷题:求问一道coding题,最近被问到了...

[复制链接] |试试Instant~ |关注本帖
pennboy 发表于 2016-1-14 12:24:22 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 pennboy 于 2016-1-14 23:57 编辑


用string形式给一个含有x,y,+,-,*,/,(, )以及用a,b,c,d等表示的数字的表达式,比如:

y = (a*x) + b

要求写一个程序输出x的表达式: x = (y-b)/a;

其中x可能出现多次,比如:y = (x+a)/b + x*c;

PS: 限制是y是linear in terms of x;

面试当时想的是先简化表达式,将所有含x的terms合并,然后parse这个string生成一
个以y为root的eval tree,然后找到x所在的node,将这个eval tree改造成以这个node
为root的eval tree,然后重建表达式,这样结果就会是x=ay-b之类的形式,不过
interviewer当时
不置可否,我当时也没写出来具体code,求大家帮忙看看有没有什么简明的解法。谢了。
dukemon7 发表于 2016-1-14 20:00:21 | 显示全部楼层
给两个x的值,计算表达式的值,然后根据两组(x,y)直接写出直线就可以了
回复 支持 反对

使用道具 举报

 楼主| pennboy 发表于 2016-1-14 23:58:52 | 显示全部楼层
dukemon7 发表于 2016-1-14 20:00
给两个x的值,计算表达式的值,然后根据两组(x,y)直接写出直线就可以了

啊是我原题表述不清,这个是无法用代入值来求的,我把题目已经改好了。
回复 支持 反对

使用道具 举报

stellari 发表于 2016-1-15 09:52:51 | 显示全部楼层
你也提到了,如果原函数是y = kx + b,那么转换以后的结果必是x = y/k-b/k

那么,假设我们现在已经有一个算法A能够合并含x的项,那么A稍作改动,同样也能够合并不含x的项,因此,我们可以由算法A得到y = kx + b的形式。既然k和b两个字符串都已经知道了,从这里我们就能直接写出x = y/k - b/k。当然,这个形式未必是最简,所以可能还要想办法进一步化简。

面试官不置可否可能是觉得你的答案和他的想法不同,但是他又不能马上判断是否有问题。抑或他可能觉得eval tree这个东西用得没有必要。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 05:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表