枚举及优化（一）.课后附加题2.牛式

Question

下面是一个乘法竖式，如果用我们给定的那几个数字来取代 * ，可以使式子成立的话，我们就叫这个式子牛式。

---

x * *

---

---

---

---

数字只能取代 * ，当然第一位不能为 0 。

写一个程序找出所有的牛式。

输入格式

第一行一个整数 N ，代表数字的个数。

第二行 : N 个用空格分开的数字 ( 每个数字都 ∈ { 1,2,3,4,5,6,7,8,9 } )。

输出格式

一个数字。表示牛式的总数。

样例

输入数据 1
5
2 3 4 6 8
输出数据 1
1

Answer 1

♥ 该回答参考ChatGPT，由吾为汝整理提供，如若有用，还请题主采纳！♥

为了找出所有可能的牛式，我们需要通过枚举所有可能的数字组合来替代乘法竖式中的星号（*）。在这个问题中，我们有一个乘法竖式的形式：

  x * *
× * * *
---------
  * * *

我们需要确保替代的数字满足乘法的正确性，并且第一位不能为0。以下是一个 C++ 程序的实现，来解决这个问题：

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

// 函数来检查给定的数字组合是否形成一个有效的牛式
bool isValidCowStyle(int x, int y, int z, int a, int b, int c) {
    int product1 = x * 10 + y; // x * y
    int product2 = z * 100 + a * 10 + b; // z * (a b c)
    int result = product1 * z; // 结果

    // 计算竖式的结果
    int expectedResult = (product1 * (c + 10 * b)); // 竖式的结果

    return result == expectedResult;
}

int main() {
    int N;
    cin >> N;
    vector<int> digits(N);
    for (int i = 0; i < N; ++i) {
        cin >> digits[i];
    }

    set<int> uniqueCowStyles; // 用于存储唯一的牛式组合
    int count = 0;

    // 枚举所有可能的组合
    for (int x : digits) {
        for (int y : digits) {
            for (int z : digits) {
                for (int a : digits) {
                    for (int b : digits) {
                        for (int c : digits) {
                            // 确保第一位不为0
                            if (x != 0 && z != 0) {
                                if (isValidCowStyle(x, y, z, a, b, c)) {
                                    count++;
                                    uniqueCowStyles.insert(x * 10000 + y * 1000 + z * 100 + a * 10 + b * 1 + c);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    cout << count << endl; // 输出牛式的总数
    return 0;
}

代码说明：

1. 输入处理：首先读取数字的个数和具体的数字。
2. 组合枚举：使用六重循环来枚举所有可能的数字组合。
3. 有效性检查：通过 isValidCowStyle 函数检查当前组合是否形成有效的牛式。
4. 结果输出：最后输出符合条件的牛式总数。

注意事项：

• 代码中使用了 set 来存储唯一的牛式组合，确保不重复计数。
• 需要确保输入的数字不包含0，并且在组合时第一位数字不能为0。

（如若有用，还请题主采纳！）