用 Java 解数学题之 <老师在纸上写了两个正整数... >

home 编辑时间 2021/06/09

![](/api/file/getImage?fileId=60c06cd816199b501c025ba0)
 
## 前言

![](/api/file/getImage?fileId=60c0732716199b501c025ba9)

> 老师在纸上写了两个正整数，
把它们的和告诉了小红，
把它们的积告诉了小明。 老师说：这两个正整数可能相等也可能不相等。
> 1. 小明说：我不知道这两个数是多少。
> 2. 小红说：我也不知道这两个数是多少。
> 3. 小明说：我现在知道了。 请问这两个数到底是多少？

原题如上，是在某个b站up主的视频里看到的
我是感觉这题非常适合写成代码让计算机来算
说干就干，用java8实现了一个基础草率版本的算法

## 折腾
先简单还原一下现场过程

小明得到4，可以拆分出 `1 x 4` 或者 `2 x 2`
这里可能出现的答案明显不唯一
故问1， 小明回答，不知道

假设这里能通过，小明得到的只能是素数
比如小明拿到3 必然马上拆分出是 `1 x 3`
这里没通过，也说明小明必然没拿到素数

小红得到5，可以拆分出 `1 + 4` 或者 `2 + 3`
套娃小明分析得出 `1 x 4 = 4` ， `2 x 3 = 6` 
4和6都不是素数，都存在可能，答案明显不唯一
故问2， 小红回答，不知道

最后小明个zz回答知道了
这只存在一种可能，就是小明套娃小红套娃小明后，所有的可能性里，只存在一个分支，是小红不知道，其余小红必知道。
回到数学上，刚才说
小明是4，分析自己可以是 `1 x 4` 或者 `2 x 2` 
套娃小红后 小红只能是 `1 + 4 = 5` 或者 `2 + 2 = 4`
如果小红是 5 
可以分析成 `1 + 4 = 5` 或者 `2 + 3 = 5`
套娃小明后得出 `1 x 4 = 4` 或者 `2 x 3 = 6`
如果小红是 4 
可以分析成 `1 + 3 = 4` 或者 `2 + 2 = 4`
套娃小明后得出 `1 x 3 = 3` 或者 `2 x 2 = 4`
这种情况是绝对不可能出现的，因为如果小明是3
第一回合，小明必知道自己是 `1 x 3` 或者 `3 x 1`
所以如果小红是4，第二回合能直接排除掉1 和 3，只能是2 和 2
小红说不知道，所以小红也必不可能是 4
那么小红只能是5， `1 + 4 = 5` 或者 `4 + 1 = 5`
小明个zz就知道了

说的有点啰嗦，反正就是这个意思，下面上代码

先上个基础款
```java
package com.company;

/**
 * 原题
 * 老师在纸上写了两个正整数，
 * 把它们的和告诉了小红，
 * 把它们的积告诉了小明。
 * 老师说：这两个正整数可能相等也可能不相等。
 * 1. 小明说：我不知道这两个数是多少。
 * 2. 小红说：我也不知道这两个数是多少。
 * 3. 小明说：我现在知道了。
 * 请问这两个数到底是多少？
 *
 * 思路
 * 结合 1，说明小明得到的数字 分解成 x * y 可能性不唯一
 * 结合 2，说明小红得到的数字 分解成 x + y 再结合成 x * y 结果依旧不唯一
 * 结合 3，说明小明得到的数字 分解成 x * y 再结合成 x + y 可以得到多个结果，但只有一个小红不能唯一，其余结果小红在2中必能解开
 */

public class Main {

/**
 * 判断是否为素数
 */
 public static boolean isPrime(int number) {
 for (int i = 2; i < number; i++) {
 if (number % i != 0) {
 continue;
 }
 return false;
 }
 return true;
 }

/**
 * 排除不合格的数字b
 * 拆解b 后模拟乘 不为素数的可能性必须大于2
 */
 public static boolean checkNumberB(int number) {
 int count = 0;
 for (int i = 1; i <= number / 2; i++) {
 int x = i;
 int y = number - i;
 if(!isPrime(x * y)){
 count ++;
 }
 }
 return count < 2;
 }

/**
 * 能进入这里说明不是素数
 * 拆解a 后模拟加
 */
 public static boolean checkNumberA(int number) {
 int count = 0;
 for (int i = 1; i <= Math.sqrt(number); i++) {
 // 能整除
 if(number % i == 0){
 int x = i;
 int y = number / i;
 // 核心就是这句话 套娃
 if(checkNumberB(x + y)){
 count ++;
 }
 }
 }
 // a这个数字拆分完 模拟完 只允许出现一个能通过的可能性 否则都不符合问题3
 return count != 1;
 }

/**
 * 核心算法
 */
 public static void core() {
 for (int i = 1; i < 100; i++) {
 for (int j = 1; j < 100; j++) {
 int a = i * j;
 int b = i + j;
 // 对应问题1 a 不能是素数
 if (isPrime(a)) {
 continue;
 }
 // 对应问题2 b 拆分后模拟 i*j所有可能性能通过验算
 if(checkNumberB(b)){
 continue;
 }
 // 对应问题3 略
 if(checkNumberA(a)){
 continue;
 }
 // 上面3个逻辑排除完 还没被排除的就是正确答案 i 和 j 就是那2个数，a 是积，b 是和
 System.out.println("i = " + i + " , j = " + j + " , a = " + a + " , b = " + b);
 }
 }
 }

public static void main(String[] args) {
        core();
    }
}
```

