24点暴力解法

时间：2009-08-23 来源：ubuntuer

写着写着难得回溯,条件判断太繁琐!!!搞成穷举了... 1.perm求输入数字的全排列 2.combine求(+, -, *, /)的4选3组合我这里因为每次都是算两个数字,所以不存在优先级问题!!!输出的时候如果是+, -加括号就可以了,我这里没加!!!也有很多的附加打印信息 eg： input 9 1 6 2 9 - 1 * 6 / 2从头开始9-1 = 8 8*6/2 48/2 == 24 输出代码有很多所谓的技巧^_^.大家别介意将就点,我自己的style^_^.别拍砖

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

int perm_num[24][4];//全排列

int global_num = 0;
char CH[4] = {'+','-','*','/'};

float my_add(float a, float b)
{
  return a+b;
}

float my_sub(float a, float b)
{
  return a-b;
}

float my_mul(float a, float b)
{
  return a*b;
}

float my_div(float a, float b)
{
  return a/b;
}

float (*method[4])(float a, float b);

void init_method()
{
   method[0] = my_add;
   method[1] = my_sub;
   method[2] = my_mul;
   method[3] = my_div;
}

void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int perm(int A[4], int i)
{
  int j;
  if(i>=4)
   {
    for(j=0;j<4;j++)
     perm_num[global_num][j] = A[j];
    global_num++;
   }
  else
   {
    for(j=i;j<4;j++)
     {
      swap(A+i, A+j);
      perm(A, i+1);
      swap(A+i, A+j);
     }
   }
}

void print_perm(int perm_num[24][4])
{
  int i;
  int j;
  for(i=0;i<24;i++)
   {
    printf("%d:\t",i+1);
    for(j=0;j<4;j++)
     printf("%d\t", perm_num[i][j]);

    printf("\n");
   }
}

void check_24(int M[3], int P[4])
{
  int i = 0;
  float tmp = P[0];
  printf("%d", P[0]);
  for(i=0;i<3;i++)
   {
     tmp = method[M[i]](tmp*1.0,P[i+1]*1.0);
     printf("%c%d",CH[M[i]], P[i+1]);
   }
  printf("=%f\n", tmp);
  if(abs(tmp-24)<0.01)
   {
     for(i=0;i<3;i++)
       printf(" %d %c", P[i],CH[M[i]]);

      printf("%d\n",P[i]);
   }
}

void combine(int n, int m, int M[4][3])
{
  int i;
  int j;
  for(i=n;i>=m;i--)
   {
     M[global_num][m-1] = i-1;
     if(m>1)
      combine(i-1, m-1, M);
     else
      {
       for(j=2;j>=0;j--)
        M[global_num+1][j]=M[global_num][j];

       global_num++;
      }
   }
}

void print_combine(int M[4][3])
{
  int i;
  int j;
  for(i=0;i<4;i++)
   {
    printf("%d:\t",i+1);
    for(j=0;j<3;j++)
     printf("%d\t", M[i][j]);

    printf("\n");
   }
}

int count_24(int A[4])
{
  int i;
  int j;
  int B[4] = {0,1,2,3};
  perm(A, 0);
  print_perm(perm_num);
  init_method();

  int M[4][3];
  global_num = 0;
  combine(4, 3, M);
  print_combine(M);

  for(i=0;i<4;i++)
  {
   for(j=0;j<24;j++)
    check_24(M[i], perm_num[j]);
  }
}

int main(int argc, char *argv[])
{
  int i;
  int A[4];
  while(1)
   {
     global_num = 0;
     printf("Please input the four number you want to count:\n");
     scanf("%d %d %d %d",&A[0],&A[1],&A[2],&A[3]);
     setbuf(stdin, NULL);
     count_24(A);
   }
  system("PAUSE");
  return 0;
}