路
- 缘起
- 代码地址
- 枚举
- 题1
- 题2
- 题2 - Plus
- 完整代码
缘起
各位小伙伴们好呀！本人最近看了下《啊哈算法》，写的确实不错。
但稍显遗憾的是，书籍示例代码是c语言，而不是本人常用的Java。
那就弥补遗憾，说干就干，把这本书的示例语言用java写一遍， 顺带附上一些自己的理解！
今天这篇博客讲的是如何用枚举来解一些奥数题。
来不及买纸质书但又想尽快感受算法魅力的童鞋也甭担心，电子版的下载链接已经放到下方了，可尽情下载。
链接：https://pan.baidu.com/s/1imxiElcCorw2F-HJEnB-PA?pwd=jmgs
提取码：jmgs
代码地址
本文代码已开源：
git clone https://gitee.com/guqueyue/my-blog-demo.git
请切换到gitee分支，
然后查看aHaAlgorithm模块下的src/main/java/com/guqueyue/aHaAlgorithm/chapter_3_Enum即可！
枚举
按照惯例，首先我们来介绍一下枚举的概念：
枚举，又称穷举，说白了就是利用计算机的性能优势，暴力的穷尽每一种可能性，最后找到符合条件的情况。
这种思想很普遍、常用，反正遍历就对了！
下面，我们用三个奥数题，来揭开枚举的奥秘。
题1
小哼在数学课上遇到一道奥数题是这样的，口3x6528=30x8256,在两个口内填入相同的数字使得等式成立。
这一题很简单，直接遍历1-9这9个数字，看等式是否成立即可，轻松拿下：
/**
* @Description ：[]3 x 6528 = 3[] x 8256, 再两个[]内填入相同的数字使得等式成立
* @Param []
* @return void
**/
private static void test1() {
for (int i = 1; i <= 9; i++) {
if ((i * 10 + 3) * 6528 == (30 + i) * 8256) {
System.out.println(i + "3 x 6528 = 3"+ i +" x 8256");
}
}
}
运行得(完整代码已开源，或者在后面查看)：
题2
现在小哼又遇到一个稍微复杂一点的奥数题， 000+000-000,将数字1~9分别填入9个口中，每个数字只能使用一次使得等式成 立。例如173+286= 459就是一个合理的组合，请问一共有多少种合理的组合呢?注意: 173+286= 459 与286+173= 459是同一种组合 !
那么，这个题怎么做呢？
我们直接声明9个变量分别表示每个数，然后再采用9个for循环来暴力穷举每种情况，看看是否符合条件，并统计：
/**
* @Description ：[][][] + [][][] = [][][], 分别填入 1-9，有多少种填法？
* a b c d e f g h i
* @Param []
* @return void
**/
private static void test2() {
int a, b, c, d, e, f, g, h, i, total = 0;
for (a = 1; a <= 9; a++) {
for (b = 1; b <= 9; b++) {
for (c = 1; c <= 9; c++) {
for (d = 1; d <= 9; d++) {
for (e = 1; e <= 9; e++) {
for (f = 1; f <= 9; f++) {
for (g = 1; g <= 9; g++) {
for (h = 1; h <= 9; h++) {
for (i = 1; i <= 9; i++) {
if (a != b && a != c && a != d && a != e && a != f && a != g && a != h && a != i
&& b != c && b != d && b != e && b != f && b != g && b != h && b != i
&& c != d && c != e && c != f && c != g && c != h && c != i
&& d != e && d != f && d != g && d != h && d != i
&& e != f && e != g && e != h && e != i
&& f != g && f != h && f != i
&& g != h && g != i
&& h != i
&& a * 100 + b * 10 + c + d * 100 + e * 10 + f == g * 100 + h * 10 + i
) {
System.out.println("" + a + b + c + " + " + d + e + f + " = " + g + h + i);
total++;
}
}
}
}
}
}
}
}
}
}
System.out.println("情况为（种）：" + total/2);
}
运行得(完整代码已开源，或者在后面查看)：
题2 - Plus
看了上文的代码，估计大家会觉得很恐怖，毕竟我打都打了半天。
如果要用一句歇后语来形容，那就是：封建社会老太太的裹脚布 —— 又臭又长。
上文的代码主要有两个问题：
- 声明变量太多容易让人搞错。
- 确定每个数互不相等的逻辑太过于冗长，简直让人崩溃。
那么，要怎么优化呢？我这里就不卖关子了，直接给出解决方案：
- 变量的话可以直接声明一个数组，不同的索引位置来存放不同数，清晰明了方便。
- 确定每个数互不相等的部分，可以采用一个标记数组：如果有这个数，标记为1；无，则标记为0。最后，将标记数组相加，若和为9，则每个数都互不相同。
优化代码如下：
/**
* @Description ：[][][] + [][][] = [][][], 分别填入 1-9，有多少种填法？
* a b c d e f g h i
* @Param []
* @return void
**/
private static void test2Plus() {
int[] a = new int[9]; // 用于存储
int[] book = new int[10]; // 用于标记数字
int total = 0;
for (a[0] = 1; a[0] <= 9; a[0]++) {
for (a[1] = 1; a[1] <= 9; a[1]++) {
for (a[2] = 1; a[2] <= 9; a[2]++) {
for (a[3] = 1; a[3] <= 9; a[3]++) {
for (a[4] = 1; a[4] <= 9; a[4]++) {
for (a[5] = 1; a[5] <= 9; a[5]++) {
for (a[6] = 1; a[6] <= 9; a[6]++) {
for (a[7] = 1; a[7] <= 9; a[7]++) {
for (a[8] = 1; a[8] <= 9; a[8]++) {
// 初始化 book 数组
for (int i = 1; i < 10; i++) {
book[i] = 0;
}
// 标记
for (int i = 0; i < 9; i++) {
book[a[i]] = 1;
}
int sum = 0;
for (int i = 1; i <= 9; i++) {
sum += book[i];
}
if (sum == 9
&& a[0] * 100 + a[1] * 10 + a[2] + a[3] * 100 + a[4] * 10 + a[5] == a[6] * 100 + a[7] * 10 + a[8]) {
System.out.println("" + a[0] + a[1] + a[2] + " + " + a[3] + a[4] + a[5] + " = " + a[6] + a[7] + a[8]);
total++;
}
}
}
}
}
}
}
}
}
}
System.out.println("情况为（种）：" + total/2);
}
是不是好很多呢？运行，可得(完整代码已开源，或者在后面查看)：
完整代码
package com.guqueyue.aHaAlgorithm.chapter_3_Enum;
/**
* @Author: guqueyue
* @Description: 枚举求奥数题
* @Date: 2024/1/16
**/
public class Test {
public static void main(String[] args) {
// test1();
// test2();
test2Plus();
}
/**
* @Description ：[]3 x 6528 = 3[] x 8256, 再两个[]内填入相同的数字使得等式成立
* @Param []
* @return void
**/
private static void test1() {
for (int i = 1; i <= 9; i++) {
if ((i * 10 + 3) * 6528 == (30 + i) * 8256) {
System.out.println(i + "3 x 6528 = 3"+ i +" x 8256");
}
}
}
/**
* @Description ：[][][] + [][][] = [][][], 分别填入 1-9，有多少种填法？
* a b c d e f g h i
* @Param []
* @return void
**/
private static void test2() {
int a, b, c, d, e, f, g, h, i, total = 0;
for (a = 1; a <= 9; a++) {
for (b = 1; b <= 9; b++) {
for (c = 1; c <= 9; c++) {
for (d = 1; d <= 9; d++) {
for (e = 1; e <= 9; e++) {
for (f = 1; f <= 9; f++) {
for (g = 1; g <= 9; g++) {
for (h = 1; h <= 9; h++) {
for (i = 1; i <= 9; i++) {
if (a != b && a != c && a != d && a != e && a != f && a != g && a != h && a != i
&& b != c && b != d && b != e && b != f && b != g && b != h && b != i
&& c != d && c != e && c != f && c != g && c != h && c != i
&& d != e && d != f && d != g && d != h && d != i
&& e != f && e != g && e != h && e != i
&& f != g && f != h && f != i
&& g != h && g != i
&& h != i
&& a * 100 + b * 10 + c + d * 100 + e * 10 + f == g * 100 + h * 10 + i
) {
System.out.println("" + a + b + c + " + " + d + e + f + " = " + g + h + i);
total++;
}
}
}
}
}
}
}
}
}
}
System.out.println("情况为（种）：" + total/2);
}
/**
* @Description ：[][][] + [][][] = [][][], 分别填入 1-9，有多少种填法？
* a b c d e f g h i
* @Param []
* @return void
**/
private static void test2Plus() {
int[] a = new int[9]; // 用于存储
int[] book = new int[10]; // 用于标记数字
int total = 0;
for (a[0] = 1; a[0] <= 9; a[0]++) {
for (a[1] = 1; a[1] <= 9; a[1]++) {
for (a[2] = 1; a[2] <= 9; a[2]++) {
for (a[3] = 1; a[3] <= 9; a[3]++) {
for (a[4] = 1; a[4] <= 9; a[4]++) {
for (a[5] = 1; a[5] <= 9; a[5]++) {
for (a[6] = 1; a[6] <= 9; a[6]++) {
for (a[7] = 1; a[7] <= 9; a[7]++) {
for (a[8] = 1; a[8] <= 9; a[8]++) {
// 初始化 book 数组
for (int i = 1; i < 10; i++) {
book[i] = 0;
}
// 标记
for (int i = 0; i < 9; i++) {
book[a[i]] = 1;
}
int sum = 0;
for (int i = 1; i <= 9; i++) {
sum += book[i];
}
if (sum == 9
&& a[0] * 100 + a[1] * 10 + a[2] + a[3] * 100 + a[4] * 10 + a[5] == a[6] * 100 + a[7] * 10 + a[8]) {
System.out.println("" + a[0] + a[1] + a[2] + " + " + a[3] + a[4] + a[5] + " = " + a[6] + a[7] + a[8]);
total++;
}
}
}
}
}
}
}
}
}
}
System.out.println("情况为（种）：" + total/2);
}
}
