蓝桥杯决赛 cc++ c组 第二题 最大乘积（c++描述）

题目：

标题：最大乘积

把 1~9 这9个数字分成两组，中间插入乘号， 有的时候，它们的乘积也只包含1~9这9个数字，而且每个数字只出现1次。

比如： 984672 * 351 = 345619872 98751 * 3462 = 341875962 9 * 87146325 = 784316925 …

符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？

---

思路：

深搜解题，深搜不难，较难点在查重和相乘。 原数查重： 原数直接两重for循环查重即可。 相乘求积： 如无重则记录数字，然后用 / % 求出前后两段进行相乘，n表示的是拆分位置，每次结束后向右移一位。 乘积查重： 由于数字不好查重，则转为字符串进行查重，检查完毕若没有重复，则再转为int与前一个存储数据比较大小，如大于则存入。 答案： 839542176

---

代码：

#include <iostream> #include <string> using namespace std; int index[15], value[15]; int max; // 最大的符合要求数 void check() { // 查重 for (int i = 1; i < 9; i++) { for (int j = i + 1; j < 10; j++) { if (value[i] == value[j]) { return; } } } // 记录数字 int sum = value[1] * 100000000 + value[2] * 10000000 + value[3] * 1000000 + value[4] * 100000 + value[5] * 10000 + value[6] * 1000 + value[7] * 100 + value[8] * 10 + value[9]; int n = 100000000; // 分割 int s = 1; // 控制 for (int i = 0; i < 8; i++) { // 拆分相乘 int v = sum / n; int h = sum % n; n /= 10; string str = to_string(v * h); // 转为字符串 方便查重 s = 1; // if条件控制 for (int i = 0; i < str.length() - 1; i++) { for (int j = i + 1; j < str.length(); j++) { if (str[i] == str[j] || str[i] == '0') // 有重复或有0则退出本次循环 { s = 0; break; } } if (s == 0) { break; } } if (s && atoi(str.c_str()) > max) // 转回int型 进行大小比较 { max = atoi(str.c_str()); } } } void dfs(int x) { if (x == 10) { check(); return; } for (int i = 1; i < 10; i++) { if (index[i] == 0) { index[i] = 1; value[x] = i; dfs(x + 1); index[i] = 0; } } } int main() { dfs(1); cout << max << endl; // 输出答案 return 0; }

printf(“看到最后了点个赞吧！”); cout << “点个赞吧！”; Console.WriteLine(“点个赞吧！”); System.out.println(“点个赞吧！”); print(“点个赞吧！”)