24点.txt

C精彩编程百例源码

第一个算法是用C语言描述的，第二个是C++描述的，都是我在网上搜集整理的计算24点的算法，其中第二个最容易理解（递归的魅力），因为它用了string这种很方便的字符串流，第一种算法很复杂，我每次都要再看过，大家可以收藏起来慢慢品味~

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

char op[3], o[5]="+-*/";
float n[4], on[10];
int used[4] = {0}, top=0, tp=0, x;

void chk(float k);
void search24(int d);
float calc(float n1, float n2, char o);
void make(int i, float p, float q, char o, int d);

int main( void )
{
 printf("please input 4 card number:\n");
    scanf("%f%f%f%f", &n[0], &n[1], &n[2], &n[3]);

    search24(0);
    printf("No answer.\n");

    return 0;
}


void chk(float k)
{
    if( (tp != 3) || ( fabs(k-24.0) > 0.000001 )) //没有用完3个运算符或者结果不为24就退出.
  return;
    for(x=0; x<5; x+=2)                                            //这样设计是为了使3个选中的符号都可以得到输出.
        printf("%g%c%g=%g\n", on[x], op[x/2], on[x+1],         //分析得到的.
                               calc(on[x], on[x+1], op[x/2]));
 system("pause");
    exit(0);
}
float calc(float n1, float n2, char o)
{

    switch(o){
        case '+': return (n1+n2);
        case '-': return (n1-n2);
        case '*': return (n1*n2);
        case '/': return (n1/n2);
  default: exit(0);
    }

}
void make(int i, float p, float q, char o, int d)
{
    if(fabs(q)>0.000001 || o!='/')   //除数不为0,或者为0的时候不能为除数.
        n[i] = calc(p, q, o);
    op[tp++] = o;  

 chk(n[i]);
    search24(d+1); 
 tp--;    //因为是全是全局变量,所以在做试验性的循环递归问题时,如果失败,要在递归函数后面重新恢复回原来的值
}

void search24(int d)
{
    int i, j, k;
    float p, q;
    if(d>=3)    //控制递归深度,就是运算符的输出个数.
  return;
    for(i=0; i<4; i++)
        for(j=0; j<4; j++)
            if( (i!=j)&& (used[i]+used[j] == 0) ) //i!=j是防止重复,(used[i]+used[j] == 0)是防止又再匹配已经用过的j,
                                      //但是i可以新来.
   {
                used[j] = 1;   //j得到匹配之后,赋值为1,表示已经使用
    p=n[i]; 
    q=n[j];
                on[top++] = p; 
    on[top++] = q; 
                for(k=0; k<4; k++)  //运算符的循环试用.
                    make(i, p, q, o[k], d);
                n[i] = p;        //因为是全是全局变量,所以在做试验性的循环递归问题时,
    used[j] = 0;     //如果失败,要在递归函数后面重新恢复回原来的值
                top -= 2;        //
            }

}







#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 Judgement = false;                    //判断是否有解。
int count = 0;    
    

void  Search(int   n)   
{   
      if (n   ==   1) 
   {   
            if ( fabs(number[0] - NUMBER_TO_BE_CAL) <= PRECISION   )  //对于除法，要小心小数的精确位数
   {   
                  cout << expression[0] << "\t\t";  
      Judgement = true;
      count ++;
      if((count % 3)==0)
       cout<<endl;
            }   
   else  
   {   }   
       }   
    
       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];   //递归之后，n比以前小一位，所以可以不停向前赋值  
    
                        expa   =   expression[i];   
                        expb   =   expression[j];   
                        expression[j]  =  expression[n - 1];   //递归之后，n比以前小一位，所以可以不停向前赋值
    
                        expression[i]   =   '('   +   expa   +   '+'   +   expb   +   ')';   //加法不需要分顺序
                        number[i]   =   a   +   b;   
                        Search(n-1);
                            
                        expression[i]   =   '('   +   expa   +   '-'   +   expb   +   ')';   //减法应该分顺序，减数以及被减数
                        number[i]   =   a   -   b;   
                        Search(n-1);  
                            
                        expression[i]   =   '('   +   expb   +   '-'   +   expa   +   ')';   //减法应该分顺序，减数以及被减数
                        number[i]   =   b   -   a;   
                        Search(n-1);  
                                                    
    
                        expression[i]   =   '('   +   expa   +   '*'   +   expb   +   ')';   //乘法不需要分顺序
                        number[i]   =   a   *   b;   
                        Search(n-1);  
    
                        if (b != 0) 
      {   
                                expression[i]   =   '('   +   expa   +   '/'   +   expb   +   ')';   //除法应该分顺序，除数以及被除数
                                number[i] = a / b;   
                                Search(n-1);   
                        }     
                        if (a != 0)
      {   
                                expression[i]   =   '('   +   expb   +   '/'   +   expa   +   ')';   //除法应该分顺序，除数以及被除数
                                number[i]   =   b  /  a;   
                                Search(n-1);   
                        }   
    
                        number[i]   =   a;                  //这4句语句是为了防止如果上面几种可能都失败了的话,
                        number[j]   =   b;                  //就把原来的赋值撤消回去,以无干扰的正确的进入到下一次
                        expression[i]   =   expa;           //for循环队列中。
                        expression[j]   =   expb;           //
                }   
    } 
}   
    

int  main()   
{   

  cout<<"Please input 4 value of Cards:\n";

        for (int i = 0; i < COUNT_OF_NUMBER; i++)  
  {   
                char   buffer[20];    
    cout<<"The "<<i+1<<"th card:";
                cin   >>   number[i];                   
                itoa(number[i],   buffer,   10);   //itoa()函数的作用是把第一个参数(数值)传送到第二个参数(字符串)中去，第三个
               //参数(int型)是该数值在字符串里以什么进制存放。
                expression[i]   =   buffer;   
        } 
  
  cout<<endl;

        Search(COUNT_OF_NUMBER) ;

  if(Judgement==true)
  {   
                cout   <<   "\nSuccess."   <<   endl; 
    cout<<"The sum of the ways = "<<count<<endl;
        }   
  else 
  {   
                  cout   <<   "Fail."   <<   endl;   
        }        

  system("pause");

  return 0;
}