LQ0046 凑算式【枚举】

题目出处：蓝桥杯2016初赛 C++ B组C题

题目描述
这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？

输出格式
输出一个整数表示答案

问题分析
求解法数量，需要枚举所有的可能，使用置换函数next_permutation()得到全排列再行计算，程序代码最为简洁。
可以用多重循环来实现枚举，也可以用DFS来实现枚举。
程序计算结果得29。

AC的C++语言程序如下：

/* LQ0046 凑算式 */

#include 
#include 

using namespace std;

double a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

int main()
{
    int cnt = 0;
    do {
        double sum = a[0] + a[1] / a[2]
                + (a[3] * 100 + a[4] * 10 +a[5]) / (a[6] * 100 + a[7] * 10 + a[8]);
        if (sum == 10.0) cnt++;
    } while (next_permutation(a, a + 9));

    printf("%d\n", cnt);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22