运行结果如下
```java
i = 1 , j = 4 , a = 4 , b = 5
i = 4 , j = 1 , a = 4 , b = 5
```

上述代码已得到正确答案，但我设置的范围是100以内，如果数字设置过大，运算复杂度高，会非常缓慢。当然我也能估计出来，可以用数学的方法，来证明只存在这一组答案，不需要计算大范围。但我还是想锻炼一下我的AMD 4800H CPU，所以这里再加上多线程试试

代码如下
```java
package com.company;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * 原题
 * 老师在纸上写了两个正整数，
 * 把它们的和告诉了小红，
 * 把它们的积告诉了小明。
 * 老师说：这两个正整数可能相等也可能不相等。
 * 1. 小明说：我不知道这两个数是多少。
 * 2. 小红说：我也不知道这两个数是多少。
 * 3. 小明说：我现在知道了。
 * 请问这两个数到底是多少？
 * 
 * 思路
 * 结合 1，说明小明得到的数字 分解成 x * y 可能性不唯一
 * 结合 2，说明小红得到的数字 分解成 x + y 再结合成 x * y 结果依旧不唯一
 * 结合 3，说明小明得到的数字 分解成 x * y 再结合成 x + y 可以得到多个结果，但只有一个小红不能唯一，其余结果小红在2中必能解开
 */

public class Main {

/**
 * 排除不合格的数字b
 * 拆解b 后模拟乘 不为素数的可能性必须大于2
 */
 public static boolean checkNumberB(int number) {
 int count = 0;
 for (int i = 1; i <= number / 2; i++) {
 int x = i;
 int y = number - i;
 if (!isPrime(x * y)) {
 count++;
 }
 }
 return count < 2;
 }

/**
 * 能进入这里说明不是素数
 * 拆解a 后模拟加
 */
 public static boolean checkNumberA(int number) {
 int count = 0;
 for (int i = 1; i <= Math.sqrt(number); i++) {
 // 能整除
 if (number % i == 0) {
 int x = i;
 int y = number / i;
 // 核心就是这句话 套娃
 if (checkNumberB(x + y)) {
 count++;
 }
 }
 }
 // 只能存在一个通过套娃 checkNumberB 的结果
 return count != 1;
 }

/**
 * 核心算法
 */
 @SuppressWarnings("AlibabaThreadPoolCreation")
 public void core(int nThreads) {
 ExecutorService executorService = Executors.newFixedThreadPool(nThreads);
 for (int i = 1; i < 1000; i++) {
 for (int j = 1; j < 1000; j++) {
 executorService.submit(new CalcThread(i,j));

}
        }
        executorService.shutdown();
    }

public static void main(String[] args) {
        // 开200个线程去跑
        new Main().core(200);
    }

class CalcThread extends Thread {
        private int i;
        private int j;

public CalcThread(int i , int j){
            this.i = i;
            this.j = j;
        }

@Override
        public void run() {
            int a = i * j;
            int b = i + j;
            // 对应问题1 a 不能是素数
            if (isPrime(a)) {
                return;
            }
            // 对应问题2 b 拆分后模拟 i*j所有可能性能通过验算
            if (checkNumberB(b)) {
                return;
            }
            // 对应问题3 略
            if (checkNumberA(a)) {
                return;
            }
            // 上面3个逻辑排除完 还没被排除的就是正确答案 i 和 j 就是那2个数，a 是积，b 是和
            System.out.println("i = " + i + " , j = " + j + " , a = " + a + " , b = " + b);
        }
    }
}
```

**注意我这里开200个线程还能正常操作，如果你的电脑CPU不太能经受得起锻炼，少开点线程试试水，开个16线程足以**

运行结果如下
```java
i = 1 , j = 4 , a = 4 , b = 5
i = 4 , j = 1 , a = 4 , b = 5
```

![](/api/file/getImage?fileId=60c07c8b16199b501c025bc0)

最后运行结果还是意料之中的，但cpu曲线图异常的优美，另外温度也很感人。速度的话远不及预期，可能是因为数字越大，越卷。。。

## END

送人玫瑰,手留余香