Chinaunix首页 | 论坛 | 博客
  • 博客访问: 506074
  • 博文数量: 65
  • 博客积分: 1158
  • 博客等级: 少尉
  • 技术积分: 1261
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-18 22:07
文章分类

全部博文(65)

文章存档

2016年(1)

2014年(2)

2013年(9)

2012年(53)

分类: C/C++

2012-09-18 09:50:25

/*
Description

求24点问题。给定4个正整数,用算术运算符+,-,*,/将这4个正整数连接起来,
使其最终结果恰为24。如果能得到24,输出Yes,否则输出No。


数据输入:

第一行是一个整数N(1<=N<=20),表示有多少个测试例子。以下每行为一个测试例子,每行有四个正整数。


数据输出:

每行输出对应测试例子的结果。

Sample Input

2
1 2 3 7
2 2 2 2


Sample Output

Yes
No
*/
/**
分析:4个数中任意两个用六种运算得到一个结果,将其赋给辅助数组的第一个位置,
其他两个没有选取的赋给第二个和第三个元素;递归调用,直到得到结果,判断结果是不是24
如果不是,当传递的操作数个数为两个时,则换一个操作符试试看能不能使其得到结果为24
六种都试过后,那就得回溯到三个操作数的时候了,回溯即把辅助数组的元素还原,当然每次调用之前都把辅助数组
拷贝一份给操作数就不需要将值再赋值回赋值数组了,
为什么要回溯或者是要用到拷贝主要是因为这个公用的数组在使用时会发生变化,
当要回溯时,直接将拷贝的数据复制给它就行了
回到三个操作数那一层时,再去试试其他操作符,然后再递归调用,或者都不行,回溯到四个操作数那一层。
直到所以的操作都试了 还是得不到24 再去换其他任意两个数 继续这样的操作 知道所以的组合全部试完
仍然得不到24的话 返回false 如果有一个得到24 直接返回true 毕竟这里不是要你求所以的组合
*/


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. int assists[3] = {0,0,0};
  4. int calculate(int);
  5. bool judge(int *,int);

  6. int main()
  7. {
  8.     int cases,input[4],i;

  9.     scanf("%d",&cases);

  10.     while(cases--)
  11.     {
  12.         for(i=0; i<4; i++)
  13.         {
  14.             scanf("%d",&input[i]);
  15.         }

  16.         if(judge(input,4))
  17.         {
  18.             printf("Yes\n");
  19.         }
  20.         else
  21.         {
  22.             printf("No\n");
  23.         }
  24.     }
  25.     system("pause");
  26.     return 0;
  27. }

  28. int calculate(int num1,int num2,int operate)
  29. {
  30.     //乘法和加法有交换律
  31.     //做除法时 除数为零和除不尽都返回30000 表示不用考虑这种情况
  32.     switch(operate)
  33.     {
  34.     case 1:
  35.         return num1 + num2;
  36.         break;
  37.     case 2:
  38.         return num1 - num2;
  39.         break;
  40.     case 3:
  41.         return num1 * num2;
  42.         break;
  43.     case 4:
  44.         return num2 - num1;
  45.         break;
  46.     case 5:
  47.         return ((num2 != 0 && num1 % num2 == 0)?(num1/num2):10000);
  48.         break;
  49.     case 6:
  50.         return ((num1 != 0 && num2 % num1 == 0)?num2/num1:10000);
  51.         break;
  52.     }
  53. }

  54. bool judge(int *p,int count)
  55. {
  56.     bool result = false;
  57.     int i,j,k,n,operators[6],input[4],a=0;

  58.     //先将数组拷贝一份
  59.     for(i=0; i<count; i++)
  60.     {
  61.         input[i] = p[i];
  62.         //printf("%d\n",p[i]);
  63.     }

  64.     for(i=0; i<6; i++)
  65.     {
  66.         operators[i] = i + 1;
  67.     }
  68.     for(i=0; i<count; i++)
  69.     {
  70.         for(j=0; j<count&&j!=i; j++)
  71.         {
  72.             //printf("_______________________________________\n");
  73.             for(k=0; k<6; k++)
  74.             {

  75.                 if(calculate(input[i],input[j],operators[k]) != 10000)
  76.                 {
  77.                     //完成第一次运算
  78.                     assists[0] = calculate(input[i],input[j],operators[k]);
  79.                     //printf("%d--------------------\n",assists[0]);


  80.                     if(count == 4)
  81.                     {
  82.                         bool flag = true;
  83.                         //给其他两个操作数赋值
  84.                         for(n=0; n<count; n++)
  85.                         {
  86.                             if(n != i && n != j && flag)
  87.                             {
  88.                                 assists[1] = input[n];
  89.                                 //printf("%d===\n",assists[1]);
  90.                                 flag = false;
  91.                                 continue;
  92.                             }
  93.                             else if(n != i && n != j)
  94.                             {
  95.                                 assists[2] = input[n];
  96.                                 //printf("%d===\n",assists[2]);
  97.                             }
  98.                             else
  99.                             {
  100.                                 continue;
  101.                             }

  102.                         }

  103.                         //调用自身,操作数个数减1
  104.                         result = judge(assists,count-1);
  105.                         if(!result)
  106.                         {
  107.                             if(k == 5)
  108.                             {
  109.                                 break; //不需要回溯,直接退出这个循环,再选取另外两个
  110.                             }

  111.                             continue; //继续试试新的操作数
  112.                         }
  113.                         else
  114.                         {
  115.                             return true;
  116.                         }

  117.                     }
  118.                     else if(count == 3)
  119.                     {
  120.                         for(n=0; n<count; n++)
  121.                         {
  122.                             if(n != i && n != j)
  123.                             {
  124.                                 assists[1] = input[n];
  125.                                 //printf("%d===\n",assists[1]);
  126.                                 break;
  127.                             }
  128.                             else
  129.                             {
  130.                                 continue;
  131.                             }

  132.                         }

  133.                         if(!judge(assists,count-1))
  134.                         {
  135.                             if(k == 5)
  136.                             {
  137.                                 //assists[0] = input[0]; //回溯,返回有4个操作数时再进行判断
  138.                                 return false;
  139.                             }
  140.                             continue; //继续试试新的操作
  141.                         }
  142.                         else
  143.                         {
  144.                             //printf("HelloWolrd3\n");
  145.                             return true; //成功返回
  146.                         }
  147.                     }
  148.                     else if(count == 2)
  149.                     {
  150.                         if(assists[0] == 24)
  151.                         {
  152.                             //printf("HelloWolrd2\n");
  153.                             return true;
  154.                         }

  155.                         if(k == 5)
  156.                         {
  157.                             //assists[0] = input[0]; //回溯
  158.                             //assists[1] = input[1];
  159.                             return false; //返回3个操作数的时刻
  160.                         }
  161.                         else
  162.                         {
  163.                             //printf("%d++++++++++++++++\n",a++);
  164.                             continue;//试试其他操作符
  165.                         }
  166.                     }
  167.                 }

  168.                 else
  169.                 {
  170.                     continue;
  171.                 }
  172.             }

  173.         }
  174.     }

  175.     return false; //能到达这里 说明前面的都没有成功 最后返回false
  176. }

阅读(494) | 评论(0) | 转发(0) |
0

上一篇:归并排序

下一篇:背包问题

给主人留下些什么吧!~~