张运涛

c++
   :: 首页 :: 联系 :: 聚合  :: 管理

常用链接

留言簿(4)

随笔分类

随笔档案

文章分类

文章档案

收藏夹

Blogs

Game Dev

Mac / IOS Dev

Play Iphone

搜索

  •  

最新评论

回溯经典-二十四点算法

 

#include   <iostream>   
#include   <string>   
#include   <cmath>   

using   namespace   std;   

const   double   PRECISION   =   1E-6;   
const   int   COUNT_OF_NUMBER     =   4;   
const   int   NUMBER_TO_BE_CAL   =   24;   

double   number[COUNT_OF_NUMBER];   
string   expression[COUNT_OF_NUMBER];   

bool   Search(int   n)   
{   
    if(n==1)   
    {   
        if(fabs(number[0]-NUMBER_TO_BE_CAL) < PRECISION)   
        {   
            cout<<expression[0]<<endl;   
            return  true;   
        }
        else   
        {   
            return false;   
        }   
    }   
    
    for   (int   i   =   0;   i   <   n;   i++)  
    {   
        for (int   j   =   i   +   1;   j   <   n;   j++)   
        {   
            double   a,   b;   
            string   expa,   expb;   
            
            a   =   number[i];   
            b   =   number[j];   
            number[j]   =   number[n   -   1];   
            
            expa   =   expression[i];   
            expb   =   expression[j];   
            expression[j]   =   expression[n   -   1];   
            
            expression[i]   =   '('   +   expa   +   '+'   +   expb   +   ')';   
            number[i]   =   a   +   b;   
            if   (   Search(n   -   1)   )   return   true;   
            
            expression[i]   =   '('   +   expa   +   '-'   +   expb   +   ')';   
            number[i]   =   a   -   b;   
            if   (   Search(n   -   1)   )   return   true;   
            
            expression[i]   =   '('   +   expb   +   '-'   +   expa   +   ')';   
            number[i]   =   b   -   a;   
            if   (   Search(n   -   1)   )   return   true;   
            
            
            expression[i]   =   '('   +   expa   +   '*'   +   expb   +   ')';   
            number[i]   =   a   *   b;   
            if   (   Search(n   -   1)   )   return   true;   
            
            if   (b   !=   0)   {   
                expression[i]   =   '('   +   expa   +   '/'   +   expb   +   ')';   
                number[i]   =   a   /   b;   
                if   (   Search(n   -   1)   )   return   true;   
            }     
            if   (a   !=   0)   {   
                expression[i]   =   '('   +   expb   +   '/'   +   expa   +   ')';   
                number[i]   =   b   /   a;   
                if   (   Search(n   -   1)   )   return   true;   
            }   
            
            number[i]   =   a;   
            number[j]   =   b;   
            expression[i]   =   expa;   
            expression[j]   =   expb;   
        }   
    }   
    return   false;   
}   

void   main()   
{   
    for(int i = 0;i< COUNT_OF_NUMBER;i++)
    {   
        char  buffer[20];   
        int  x;   
        cin  >> x;   
        number[i]= x;   
        itoa(x,   buffer,   10);   
        expression[i]   =   buffer;   
    }  
    

    if(Search(COUNT_OF_NUMBER)) 
    {   
        cout   <<   "Success."   <<   endl;   
    }   else   {   
        cout   <<   "Fail."   <<   endl;   
    }                   
    
}
posted on 2010-04-11 12:37 张运涛 阅读(654) 评论(0)  编辑 收藏 引用 所属分类: 算法学习

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理