好友
阅读权限10
听众
最后登录1970-1-1
|
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
这种方法如何转换成程序呢?
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;
//[0]集合
List<Integer> kn1 = new ArrayList<>();
//[-1,0]集合
List<Integer> kn2Minus = new ArrayList<>();
//[1,0]集合
List<Integer> kn2Positive = new ArrayList<>();
//[-1,0,1]集合
List<Integer> kn3 = new ArrayList<>();
/**
* 设置第number个硬币的质量偏差为deviation
* number从0起,范围[0-11], 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 右轻
* home.php?mod=space&uid=952169 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次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为1
第2次测量,左为:[10, 0, 3]右为[6, 9, 2]结果为1
第3次测量,左为:[3]右为[1]结果为0
第0硬币质量重
---------------
第1次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为-1
第2次测量,左为:[9, 1, 4]右为[7, 10, 2]结果为1
第3次测量,左为:[4]右为[0]结果为0
第1硬币质量重
---------------
第1次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为0
第2次测量,左为:[2, 11, 3, 7]右为[5, 0, 4, 9]结果为1
第3次测量,左为:[2]右为[11]结果为1
第2硬币质量重
---------------
第1次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为1
第2次测量,左为:[10, 0, 3]右为[6, 9, 2]结果为1
第3次测量,左为:[3]右为[1]结果为1
第3硬币质量重
---------------
第1次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为-1
第2次测量,左为:[9, 1, 4]右为[7, 10, 2]结果为1
第3次测量,左为:[4]右为[0]结果为1
第4硬币质量重
---------------
第1次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为0
第2次测量,左为:[2, 11, 3, 7]右为[5, 0, 4, 9]结果为-1
第3次测量,左为:[2]右为[11]结果为0
第5硬币质量重
---------------
第1次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为1
第2次测量,左为:[10, 0, 3]右为[6, 9, 2]结果为-1
第3次测量,左为:[6]右为[9]结果为1
第6硬币质量重
---------------
第1次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为-1
第2次测量,左为:[9, 1, 4]右为[7, 10, 2]结果为-1
第3次测量,左为:[7]右为[10]结果为1
第7硬币质量重
---------------
第1次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为0
第2次测量,左为:[2, 11, 3, 7]右为[5, 0, 4, 9]结果为0
第3次测量,左为:[8, 2, 5, 9]右为[0, 3, 6, 10]结果为1
第8硬币质量重
---------------
第1次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为1
第2次测量,左为:[10, 0, 3]右为[6, 9, 2]结果为-1
第3次测量,左为:[6]右为[9]结果为-1
第9硬币质量重
---------------
第1次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为-1
第2次测量,左为:[9, 1, 4]右为[7, 10, 2]结果为-1
第3次测量,左为:[7]右为[10]结果为-1
第10硬币质量重
---------------
第1次测量,左为:[0, 3, 6, 9]右为[1, 4, 7, 10]结果为0
第2次测量,左为:[2, 11, 3, 7]右为[5, 0, 4, 9]结果为1
第3次测量,左为:[2]右为[11]结果为-1
第11硬币质量重
---------------
其中在计算这么摆放硬币最优grouping()方法,感觉很难写,而且当硬币达到39时,目前程序会出错
大家有什么更好的写发没,还有遇到这种逻辑题怎么用代码解决
注: 参考了b站up主Solara570的视频 论坛littlefall作者的博客 |
免费评分
-
查看全部评分
|
|
发表于 2022-8-13 12:09
