【逻辑题】经典的“12枚硬币称量问题”

jgdfc 发表于 2022-8-12 18:31

本帖最后由 jgdfc 于 2022-8-12 18:36 编辑

问题描述：
12枚硬币，其中11枚真币1枚假币，现有一架天平，最少称多少次可以找出这枚假币并且知道假币和真币的相对重量。

先求最少次数
总共12枚硬币,假币有俩种可能:轻或重,所以共12*2=24可能
每次称重有3种可能,左轻,平衡,右轻,3次称量可以获得的信息是3^3=27
所以理论上3次可行

本质是利用信息熵去解决，每次称量尽量造成信息熵减少（类似于动态规划）。
注：可获得信息大于信息熵时是理论上可行，实际中有不可行的情况，比如需要借一个正常硬币才能称量出来。

第一种方法解法
[*]每个方框表示当前的状态，即哪些硬币可能会重，哪些硬币可能会轻。
[*]每个菱形框表示所做的判断，即将哪些硬币用于称量。
此图版权所有：littlefall
https://attach.52pojie.cn//forum/202208/12/181828bpo2pg988b9lb9bp.png?l

这种方法如何转换成程序呢?
``` java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Demo {
Integer yingBiSize = 12;
//硬币
List<Integer> yingBi = new ArrayList<>();
//结果可能性
List<List<Integer>> result = new ArrayList<>();
//称重次数
int limit = 1;

//集合
List<Integer> kn1 = new ArrayList<>();
//[-1,0]集合
List<Integer> kn2Minus = new ArrayList<>();
//集合
List<Integer> kn2Positive = new ArrayList<>();
//[-1,0,1]集合
List<Integer> kn3 = new ArrayList<>();

/**
* 设置第number个硬币的质量偏差为deviation
* number从0起,范围, deviation范围[-1,0,1]
*/
public Demo(int number, int deviation) {
   for (int i = 0; i < yingBiSize; i++) {
         yingBi.add(number == i?deviation:0);
         result.add(new ArrayList<Integer>(Arrays.asList(-1,0,1)));
         kn3.add(i);
   }

}

/**
* 比较重量 -1 左轻 ; 0 平衡 ; 1 右轻
* @Param left
* @param right
* @return
*/
public Integer compare(List<Integer> left,List<Integer> right){
   int leftSum = left.stream().mapToInt(x -> yingBi.get(x)).sum();
   int rightSum = right.stream().mapToInt(x -> yingBi.get(x)).sum();
   int i = leftSum - rightSum;
   System.out.println("第"+(limit++)+"次测量,左为:"+left+"右为"+right+"结果为"+i);
   return i;
}

/**
* 计算这么摆放硬币
* @return
*/
public List<List<Integer>>grouping(){
   List<List<Integer>> paixu = new ArrayList<>();
   //左侧
   List<Integer> left = new ArrayList<>();
   //闲置
   List<Integer> middle = new ArrayList<>();
   //右侧
   List<Integer> right = new ArrayList<>();

   if (kn3.size()>0){
         List<Integer> kn = new ArrayList<>();
         kn.addAll(kn3);
         kn.addAll(kn1);
         for (int i = 0; i < kn.size(); i++) {
            if (i%3 ==0){
               left.add(kn.get(i));
            }else if(i%3 ==1){
               right.add(kn.get(i));
            }else {
               middle.add(kn.get(i));
            }
         }
   }else if(kn2Positive.size() >0 || kn2Minus.size() >0){

         List<Integer> kn = new ArrayList<>();
         if (kn2Positive.size() > kn2Minus.size()) {
            kn.addAll(kn2Positive);
            kn.addAll(kn2Minus);
         } else {
            kn.addAll(kn2Minus);
            kn.addAll(kn2Positive);
         }
         kn.addAll(kn1);
         int kn2Size = kn2Positive.size()+kn2Minus.size();
         int middleSize = kn2Size / 3 ;
         if ( kn2Size % 3 != 0){
            middleSize++;
            middle.addAll(kn.stream().limit(middleSize).collect(Collectors.toList()));
            left.addAll(kn.stream().skip(middleSize).limit(middleSize).collect(Collectors.toList()));
            right.addAll(kn.stream().skip(middleSize* 2L).limit(middleSize).collect(Collectors.toList()));
         }else {
            left.addAll(kn.stream().limit(middleSize).collect(Collectors.toList()));
            right.addAll(kn.stream().skip(middleSize).limit(middleSize).collect(Collectors.toList()));
            middle.addAll(kn.stream().skip(middleSize* 2L).limit(middleSize).collect(Collectors.toList()));
         }
   }
   paixu.add(left);
   paixu.add(middle);
   paixu.add(right);
   return paixu;
}

/**
* 根据结果排除可能性
* @param left
* @param right
* @param compare
* @return
*/
public void checkResult(List<Integer> left,List<Integer> middle,List<Integer> right,Integer compare){
   if (compare==0){
         left.forEach(x ->result.get(x).removeIf(s -> !s.equals(0)));
         right.forEach(x ->result.get(x).removeIf(s -> !s.equals(0)));
   }else {
         middle.forEach(x ->result.get(x).removeIf(s -> !s.equals(0)));
         left.forEach(x ->result.get(x).removeIf(s -> s.equals((-1) * compare)));
         right.forEach(x ->result.get(x).removeIf(s -> s.equals(compare)));
   }

}

/**
* 分析结果
*/
public void interpretationResult(){
   kn1 = new ArrayList<>();
   kn2Minus = new ArrayList<>();
   kn2Positive= new ArrayList<>();
   kn3 = new ArrayList<>();
   for (int i = 0; i < result.size(); i++) {
         if (result.get(i).size()==1){
            kn1.add(i);
         }
         if (result.get(i).size()==2){
            if (result.get(i).get(0).equals(0)){
               kn2Positive.add(i);
            }else {
               kn2Minus.add(i);
            }
         }
         if (result.get(i).size()==3){
            kn3.add(i);
         }
   }
//    System.out.println("排除"+kn1+"号硬币");
//    System.out.println("偏轻"+kn2Minus+"号硬币");
//    System.out.println("偏重"+kn2Positive+"号硬币");
//    System.out.println("未知"+kn3+"号硬币");
   if (kn1.size()==yingBiSize-1){
         if (kn2Minus.size()==1){
            System.out.println("第"+kn2Minus.get(0)+"硬币质量轻");
         }else if(kn2Positive.size()==1) {
            System.out.println("第"+kn2Positive.get(0)+"硬币质量重");
         }
   }
   if (kn1.size()==yingBiSize){
         System.out.println("没有假币");
   }
//    System.out.println(result);
}

public static void main(String[] args) {
   for (int i = 0; i < 12; i++) {
         Demo demo = new Demo(i, 1);
         while (demo.limit<=3){
            List<List<Integer>> grouping = demo.grouping();
            Integer compare = demo.compare(grouping.get(0), grouping.get(2));
            demo.checkResult(grouping.get(0), grouping.get(1),grouping.get(2),compare);
            demo.interpretationResult();

         }
         System.out.println("---------------");
   }

}

}

```
程序结果如下

