华为OJ24点游戏算法

冷不防 2022-06-17 12:49 161阅读 0赞

<table style="border-spacing:0px; border-collapse:collapse; width:960px; margin-bottom:35px; table-layout:fixed; color:rgb(92,92,92); font-family:glober,'Helvetica Neue',Helvetica,Arial,'Lantinghei SC','Hiragino Sans GB','Microsoft YaHei','Wenquanyi Micro Hei',sans-serif; font-size:14px; line-height:20px"> 
 <tbody style=""> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 描述</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <pre style="overflow:hidden; font-family:monospace,monospace; font-size:1em; white-space:pre-wrap; word-wrap:break-word; line-height:24px"><p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px">问题描述：给出4个1-10的数字，通过加减乘除，得到数字为24就算胜利<br style="">输入：<br style="">4个1-10的数字。[数字允许重复，测试用例保证无异常数字]<br style="">输出：<br style="">true&nbsp;or&nbsp;false</p></pre> </td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 知识点</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 循环</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 运行时间限制</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 10M</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 内存限制</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 128</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输入</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 输入4个int整数</p> </td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输出</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 返回能否得到24点，能输出true，不能输出false</p> </td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输入</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> 7 2 1 10</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输出</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); background-color:rgb(226,243,253); width:872px"> true</td> 
  </tr> 
 </tbody> 
</table>

#include <iostream>  
    #include <string>  
    #include <algorithm>  
    #include <vector>  
    #include <fstream>  
    #include <map>
    
    using namespace std;
    
    int Is24Game(int *a, int i, int result)
    {
    	if (result == 24)
    		return 1;
    	else if (result > 24 || i >= 4)
    		return 0;
    	else
    		return Is24Game(a, i + 1, result + a[i]) ||
    		Is24Game(a, i + 1, result - a[i]) ||
    		Is24Game(a, i + 1, result * a[i]) ||
    		Is24Game(a, i + 1, result == 0 ? 0 : result / a[i]);
    }
    
    int main()
    {
    	int *a = new int[4];
    	for (int i = 0; i < 4; i++)
    		cin >> a[i];
    
    	sort(a, a + 4);
    	bool flag = false;
    	do
    	{
    		if (Is24Game(a, 0, 0))
    		{
    			cout <<"true";
    			flag = true;
    			break;
    		}
    	} while (next_permutation(a, a + 4));
    
    	if (!flag)
    		cout << "false";
    	delete[]a;
    	return 0;
    }