关于那道趣的算法题：实现24点游戏求解的存储过程

Question

我也写了一个，跟大家分享一下:)
--保存运算符之间的优先级，通过该表可以判断在一个表达式中加上一对括号是否会改变表达式的值。
create table t_operator (operator1 char(1),operator2 char(1),flag int)
insert t_operator(operator1,operator2,flag)
select '-','+','2' union all select '-','-','2' union all select '/','*','2' union all 
select '/','/','2' union all select '*','+','2' union all select '*','-','2' union all
select '/','+','2' union all select '/','-','2' union all select '+','*','1' union all
select '+','/','1' union all select '-','*','1' union all select '-','/','1'
gocreate proc p_calc_24 @a int,@b int,@c int,@d int
as
/*
  描述：
    给定任意四个整数，保持数字顺序不变,在数字中间加入+-* /()等符号,使表达式等于24，括号最多加4-2=2对。  
  版本：
    时间            修改人  操作
    2007年05月21日  mengmou 创建
  输入参数：
    任意四个整数.
  涉及:
    表t_operator，保存运算符之间的优先级，通过该表可以判断在一个表达式中加上一对括号是否会改变表达式的值。
  返回：
    所有满足条件的表达式的结果集。
  BUG：
    1.表达式[8+13-9*2]⑴派生出[(8+13-9)*2]⑵和[8+(13-9)*2]⑶，表达式⑶又派生出[(8+(13-9))*2]⑷，
      表达式⑷中的内层括号并不影响⑷的值，⑷相当于⑵的冗余，所以像⑷这类冗余不应该出现在结果集中。
      四个整数的表达式最多有两对括号，如果一一列举出所有情况并判断是否为冗余，会使代码会非常臃肿。
*/set nocount on
set arithabort off 
set arithignore off 
set ansi_warnings offdeclare @operator_list varchar(4),@x int,@y int,@z int,@i int,@sql nvarchar(50),@result numeric(38,6)
  ,@aa varchar(10),@bb varchar(10),@cc varchar(10),@dd varchar(10),@xx char(1),@yy char(1),@zz char(1)
  ,@id int,@operator varchar(8000),@group_id int,@new_operator varchar(8000),@min_id int,@max_id int
  ,@old_group_id int,@new_group_id int
select @aa = convert(varchar(10),@a)+'.0',@bb = convert(varchar(10),@b)+'.0',@cc = convert(varchar(10),@c)+'.0'
  ,@dd = convert(varchar(10),@d)+'.0',@operator_list = '-+/*',@x = 1,@y = 1,@z = 1,@i = 1,@new_operator = ''
  ,@new_group_id = 1,@old_group_id = 0
declare @t_expression table(expression varchar(50))
declare @t_operator table(group_id int,id int identity,operator varchar(8000))while @x <= 4
begin
  while @y <= 4
  begin
    while @z <= 4--增加嵌套循环的层数便可以实现在N个数中间加上+-*/()使表达式等于M，括号最多加N-2对。
    begin
      select @xx = substring(@operator_list,@x,1),@yy = substring(@operator_list,@y,1)
        ,@zz = substring(@operator_list,@z,1)
        ,@sql = 'select @result ='+ @aa + @xx + @bb + @yy + @cc + @zz + @dd 
      exec sp_executesql @sql,N'@result numeric(38,6) out',@result out
      
      if @result = 24.00000
      begin
        insert @t_expression(expression) select replace(stuff(@sql,1,16,''),'.0','')
      end
      else--去掉else中的代码返回只有加减乘除没有括号的表达式
      begin
        insert @t_operator
        select @new_group_id,@aa union all select @new_group_id,@xx union all select @new_group_id,@bb union all 
        select @new_group_id,@yy union all select @new_group_id,@cc union all select @new_group_id,@zz union all 
        select @new_group_id,@dd
        
        set @new_group_id = @new_group_id + 1
      loop1:
        declare c_suited_id cursor for
        select distinct _a.group_id
          ,case when exists(select 1 from t_operator where flag = 1 and operator1 = _a.operator and operator2 = _b.operator)
            then _a.id-1 else _a.id+1 end as min_id
          ,case when exists(select 1 from t_operator where flag = 1 and operator1 = _a.operator and operator2 = _b.operator)
            then _b.id-1 else _b.id+1 end as max_id
        from @t_operator _a
        join @t_operator _b on _b.id > _a.id and _b.group_id = _a.group_id
        where _a.group_id >= @old_group_id and _b.group_id >= @old_group_id
          and _a.operator in ('+','-','*','/') and _b.operator in ('+','-','*','/')
          and exists(select 1 from t_operator where operator1 = _a.operator and operator2 = _b.operator )
    
        set @old_group_id = @new_group_id
        open c_suited_id
        fetch next from c_suited_id into @group_id,@min_id,@max_id
        while @@fetch_status = 0
        begin
          set @new_operator = ''
          select @new_operator = @new_operator + operator
          from @t_operator
          where group_id = @group_id and id between @min_id and @max_id
          
          insert @t_operator(group_id,operator)
          select @new_group_id,* 
          from (
            select operator from @t_operator where group_id = @group_id and id < @min_id union all
            select '('+@new_operator+')' union all
            select operator from @t_operator where group_id = @group_id and id > @max_id 
          ) x
          
          select @sql = ''
          select @sql = @sql + operator from @t_operator where group_id = @new_group_id order by id
          select @sql = 'select @result =' + @sql
          exec sp_executesql @sql,N'@result numeric(38,6) out',@result out
          if @result = 24.00000
            insert @t_expression(expression) select replace(stuff(@sql,1,16,''),'.0','')
          
          set @new_group_id = @new_group_id + 1
          fetch next from c_suited_id into @group_id,@min_id,@max_id
        end
        close c_suited_id
        deallocate c_suited_id
        
        if @old_group_id < @new_group_id
          goto loop1
        delete @t_operator
      end
      set @z = @z + 1
    end
    select @y = @y + 1,@z = 1
  end
  select @x = @x + 1,@y = 1,@z = 1
