前言

老师在纸上写了两个正整数,
把它们的和告诉了小红,
把它们的积告诉了小明。 老师说:这两个正整数可能相等也可能不相等。
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 = 42 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就知道了



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



先上个基础款

  1. package com.company;
  2. /**
  3. * 原题
  4. * 老师在纸上写了两个正整数,
  5. * 把它们的和告诉了小红,
  6. * 把它们的积告诉了小明。
  7. * 老师说:这两个正整数可能相等也可能不相等。
  8. * 1. 小明说:我不知道这两个数是多少。
  9. * 2. 小红说:我也不知道这两个数是多少。
  10. * 3. 小明说:我现在知道了。
  11. * 请问这两个数到底是多少?
  12. *
  13. * 思路
  14. * 结合 1,说明小明得到的数字 分解成 x * y 可能性不唯一
  15. * 结合 2,说明小红得到的数字 分解成 x + y 再结合成 x * y 结果依旧不唯一
  16. * 结合 3,说明小明得到的数字 分解成 x * y 再结合成 x + y 可以得到多个结果,但只有一个小红不能唯一,其余结果小红在2中必能解开
  17. */
  18. public class Main {
  19. /**
  20. * 判断是否为素数
  21. */
  22. public static boolean isPrime(int number) {
  23. for (int i = 2; i < number; i++) {
  24. if (number % i != 0) {
  25. continue;
  26. }
  27. return false;
  28. }
  29. return true;
  30. }
  31. /**
  32. * 排除不合格的数字b
  33. * 拆解b 后模拟乘 不为素数的可能性必须大于2
  34. */
  35. public static boolean checkNumberB(int number) {
  36. int count = 0;
  37. for (int i = 1; i <= number / 2; i++) {
  38. int x = i;
  39. int y = number - i;
  40. if(!isPrime(x * y)){
  41. count ++;
  42. }
  43. }
  44. return count < 2;
  45. }
  46. /**
  47. * 能进入这里说明不是素数
  48. * 拆解a 后模拟加
  49. */
  50. public static boolean checkNumberA(int number) {
  51. int count = 0;
  52. for (int i = 1; i <= Math.sqrt(number); i++) {
  53. // 能整除
  54. if(number % i == 0){
  55. int x = i;
  56. int y = number / i;
  57. // 核心就是这句话 套娃
  58. if(checkNumberB(x + y)){
  59. count ++;
  60. }
  61. }
  62. }
  63. // a这个数字拆分完 模拟完 只允许出现一个能通过的可能性 否则都不符合问题3
  64. return count != 1;
  65. }
  66. /**
  67. * 核心算法
  68. */
  69. public static void core() {
  70. for (int i = 1; i < 100; i++) {
  71. for (int j = 1; j < 100; j++) {
  72. int a = i * j;
  73. int b = i + j;
  74. // 对应问题1 a 不能是素数
  75. if (isPrime(a)) {
  76. continue;
  77. }
  78. // 对应问题2 b 拆分后模拟 i*j所有可能性能通过验算
  79. if(checkNumberB(b)){
  80. continue;
  81. }
  82. // 对应问题3 略
  83. if(checkNumberA(a)){
  84. continue;
  85. }
  86. // 上面3个逻辑排除完 还没被排除的就是正确答案 i 和 j 就是那2个数,a 是积,b 是和
  87. System.out.println("i = " + i + " , j = " + j + " , a = " + a + " , b = " + b);
  88. }
  89. }
  90. }
  91. public static void main(String[] args) {
  92. core();
  93. }
  94. }



运行结果如下

  1. i = 1 , j = 4 , a = 4 , b = 5
  2. i = 4 , j = 1 , a = 4 , b = 5

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



