服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|JavaScript|易语言|

服务器之家 - 编程语言 - JAVA教程 - java编程实现求解八枚银币代码分享

java编程实现求解八枚银币代码分享

2021-02-25 22:46ljtyzhr JAVA教程

这篇文章主要介绍了java编程实现求解八枚银币代码分享,具有一定参考价值,需要的朋友可以了解下。

1、引言

笔者在大学的算法竞赛中,遇到过这样的一个题目,现在拿出来与大家分享一下:现在有现有八枚银币abcdefgh,已知其中一枚是假币,其重量不同于真币,但不知是较轻或较重,如何使用天平以最少的比较次数,决定出哪枚是假币,并得知假币比真币较轻或较重。

2、分析

如果本题目只是很单纯的求解假币是哪一个,问题倒并不是很复杂,只需要回溯递归便可求得结果。问题的难点在意,我们需要用最少的步骤!!!

比之以前的数据结构问题,有递归,回溯,我们今天可能要接触一个新的概念,叫做树。顾名思义,数结构就是说我们的分析图示像树一样,有分支节点等各种信息。树结构是数据结构中的一个较大的章节,不在我们的讨论之中,在本题目当中,我们会介绍树的一个小小的分子,决策树。

我们先建立一下,八个银币求解的数学模型。一个简单的状况是这样的,我们将银币依次命名为abcdefg等,我们比较a+b+c与d+e+f,如果相等,则假币必是g或h,我们先比较g或h哪个较重,如果g较重,再与a比较(a是真币),如果g等于a,则g为真币,则h为假币,由于h比g轻而g是真币,则h假币的重量比真币轻。

如果不相等呢?又是何种情况,我们将依次分支回溯比较,直到得到最终的答案!

3、示例图

根据上面的分析,我们可以有一个完整的决策树图示:

java编程实现求解八枚银币代码分享

4、代码

java" id="highlighter_303679">
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class coins {
  private int[] coins;
   
  public coins() {
    coins = new int[8];
    for(int i = 0; i < 8; i++) 
      coins[i] = 10
  }
   
  public void setfake(int weight) {
    coins[(int) (math.random() * 7)] = weight;
  }
   
  public void fake() {
    if(coins[0]+coins[1]+coins[2] == 
      coins[3]+coins[4]+coins[5]) { 
      if(coins[6] > coins[7]) 
        compare(6, 7, 0); 
      else
        compare(7, 6, 0); 
    
    else if(coins[0]+coins[1]+coins[2] > 
        coins[3]+coins[4]+coins[5]) { 
      if(coins[0]+coins[3] == coins[1]+coins[4]) 
        compare(2, 5, 0); 
      else if(coins[0]+coins[3] > coins[1]+coins[4]) 
        compare(0, 4, 1); 
      if(coins[0]+coins[3] < coins[1]+coins[4]) 
        compare(1, 3, 0); 
    
    else if(coins[0]+coins[1]+coins[2] < 
        coins[3]+coins[4]+coins[5]) { 
      if(coins[0]+coins[3] == coins[1]+coins[4]) 
        compare(5, 2, 0); 
      else if(coins[0]+coins[3] > coins[1]+coins[4]) 
        compare(3, 1, 0); 
      if(coins[0]+coins[3] < coins[1]+coins[4]) 
        compare(4, 0, 1); 
    
  }
   
  protected void compare(int i, int j, int k) {
    if(coins[i] > coins[k]) 
      system.out.print("\n假币 " + (i+1) + " 较重"); 
    else
      system.out.print("\n假币 " + (j+1) + " 较轻"); 
  }
   
  public static void main(string[] args) {
    if(args.length == 0) {
      system.out.println("输入假币重量(比10大或小)");
      system.out.println("ex. java coins 5");
      return;
    }
     
    coins eightcoins = new coins();
    eightcoins.setfake(integer.parseint(args[0]));
    eightcoins.fake();
  }
}

结果:

输入假币重量(比10大或小)
ex. java coins 5

这里是一段通用的解题方法,大家可以仔细琢磨代码,对于本段代码,上面的分析已经足够,剩下的就要大家自己琢磨学习了,这样才能深刻理解。

总结

以上就是本文关于java编程实现求解八枚银币代码分享的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

原文链接:http://blog.csdn.net/ljtyzhr/article/details/39274059

延伸 · 阅读

精彩推荐