主题:关于利用混合加减法算最小结果的题目!
孤狼5926
[专家分:0] 发布于 2005-11-07 11:20:00
从键盘输入四个自然数,请用这四个自然数组成一个不含括号的加减法混合运算题,使该题所得结果最小(但不能小于零,而且运算的中间结果也不能小于零)。输出格式要符合数学算式要求,如有多种答案,只需输出一种符合要求的表达式。
例如: 输入 15 6 12 4
输出: 15-12+4-6=1
回复列表 (共10个回复)
沙发
moz [专家分:37620] 发布于 2005-11-06 18:31:00
可以设置两个组合
A组:被减数
B组:减数
把这四个数所有的组合情况分别放到这两个组中去计算结果比较就是了。
板凳
moz [专家分:37620] 发布于 2005-11-06 18:54:00
deflng a-z
dim s&(4)
input "a,b,c,d:",s(1),s(2),s(3),s(4)
minsum=s(1)+s(2)+s(3)+s(4)
利用排列函数吧:
x$="1234"
do
for i=1 to 4
sum=0
y$=""
for j=1 to i
sum=sum+s(val(mid$(x$,j,1)))
if y$<>"" then y$=y$+"+"
y$=y$+str$(s(val(mid$(x$,j,1))))
next
for g=(i+1) to 4
if y$<>"" then y$=y$+"-"
sum=sum-s(val(mid$(x$,g,1)))
y$=y$+str$(s(val(mid$(x$,g,1))))
next
y$=y$+"="+str$(sum)
if sum>=0 and sum<minsum then
minsum=sum
miny$=y$
end if
next
x$=nextpl$(x$)
loop until x$=""
print miny$
end
排列函数:
function nextpl$(a$)
l=len(a$)
for e=(l-1) to 1 step -1 '找不合适的位置 e
if mid$(a$,e,1)<mid$(a$,e+1,1) then exit for
next
if e<1 then
a$=""
exit function
endif
FOR i = l TO (e + 1) STEP -1 '找需要交换的位置 i
IF MID$(a$, i, 1) > MID$(a$, e, 1) THEN EXIT FOR
NEXT
b$ = MID$(a$, i, 1) '交换字符
MID$(a$, i, 1) = MID$(a$, e, 1)
MID$(a$, e, 1) = b$
FOR i = (e + 1) TO (l + e + 1) \ 2 '对后面段的字符排顺序
j = l + e + 1 - i
b$ = MID$(a$, i, 1)
MID$(a$, i, 1) = MID$(a$, j, 1)
MID$(a$, j, 1) = b$
NEXT
nextpl$=a$
end function
没经过试验过,自己试试行不行吧。近来我的脑袋也不太行了。
当然还可以弄更简洁一点的办法的。
3 楼
moz [专家分:37620] 发布于 2005-11-06 19:14:00
还得麻烦你要把主题改成:
主题:关于利用混合加减法算最小结果的题目!
那张贴已经给我删掉了。
4 楼
孤狼5926 [专家分:0] 发布于 2005-11-07 11:23:00
感谢moz的答复,程序有些地方还没有完全看懂,我慢慢分析一下,如有疑问,还要在来请教您!不胜感谢!!!
5 楼
moz [专家分:37620] 发布于 2005-11-07 18:00:00
为了你这个题目
我又做了一个组合函数出来了
又把程序改了一下:
deflng a-z
dim s(4)
input "a,b,c,d:",s(1),s(2),s(3),s(4)
minsum=s(1)+s(2)+s(3)+s(4)
'利用组合函数吧:
a$="1234"
for i=1 to 4
b$=right$(a$,i)
do
sum=0
y$=""
for j=1 to 4
if instr(b$,chr$(48+j))>0 then
sum=sum+s(j)
if y$<>"" then y$=y$+"+"
y$=y$+str$(s(j))
endif
next
for j=1 to 4
if instr(b$,chr$(48+j))=0 then
if y$<>"" then y$=y$+"-"
sum=sum-s(j)
y$=y$+str$(s(j))
endif
next
y$=y$+"="+str$(sum)
if sum>=0 and sum<minsum then
minsum=sum
miny$=y$
end if
loop until nextzh$(a$,b$)=""
next
print miny$
end
-------------------------------------------------------
FUNCTION nextzh$ (a$, b$)
fOR i = 1 TO LEN(b$)
IF INSTR(1, a$, MID$(b$, i, 1)) > i THEN
MID$(b$, 1, i) = MID$(a$, INSTR(1, a$, MID$(b$, i, 1)) - i, i)
nextzh$ = b$
EXIT FUNCTION
END IF
NEXT
END FUNCTION
6 楼
staa [专家分:3690] 发布于 2005-11-08 16:14:00
我提出一个算法,程序就不写了:
前提:四个自然数;只能用加减运算。
一、先把这四个数排序;
二、如果|s1-s2-s3-s4|-|s1+s4-s2-s3|>0,则三,否则五;
三、如果s1+s4-s2-s3>=0,则照此输出;否则就输出s2+s3-s1-s4;
四、结束;
五、如果s1-s2-s3-s4>0,则照此输出;否则就输出s2+s3+s4-s1;
六、结束;
说明:排序后,它们的组合方式就少多了,只有两种情况,一是s1独大,二是s1+s4与s2+s3抗衡。
例如: 输入 15 6 12 4
排序后,s1=15, s2=12, s3=6, s4=4
|15-12-6-4|=7; |15+4-12-6|=1; 则三
15+4-12-6=1 >=0, 则直接输出这个算式即可。
7 楼
moz [专家分:37620] 发布于 2005-11-08 17:05:00
嗯,老家伙果然有独到之处,
我也想过这种方法,
但我只想到独大的情形,
之后的东西就没敢想下去,
因为我是为了易于扩展数目.
就按staa说的来做吧:
deflng a-z
dim s(4)
input "a,b,c,d:",s(1),s(2),s(3),s(4)
for i=1 to 3
for j=(i+1) to 4
if s(j)>s(i) then swap s(i),s(j)
next j,i
if abs(s(1)-s(2)-s(3)-s(4))-abs(s(1)+s(4)-s(2)-s(3))>0 then
if s(1)+s(4)-s(2)-s(3)>=0 then
print s(1);"+";s(4);"-";s(2);"-";s(3);"=";s(1)+s(4)-s(2)-s(3)
else
print s(2);"+";s(3);"-";s(1);"-";s(4);"=";s(2)+s(3)-s(1)-s(4)
endif
else
if s(1)-s(2)-s(3)-s(4)>=0 then
print s(1);"-";s(2);"-";s(3);"-";s(4);"=";s(1)-s(2)-s(3)-s(4)
else
print s(2);"+";s(3);"+";s(4);"-";s(1);"=";s(2)+s(3)+s(4)-s(1)
endif
endif
8 楼
staa [专家分:3690] 发布于 2005-11-09 12:15:00
看你小子这么谦虚好学,我老人家就再露一手
如果是比较多的数,可以考虑用改良的贪婪算法:
当然还是要先排序;
for i=1 to n/2 'n是数据个数,i是指前i个数先加在一起,i=1时就是通常所说的贪婪算法
......
'记录下各个i值下的较优解
next i
'然后比较这些较优解,找到最优解
9 楼
孤狼5926 [专家分:0] 发布于 2005-11-09 14:48:00
非常感谢楼上两位高手的指点!果然是受益非浅!谢谢!!
但我有点不明白:
|s1-s2-s3-s4|-|s1+s4-s2-s3|>0 是起什么作用?请指教!
10 楼
staa [专家分:3690] 发布于 2005-11-09 15:40:00
排序后,它们的组合方式就少多了,只有两种情况,一是s1独大,二是s1+s4与s2+s3抗衡。
|s1-s2-s3-s4|-|s1+s4-s2-s3|>0
就是为了解决是s1独大好呢还是s1+s4与s2+s3抗衡更好些。>0,则说明后者好;<0,则是前者好;=0,两个一样好,当然它不可能等于0。
我来回复