Re: Request for Algorithm

[Dao thi Bich Hanh <dao@esil.univ-mrs.fr>]

Do / Ngoc Minh (ISE) wrote:
> 
> On Fri, 16 May 1997, Ninh Tran wrote:
> 
> >
> > Dear vnsa friends,
> >
> > Can someone provide an algorithm that:
> >
> > 1. Given as input, four numbers, all greater than zero,
> > 2. Using four arithmetic operators +, -, *, /.
> >
> > Answer yes or no if there is a way to come up with 24 using the four
> > input
> > numbers and the four arithmetic operators. Each number must be used
> > exatcly
> > one, and the result of one computation can be used in the next.
> >
> > If the answer if Yes, print the calculation.
> >
> > Examples,
> >
> > 1. Input:  1,2,3,4.
> >     Answer: Yes:  (1+2+3)*4
> >
> > 2. Input: 2,2,2,2.
> >     Answer: No.
> >
> >
> > Regards,
> >
> > Ninh
> >
> 
> A simple approach is to search through the entire search space to find
> out the possible solution(s).  This can be done by induction as follows:
> 
> >From the list of n (n >= 2) numbers, we replace 2 arbitrary numbers, say a
> and b, by a new number c = f(a,b) where f is one of operators {+,-,*,/}.
> This process continues until we are left with one number which then can
> be compared with 24 in our case.
> 
> To have an idea of the search space, if let S(n) is the number of
> combinations for the list of n numbers, then from above we have:
>         S(n) = 4*C(n,2)*S(n-1)          (C(n,2) = n(n-1)/2)
> 
> or      S(n) = 4^(n-1)*C(n,2)*...*C(2,2)
> 
> As in our case, S(4) = 1152 combinations.
> 
> A program can be written in Prolog (a logic language that has the
> ability to backtrack) with less than 20 lines of code.
> 
> Cheers,
> Minh.

DDu'ng la` chu+o+ng tri`nh na`y ddu+o+.c the^? hie^.n ra^'t
nga('n go.n trong Prolog, tuy va^.y theo to^i, kho^ng gian ti`m kie^'m
kho^ng pha?i ddu+o+.c ti'nh theo co^ng thu+'c tre^n\. Vi' du. vo+'i
hai so^' a va` b (n=2), do '-' va` '/' kho^ng giao hoa'n, 
ta co' 6 kha? na(ng kha'c nhau: a+b, a-b, b-a, a*b, a/b va` b/a.
Vi` va^.y   
     S(n) = 6*C(n,2)*S(n-1), n>=2
  => S(n) = 6^(n-1)*C(n,2)*...*C(2,2)

Regards,
BHanh