w********s
发帖数: 1570 | 1 input: 4个数字, a,b,c,d
output: 所有结果=24的等式，例如:24=(a+b)*(c*d) |
l*********8
发帖数: 4642 | 2 很繁琐，如果不是事先写过，很难在45分钟内写好。 |
l*********8
发帖数: 4642 | 3 单单把二叉树输出为算术表达式（没有冗余括号》， 就可以作为面试coding的一道题
目了。 |
s*********5
发帖数: 514 | 4 如果只有4个数字的话，一共24个顺序X64种变化，brute force OK了吧 |
s*********5
发帖数: 514 | 5 如果只有4个数字的话，一共24个顺序X64种变化，brute force OK了吧 |
s*********5
发帖数: 514 | 6 如果只有4个数字的话，一共24个顺序X64种变化，brute force OK了吧 |
p*****2
发帖数: 21240 | |
g**********y
发帖数: 14569 | 8 准备面试的标准应该做到可以写，不是真写完，但应该把框架写出来。
写成接近可运行的程序，45分钟要求有点高，但也不算太离谱。那次谁贴的Amazon的计
算机多个加油站之间距离的，我觉得比这个难多了。大家在版上讨论了很久。碰上那种
题，绝对是人品问题了。
【在 w********s 的大作中提到】
: input: 4个数字, a,b,c,d
: output: 所有结果=24的等式，例如:24=(a+b)*(c*d)
|
m***n
发帖数: 2154 | 9 a*(b+c)/d
这个还要考虑括号吧。
【在 s*********5 的大作中提到】
: 如果只有4个数字的话，一共24个顺序X64种变化，brute force OK了吧
|
l*********8
发帖数: 4642 | 10 In addition, the output should not contains duplications even if there are
duplicated numbers.
For example,
6 6 6 6
we don't want to output 6+6+6+6 for 24 times.
【在 m***n 的大作中提到】
: a*(b+c)/d
: 这个还要考虑括号吧。
|
|
|
p*****2
发帖数: 21240 | 11
明白什么意思了。
【在 m***n 的大作中提到】
: a*(b+c)/d
: 这个还要考虑括号吧。
|
m***n
发帖数: 2154 | 12 这个好办，直接表达式压入set就行了。
其实a*(b+c)/d的情况也是可以解决的。不用考虑括号。
a*(b+c)/d 等同于
b+c*a/d 每次evaluate表达式直接从左往右evaluate.
那么只要穷举了所有的abcd排列， 然后3个符号位置组合就行了。
【在 l*********8 的大作中提到】
: In addition, the output should not contains duplications even if there are
: duplicated numbers.
: For example,
: 6 6 6 6
: we don't want to output 6+6+6+6 for 24 times.
|
l*********8
发帖数: 4642 | 13 if depends on if the interviewer thinks
a*(b+c)/d and (b+c)*a/d are different or not.
【在 m***n 的大作中提到】
: 这个好办，直接表达式压入set就行了。
: 其实a*(b+c)/d的情况也是可以解决的。不用考虑括号。
: a*(b+c)/d 等同于
: b+c*a/d 每次evaluate表达式直接从左往右evaluate.
: 那么只要穷举了所有的abcd排列， 然后3个符号位置组合就行了。
|
y****n
发帖数: 743 | 14 粗想了一下，我会把算24列成两个公式：
((a +-*/ b) +-*/ c) +-*/ d
或者 (a +- b) */ (c +- d)
这样循环穷举可在短时间搞定。 |
c****p
发帖数: 6474 | 15 我以前尝试用MATLAB写过，不太成功
基本思路是递归，把四元变成三元，把三元变成两元。
但是这样的不可能找到形如(a+b) * (c+d)这样的解。
另外，因为浮点数精度的问题，对于3 3 7 7 可能找不到(3 + 3/7) * 7这样的解
【在 w********s 的大作中提到】
: input: 4个数字, a,b,c,d
: output: 所有结果=24的等式，例如:24=(a+b)*(c*d)
|
l*********8
发帖数: 4642 | 16 how about a*/b +- c*/d
【在 y****n 的大作中提到】
: 粗想了一下，我会把算24列成两个公式：
: ((a +-*/ b) +-*/ c) +-*/ d
: 或者 (a +- b) */ (c +- d)
: 这样循环穷举可在短时间搞定。
|
g*********e
发帖数: 14401 | |
h****e
发帖数: 928 | 18 我觉得用C++/Java基本上写不出来，但是用Perl、Python、Ruby
之类的scripting languages可能可以。 |
y****n
发帖数: 743 | 19 good catch！ 我当时想的不够严谨，可能还有漏掉的情况。
【在 l*********8 的大作中提到】
: how about a*/b +- c*/d
|
b******u
发帖数: 81 | 20 暴力解. Binary Tree.
3+5+7+9
(3+9)*(7-5)
5*9-3*7
9*(5-7/3)
2+4+8+10
(4*10+8)/2
(10-4)*8/2
2-10+4*8
4*8-10+2
2-(10-4*8)
2*10-(4-8)
(2+10)/(4/8)
(2+10)*8/4
(8/4+10)*2
2*10+8-4
(2+10)*8/4
4*10-2*8
(2*8-10)*4
4*(10-8/2)
8/2*(10-4)
(10-4)/2*8
8/(2/(10-4))
(2+10)/4*8
8/(4/(2+10))
(10-2)*4-8
(10-4)/(2/8)
(3/7+3)*7
5*(5-1/5) |
|
|
l*********8
发帖数: 4642 | 21 你这个答案看起来不错啊。
你的程序是怎么知道9*5-7*3只是5*9-3*7的trivial variation的？
【在 b******u 的大作中提到】
: 暴力解. Binary Tree.
: 3+5+7+9
: (3+9)*(7-5)
: 5*9-3*7
: 9*(5-7/3)
: 2+4+8+10
: (4*10+8)/2
: (10-4)*8/2
: 2-10+4*8
: 4*8-10+2
|
l*********8
发帖数: 4642 | 22 为什么输出两次(2+10)*8/4 ？
【在 b******u 的大作中提到】
: 暴力解. Binary Tree.
: 3+5+7+9
: (3+9)*(7-5)
: 5*9-3*7
: 9*(5-7/3)
: 2+4+8+10
: (4*10+8)/2
: (10-4)*8/2
: 2-10+4*8
: 4*8-10+2
|
b******u
发帖数: 81 | 23 用 bool IsSameFor24 ( OperationNode node1, OperationNode node2 )
对 + *， 检查左右互换后是否相同。
也检查了 a + ( b + c ) = ( a + c ) + b 的情况。
有五种TREE
(a - b) - (c - d)
a - ( b - ( c -d ) )
a - ( (b - c) -d )
((a - b) - c) -d
(a - (b - c)) -d
【在 l*********8 的大作中提到】
: 你这个答案看起来不错啊。
: 你的程序是怎么知道9*5-7*3只是5*9-3*7的trivial variation的？
|
l*********8
发帖数: 4642 | 24 你是把每个符合条件的答案存起来。生成新答案的时候，和已有答案逐个相比吧？
那为什么输出两次(2+10)*8/4 ？
【在 b******u 的大作中提到】
: 用 bool IsSameFor24 ( OperationNode node1, OperationNode node2 )
: 对 + *， 检查左右互换后是否相同。
: 也检查了 a + ( b + c ) = ( a + c ) + b 的情况。
: 有五种TREE
: (a - b) - (c - d)
: a - ( b - ( c -d ) )
: a - ( (b - c) -d )
: ((a - b) - c) -d
: (a - (b - c)) -d
:
|
b******u
发帖数: 81 | 25 是的。
我猜原因是 有两个TREE 31 和 22. TREE 本身不同，但结果相同。
（ （ 2 + 10 ） * 8 ） /4
（ （ 2 + 10 ） * ( 8 /4 )
【在 l*********8 的大作中提到】
: 你是把每个符合条件的答案存起来。生成新答案的时候，和已有答案逐个相比吧？
: 那为什么输出两次(2+10)*8/4 ？
|
l*********8
发帖数: 4642 | 26 知道了。然后你输出的时候去掉了不必要的括号（的确应该），就造成一模一样的两个
答案了。
【在 b******u 的大作中提到】
: 是的。
: 我猜原因是 有两个TREE 31 和 22. TREE 本身不同，但结果相同。
: （ （ 2 + 10 ） * 8 ） /4
: （ （ 2 + 10 ） * ( 8 /4 )
|
r*****g
发帖数: 478 | 27 That's an interesting thought..
用scripting L的不同在哪里？
【在 h****e 的大作中提到】
: 我觉得用C++/Java基本上写不出来，但是用Perl、Python、Ruby
: 之类的scripting languages可能可以。
|
l***i
发帖数: 1309 | 28 It is easier if you use postfix or prefix notation, then you have no ( ) to
deal with, 3 operators and 4 operands, 7! is small
just write eval_postfix() and in the function check whether it is a valid
postfix or not |
h****e
发帖数: 928 | 29 Scripting languages的强项在于可以做真正的very-high level programming.
举Ruby为例：
- 生成所有的permutations:
a=[1,2,3]
a.permutation.to_a
- Set的操作:
require 'set'
s1 = Set.new [1, 2]
s1.merge([2, 6])
很多在C++/Java里面要一大段代码的，在这些scripting中一句话就解决了。
Google的Peter Norvig有一篇非常经典的文章，就是讲如何只用一小页的
Python代码来解决所有的Sudoku:
http://norvig.com/sudoku.html
【在 r*****g 的大作中提到】
: That's an interesting thought..
: 用scripting L的不同在哪里？
|
x*******5
发帖数: 152 | 30 这个编程之美第一章16题是答案, python代码如下
from __future__ import division
def Point_Game(n,numbers,result,Value):
"Implement 24-point game"
if n==1:
if math.fabs(numbers[0]-Value)<0.0001:
print result[0]
return True
else: return False
for i in range(n):
for j in range(i+1,n):
a,b=numbers[i],numbers[j]
expa,expb=result[i],result[j]
numbers[j]=numbers[n-1]
result[j]=result[n-1]
result[i]='('+expa+'+'+expb+')'
numbers[i]=a+b
if Point_Game(n-1,numbers,result,Value):
return True
result[i]='('+expa+'-'+expb+')'
numbers[i]=a-b
if Point_Game(n-1,numbers,result,Value):
return True
result[i]='('+expb+'-'+expa+')'
numbers[i]=b-a
if Point_Game(n-1,numbers,result,Value):
return True
result[i]='('+expa+'*'+expb+')'
numbers[i]=a*b
if Point_Game(n-1,numbers,result,Value):
return True
if b:
result[i]='('+expa+'/'+expb+')'
numbers[i]=a/b
if Point_Game(n-1,numbers,result,Value):
return True
if a:
result[i]='('+expb+'/'+expa+')'
numbers[i]=b/a
if Point_Game(n-1,numbers,result,Value):
return True
numbers[i]=a
numbers[j]=b
result[i]=expa
result[j]=expb
return False
测试：
numbers=[6,6,6,6]
results=[]
for n in numbers:
results.append(str(n))
Recur.Point_Game(4, numbers, results, 24)
Output：
(((6+6)+6)+6)
测试： numbers=[1,3,4,6]--->(6/(1-(3/4)))
numbers=[3,3,8,8]-->(8/(3-(8/3)))
numbers=[3,3,7,7]-->(((3/7)+3)*7)
测试用例是google最难算的24点
基本idea是back-tracking，这个程序可以在45分钟内写出来吧，欢迎找bug |
|
|
x*******5
发帖数: 152 | |
