《网易游戏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;
}

最后

以上就是明理小熊猫为你收集整理的《网易游戏2017互娱》实习笔试编程一：竖式填空的全部内容，希望文章能够帮你解决《网易游戏2017互娱》实习笔试编程一：竖式填空所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。