```
第1次测量,左为:右为结果为1
第2次测量,左为:右为结果为1
第3次测量,左为:右为结果为0
第0硬币质量重
---------------
第1次测量,左为:右为结果为-1
第2次测量,左为:右为结果为1
第3次测量,左为:右为结果为0
第1硬币质量重
---------------
第1次测量,左为:右为结果为0
第2次测量,左为:右为结果为1
第3次测量,左为:右为结果为1
第2硬币质量重
---------------
第1次测量,左为:右为结果为1
第2次测量,左为:右为结果为1
第3次测量,左为:右为结果为1
第3硬币质量重
---------------
第1次测量,左为:右为结果为-1
第2次测量,左为:右为结果为1
第3次测量,左为:右为结果为1
第4硬币质量重
---------------
第1次测量,左为:右为结果为0
第2次测量,左为:右为结果为-1
第3次测量,左为:右为结果为0
第5硬币质量重
---------------
第1次测量,左为:右为结果为1
第2次测量,左为:右为结果为-1
第3次测量,左为:右为结果为1
第6硬币质量重
---------------
第1次测量,左为:右为结果为-1
第2次测量,左为:右为结果为-1
第3次测量,左为:右为结果为1
第7硬币质量重
---------------
第1次测量,左为:右为结果为0
第2次测量,左为:右为结果为0
第3次测量,左为:右为结果为1
第8硬币质量重
---------------
第1次测量,左为:右为结果为1
第2次测量,左为:右为结果为-1
第3次测量,左为:右为结果为-1
第9硬币质量重
---------------
第1次测量,左为:右为结果为-1
第2次测量,左为:右为结果为-1
第3次测量,左为:右为结果为-1
第10硬币质量重
---------------
第1次测量,左为:右为结果为0
第2次测量,左为:右为结果为1
第3次测量,左为:右为结果为-1
第11硬币质量重
---------------

```

其中在计算这么摆放硬币最优grouping()方法,感觉很难写,而且当硬币达到39时,目前程序会出错
大家有什么更好的写发没,还有遇到这种逻辑题怎么用代码解决

注: 参考了b站up主Solara570的视频论坛littlefall作者的博客

hs248613 发表于 2022-8-13 08:24

数学不好，读了三分钟的题目和解析才看懂楼主意思，给和我一样数学不好的人啰嗦说明下：
1、假币可能比真币重，或比真币轻，2种可能，合起来就是楼主说的12*2=24可能
2、我们遍历24种可能就一定知道答案
3、称一次有有3种可能,左轻,平衡,右轻，称3次就是3^3=27种可能，27种可能涵盖了24种可能，再少就是称两次，3^2=9种可能比24小。再多就是称4次，3^4=81种可能比24大，但太多。
4、我们求最少称多少次，3次最佳，所以理论上3次可行

iawyxkdn8 发表于 2022-8-13 08:55

4次就能找到这个假币！

hs248613 发表于 2022-8-13 09:33

看看B站这位UP做的视频，把问题数学化了
https://www.bilibili.com/video/BV1Fy4y1T7mL?spm_id_from=333.999.0.0&vd_source=61a104c80d3fb90797dd9c7a15f4ba59

jgdfc 发表于 2022-8-13 12:09

hs248613 发表于 2022-8-13 09:33
看看B站这位UP做的视频，把问题数学化了
https://www.bilibili.com/video/BV1Fy4y1T7mL?spm_id_from=333.9 ...

看过了,但我想用程序来描述这个过程

CXC303 发表于 2022-8-13 13:22

感谢分享

页: [1]

吾爱破解 - 52pojie.cn's Archiver

【逻辑题】经典的“12枚硬币称量问题”