[深搜]24点--改进版本

叁歲伎倆 2021-11-11 15:46 158阅读 0赞

## 回顾 ##

之前写的版本[\[深搜回溯\]24点][24]，没有考虑到中间数值的可能性，是对数值进行深搜遍历，而不是对数值对进行深搜数值遍历，使得较为复杂的24点运算中有部分数据没办法得到解决。这次的改进将围绕着这个进行。

> 这个项目也被我放到了Github上关于算法的Repository上  
> [https://github.com/Sean16SYSU/Algorithms4N][https_github.com_Sean16SYSU_Algorithms4N]

## 算法思路 ##

*  当数组长度为1的时候输出，判断是否为24点，如果是24点，就输出对应的数学表达。
 *  如果数组长度大于等于2，则进行深度搜索
    
     *  在数组中任意选择两个数值，再选择加法，左减，右减（减法有顺序），左除，右除，乘法。（只有加法和乘法具有交换律）

## 测试数据 ##

1
    1 5 5 5
    (5*(5-(1/5)))

*  第一个数值为算式数量，
 *  第二行的输入为数值
 *  第三行为输出

这个数据，只有在考虑数值对的时候，才会被解决。是一个不错的数据。

## 代码 ##

#include <iostream>
    #include <stack>
    #include <string>
    #include <cmath>
    #include <vector>
    using namespace std;
    
    double arr[4];
    
    bool DFS(double *tmp, string* formulas, int size) { 
    	if (size == 1) { 
    		// cout << tmp[0] << " " << formulas[0] << endl;
    		if (tmp[0] == 24) { 
    			cout << formulas[0] << endl;
    			return true;
    		}
    		return false;
    	}
    	double *new_tmp = new double[size - 1];
    	string *new_formulas = new string[size - 1];
    	for (int i = 0; i < size; ++i) { 
    		for (int j = i + 1; j < size; ++j) { 
    			int tot = 0;
    			for (int p = 0; p < size; ++p) { 
    				if (p != i && p != j) { 
    					new_tmp[tot++] = tmp[p];
    				}
    			}
    			tot = 0;
    			for (int p = 0; p < size; ++p) { 
    				if (p != i && p != j) { 
    					new_formulas[tot++] = formulas[p];
    				}
    			}
    
    			// op:0, temp + value
    			new_tmp[size - 2] = tmp[i] + tmp[j];
    			new_formulas[size - 2] = (string("(") + formulas[i] + string("+") + formulas[j] + string(")"));
    			if (DFS(new_tmp, new_formulas, size - 1))
    				return true;
    
    			// op:1, temp - value
    			new_tmp[size - 2] = tmp[i] - tmp[j];
    			new_formulas[size - 2] = (string("(") + formulas[i] + string("-") + formulas[j] + string(")"));
    			if (DFS(new_tmp, new_formulas, size - 1))
    				return true;
    
    			// op:2, value - temp 
    			new_tmp[size - 2] = tmp[j] - tmp[i];
    			new_formulas[size - 2] = (string("(") + formulas[j] + string("-") + formulas[i] + string(")"));
    			if (DFS(new_tmp, new_formulas, size - 1))
    				return true;
    			// op:3, temp / value
    			new_tmp[size - 2] = tmp[i] / tmp[j];
    			new_formulas[size - 2] = (string("(") + formulas[i] + string("/") + formulas[j] + string(")"));
    			if (DFS(new_tmp, new_formulas, size - 1))
    				return true;
    
    			// op:4, value / temp 
    			new_tmp[size - 2] = tmp[j] / tmp[i];
    			new_formulas[size - 2] = (string("(") + formulas[j] + string("/") + formulas[i] + string(")"));
    			if (DFS(new_tmp, new_formulas, size - 1))
    				return true;
    
    			// op:5, temp * value
    			new_tmp[size - 2] = tmp[i] * tmp[j];
    			new_formulas[size - 2] = (string("(") + formulas[i] + string("*") + formulas[j] + string(")"));
    			if (DFS(new_tmp, new_formulas, size - 1))
    				return true;
    		}
    	}
    	delete[] new_tmp;
    	delete[] new_formulas;
    	return false;
    }
    
    int main() { 
    	int time;
    	cin >> time;
    	
    	while (time--) { 
    		for (int i = 0; i < 4; ++i) { 
    			cin >> arr[i];
    		}
    		string formula[4];
    		for (int i = 0; i < 4; ++i) formula[i] = to_string(int(arr[i]));
    		if (DFS(arr, formula, 4)) { 
    			continue;
    		}
    		else { 
    			cout << "None\n";
    		}
    	}
    	system("pause");
    }

[24]: https://blog.csdn.net/a19990412/article/details/78412838
[https_github.com_Sean16SYSU_Algorithms4N]: https://github.com/Sean16SYSU/Algorithms4N