end
select distinct * from @t_expression order by expression
go

Answer 1

create proc p_calc_24_all @a int,@b int,@c int,@d int
as
/*
  描述：
    给定任意四个整数，可以改变数字顺序,在数字中间加入+-* /()等符号,使表达式等于24.  
  版本：
    时间            修改人    操作
    2007年05月21日  mengmou 创建
  输入参数：
    任意四个整数.
  涉及:
    p_calc_24，给定任意四个整数，保持数字顺序不变,在数字中间加入+-* /()等符号,使表达式等于24。  
  返回：
    所有满足条件的表达式的结果集。
*/set nocount on
declare @t_number table(id int identity,number int)
insert @t_number(number) select @a union all select @b union all select @c union all select @d
declare @aa int,@bb int,@cc int,@dd int
select @aa = 1,@bb = 1,@cc = 1,@dd = 1create table #t_expression(expression varchar(50))while @aa <= 4
begin
  while @bb <= 4
  begin
    if @bb in(@aa) 
    begin
      set @bb = @bb + 1 
      continue
    end
    while @cc <= 4
    begin
      if @cc in(@aa,@bb) 
      begin
        set @cc = @cc + 1
        continue
      end
      select @a = 0,@b = 0,@c = 0,@d = 0
      select @a = @a + case when id = @aa then number else 0 end
        ,@b = @b + case when id = @bb then number else 0 end
        ,@c = @c + case when id = @cc then number else 0 end
        ,@d = @d + case when id not in(@aa,@bb,@cc) then number else 0 end
      from @t_number
      insert #t_expression(expression)
      exec p_calc_24 @a,@b,@c,@d
      if @c = @d 
        break
      set @cc = @cc + 1
    end
    if @b = @c 
      break
    select @bb = @bb + 1,@cc = 1
  end
  if @a = @b 
    break
  select @aa = @aa + 1,@bb = 1,@cc = 1
end
select * from #t_expression order by expression
drop table #t_expressiongoexec p_calc_24 8,13,9,2
/*--测试结果（查询时间1秒）
expression
--------------------------------------------------
(8+(13-9))*2
(8+13-9)*2
*/
go
exec p_calc_24_all 8,13,9,2
/*--测试结果（查询时间7秒）
expression
--------------------------------------------------
(13-(9-8))*2
(13+(8-9))*2
(13+8-9)*2
(13-9)*(8-2)
(13-9+8)*2
(2-8)*(9-13)
(8-(9-13))*2
(8+(13-9))*2
(8+13-9)*2
(8-2)*(13-9)
(8-9+13)*2
(9-13)*(2-8)
2*((13+8)-9)
2*((13-9)+8)
2*((8+13)-9)
2*((8-9)+13)
2*(13-(9-8))
2*(13+8-9)
2*(13-9+8)
2*(8-(9-13))
2*(8+13-9)
2*(8-9+13)
9/(2-13/8)
*/
go
drop table t_operator
drop proc p_calc_24,p_calc_24_all