2至10个数，使用+，-，×，/，并运算=常数的程序

无心人

嗯，需要增加一个运算 假设运算符是T aTb=a * 10 + b 并且适合于左结合，并不满足交换律

mathe

这个问题的规模还是小了些.我觉得设计良好的程序应该可以解决20个数的问题

gxqcn

11# 无心人 还需加上：紧挨 T 的两边是数，不得间隔其它运算符。

mathe

仅10个数可以第一步先确定所有的T操作. 最多9个位置,每个位置是否有T操作,总共$2^9=512$种情况,对于计算机不是大数目

wayne

嗯，需要增加一个运算 假设运算符是T aTb=a * 10 + b 并且适合于左结合，并不满足交换律 无心人 发表于 2009-9-16 19:25

学习了,...

sheng_jianguo

嗯，需要增加一个运算 假设运算符是T aTb=a * 10 + b 并且适合于左结合，并不满足交换律 无心人 发表于 2009-9-16 19:25

有点问题，应该是 假设运算符是T aTb=a * 10 ^n+ b 其中n是b的字符个数。

gxqcn

楼上的很细心！ 这样看来，这个“T”运算符的行为定义就会比较复杂了。 不过，用 mathe 在 14# 说的方法就可完全避免引入该运算符了。

mathe

如果仅仅10个数,计算方法可以很简单. i)采用我在14#的方法,先分成最多512种情况 ii)选择某个较大素数p,将所有运算采用模p运算,避免引入分数,整数计算溢出或者浮点精度等问题 iii)采用动态规划,计算从第i个数到第j个数之间的数进行运算可以产生的数据的集合.

sheng_jianguo

如果仅仅10个数,计算方法可以很简单. i)采用我在14#的方法,先分成最多512种情况 ii)选择某个较大素数p,将所有运算采用模p运算,避免引入分数,整数计算溢出或者浮点精度等问题 iii)采用动态规划,计算从第i个数到第j ... mathe 发表于 2009-9-18 10:05

谢谢mathe的指点！ 但我还有一些疑问请教mathe： 您的算法中，是否所有可能的情况都进行计算，还是算前判别不用算的就不算了。 由于只有10个数，每次只运算9次，用双精度变量应能避免整数计算溢出或者浮点精度问题（当然除数=0要判别）。 如果所有可能的情况都进行计算，是否可以直接采用“暴力法”，即用循环语句将10个数和5种运算的所有情况进行计算，这样做会有什么问题？

mathe

穷举所有情况也不是那么容易的,因为你的题目中提议添加括号. 而采用动态规划的好处是有些子表达式被多个表达式同时使用,它们的值不需要重复计算.另外,有些不同的子表达式值相同,在同更外层的数据进行运行时也可以避免一些运算. 当然还有更加好一点的方法: 我们可以将表达式部分数据移动到等式右边(所有操作符变成逆操作符), 然后需要判断两个子表达式是否相等. 分别对两边子表达式使用不同操作符的情况计算所有可能的取值,得到两个集合.然后判断两个集合是否有交集(通过Hash表查找).这样可以更快.