代码如下

  1. package com.company;
  2. import java.util.concurrent.ExecutorService;
  3. import java.util.concurrent.Executors;
  4. /**
  5. * 原题
  6. * 老师在纸上写了两个正整数,
  7. * 把它们的和告诉了小红,
  8. * 把它们的积告诉了小明。
  9. * 老师说:这两个正整数可能相等也可能不相等。
  10. * 1. 小明说:我不知道这两个数是多少。
  11. * 2. 小红说:我也不知道这两个数是多少。
  12. * 3. 小明说:我现在知道了。
  13. * 请问这两个数到底是多少?
  14. * <p>
  15. * 思路
  16. * 结合 1,说明小明得到的数字 分解成 x * y 可能性不唯一
  17. * 结合 2,说明小红得到的数字 分解成 x + y 再结合成 x * y 结果依旧不唯一
  18. * 结合 3,说明小明得到的数字 分解成 x * y 再结合成 x + y 可以得到多个结果,但只有一个小红不能唯一,其余结果小红在2中必能解开
  19. */
  20. public class Main {
  21. /**
  22. * 判断是否为素数
  23. */
  24. public static boolean isPrime(int number) {
  25. for (int i = 2; i < number; i++) {
  26. if (number % i != 0) {
  27. continue;
  28. }
  29. return false;
  30. }
  31. return true;
  32. }
  33. /**
  34. * 排除不合格的数字b
  35. * 拆解b 后模拟乘 不为素数的可能性必须大于2
  36. */
  37. public static boolean checkNumberB(int number) {
  38. int count = 0;
  39. for (int i = 1; i <= number / 2; i++) {
  40. int x = i;
  41. int y = number - i;
  42. if (!isPrime(x * y)) {
  43. count++;
  44. }
  45. }
  46. return count < 2;
  47. }
  48. /**
  49. * 能进入这里说明不是素数
  50. * 拆解a 后模拟加
  51. */
  52. public static boolean checkNumberA(int number) {
  53. int count = 0;
  54. for (int i = 1; i <= Math.sqrt(number); i++) {
  55. // 能整除
  56. if (number % i == 0) {
  57. int x = i;
  58. int y = number / i;
  59. // 核心就是这句话 套娃
  60. if (checkNumberB(x + y)) {
  61. count++;
  62. }
  63. }
  64. }
  65. // 只能存在一个通过套娃 checkNumberB 的结果
  66. return count != 1;
  67. }
  68. /**
  69. * 核心算法
  70. */
  71. @SuppressWarnings("AlibabaThreadPoolCreation")
  72. public void core(int nThreads) {
  73. ExecutorService executorService = Executors.newFixedThreadPool(nThreads);
  74. for (int i = 1; i < 1000; i++) {
  75. for (int j = 1; j < 1000; j++) {
  76. executorService.submit(new CalcThread(i,j));
  77. }
  78. }
  79. executorService.shutdown();
  80. }
  81. public static void main(String[] args) {
  82. // 开200个线程去跑
  83. new Main().core(200);
  84. }
  85. class CalcThread extends Thread {
  86. private int i;
  87. private int j;
  88. public CalcThread(int i , int j){
  89. this.i = i;
  90. this.j = j;
  91. }
  92. @Override
  93. public void run() {
  94. int a = i * j;
  95. int b = i + j;
  96. // 对应问题1 a 不能是素数
  97. if (isPrime(a)) {
  98. return;
  99. }
  100. // 对应问题2 b 拆分后模拟 i*j所有可能性能通过验算
  101. if (checkNumberB(b)) {
  102. return;
  103. }
  104. // 对应问题3 略
  105. if (checkNumberA(a)) {
  106. return;
  107. }
  108. // 上面3个逻辑排除完 还没被排除的就是正确答案 i 和 j 就是那2个数,a 是积,b 是和
  109. System.out.println("i = " + i + " , j = " + j + " , a = " + a + " , b = " + b);
  110. }
  111. }
  112. }



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


运行结果如下

  1. i = 1 , j = 4 , a = 4 , b = 5
  2. i = 4 , j = 1 , a = 4 , b = 5



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

END