《网易游戏2017互娱》实习笔试编程一：竖式填空

题目介绍：

[编程|100分] 竖式填空 时间限制：1秒 空间限制：65536K 题目描述 小Q是名小学生，他最喜欢数学中的加法竖式填空了。例如下面的填空题，每个空格表示1…9中的一个数字。

有时候这种竖式题不一定只有唯一解，小Q很想知道，给定一个这样的竖式，总共可能的解有多少个。 被加数和加数的位数不会超过3位。和的位数不会超过4位。空格只可能存在于被加数和加数中。

输入描述: 每个输入数据包含多个测试点。 第一行为测试点的个数T(T<=30)。 每个测试点包含一行，包含了三个长度大于0的字符串，分别表示被加数，加数和结果。每个字符串之间有一个空格。每个字符串只会包含“X”和“1”…“9”，其中“X”表示竖式中的空格。保证竖式至少有一个解。

输出描述: 对于每个测试点，输出一行，表示一共可能的解的个数。

输入例子: 2 X7 9X 123 X X 4

输出例子: 1 3 （样例解释：样例1的解为27+96，样例2的解为1+3,2+2,3+1。）

思路

先标记出未知位在每个数中的位置，等式左边先求出已知位的和，等式右边是已知数据。用递归，对每个未知位，依次取0～9，然后递归取下一个未知位。注意最高位不能为0。

代码

// // Created by huxijie on 17-3-11. // 竖式填空 #include <iostream> #include <string> #include <sstream> #include <cmath> using namespace std; void calculate(int j,int xArray[],int mark,int &tmpLeftResult,int &tmpXCount,int counts[],int i,int rightResult); int main() { int n; cin>>n; int counts[n]; //每个式子的解法个数 string str[2]; //存放加数和被加数 int leftResult = 0; //等式左边的和 int rightResult = 0; //等式右边的和 int xCounts = 0; //X的个数 int xArray[6]; //存放未知位X的位置 int mark = 10; //用来标记X是最高位 stringstream stream; for(int i=0;i<n;i++) { counts[i] = 0; leftResult = 0; rightResult = 0; xCounts = 0; for(int j=0;j<2;j++) { cin>>str[j]; int length = str[j].length(); //整个数的位数 for(int k=0;k<length;k++) { //从最高位开始判断是否是X if (str[j][k] == 'X') { if (k != length - 1) { xArray[xCounts ] = length - k; //在这个数中X是第几位 } else { //表示是最高位 xArray[xCounts ] = length - k + mark ; //通过加上10来标记 } xCounts ++; }else { int tmp; stream<<str[j][k]; stream>>tmp; leftResult += tmp*pow(10,length-k-1); stream.clear(); } } } cin>>rightResult ; int tmpLeftResult = leftResult; int tmpXCount = xCounts ; calculate(0,xArray,mark ,tmpLeftResult,tmpXCount,counts,i,rightResult ); } for(int i=0;i<n;i++) { cout<<counts[i]<<endl; } return 0; } void calculate(int j,int xArray[],int mark,int &tmpLeftResult,int &tmpXCount,int counts[],int i,int rightResult){ if (tmpXCount>0) { if (xArray[j] > mark ) { //该X是最高位，最高位不能是0 for (int m = 1; m <= 9; m++) { tmpLeftResult += m * pow(10, xArray[j]-mark - 1); tmpXCount--; if (tmpLeftResult > rightResult ) { tmpLeftResult -= m * pow(10, xArray[j]-mark - 1); tmpXCount++; return; } else if (tmpLeftResult == rightResult && tmpXCount == 0) { counts[i]++; tmpXCount++; tmpLeftResult -= m * pow(10, xArray[j]-mark - 1); return; } else if (tmpLeftResult < rightResult && tmpXCount > 0) { calculate(++j, xArray, mark , tmpLeftResult, tmpXCount, counts, i, rightResult ); j--; tmpLeftResult -= m * pow(10, xArray[j] - mark - 1); tmpXCount++; } else { tmpLeftResult -= m * pow(10, xArray[j]-mark - 1); tmpXCount++; } } }else { for (int m = 0; m <= 9; m++) { tmpLeftResult += m * pow(10, xArray[j] - 1); tmpXCount--; if (tmpLeftResult > rightResult ) { tmpLeftResult -= m * pow(10, xArray[j] - 1); tmpXCount++; return; } else if (tmpLeftResult == rightResult && tmpXCount == 0) { counts[i]++; tmpXCount++; tmpLeftResult -= m * pow(10, xArray[j] - 1); return; } else if (tmpLeftResult < rightResult && tmpXCount > 0) { calculate(++j, xArray, mark , tmpLeftResult, tmpXCount, counts, i, rightResult ); j--; tmpLeftResult -= m * pow(10, xArray[j] - 1); tmpXCount++; } else { tmpLeftResult -= m * pow(10, xArray[j] - 1); tmpXCount++; } } } }else { calculate(++j, xArray, mark , tmpLeftResult, tmpXCount, counts, i, rightResult ); } return; }