📄 eightcoins.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>八枚银币</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 八枚银币</a></h1>
<h2> 说明</h2>
现有八枚银币a b c d e f g h，已知其中一枚是假币，其重量不同于真币，但不知是较轻或较重，如何使用天平以最少的比较次数，决定出哪枚是假币，并得知假币比真币较轻或较重。<br>
<h2>解法</h2>
单就求假币的问题是不难，但问题限制使用最少的比较次数，所以我们不能以单纯的回圈比较来求解，我们可以使用决策树（decision tree），使用分析与树状图来协助求解。<br>
<br>
一个简单的状况是这样的，我们比较a+b+c与d+e+f ，如果相等，则假币必是g或h，我们先比较g或h哪个较重，如果g较重，再与a比较（a是真币），如果g等于a，则g为真币，则h为假币，由于h比g轻而 g是真币，则h假币的重量比真币轻。<br>
<br>
完整的比较决策树如下图所示： <br>
<div style="text-align: center;"><img style="width: 634px; height: 171px;" alt="八枚银币" title="八枚银币" src="images/eightCoins-1.jpg"><br>
<br>
</div>
为了方便使用回圈，使用号码0至7表示银币，范例程式可以让您输入假币重量，但您无法事先得知假币是哪一枚，程式可得知假币是哪一枚，且它比真币轻或重。 <br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br>#include <time.h> <br> <br>void compare(int[], int, int, int); <br>void eightcoins(int[]); <br> <br>int main(void) { <br> int coins[8] = {0}; <br> int i; <br><br> srand(time(NULL)); <br><br> for(i = 0; i < 8; i++) <br> coins[i] = 10; <br><br> printf("\n输入假币重量(比10大或小)："); <br> scanf("%d", &i); <br> coins[rand() % 8] = i; <br><br> eightcoins(coins); <br><br> printf("\n\n列出所有钱币重量："); <br> for(i = 0; i < 8; i++) <br> printf("%d ", coins[i]); <br><br> printf("\n"); <br><br> return 0; <br>} <br><br>void compare(int coins[], int i, int j, int k) { <br> if(coins[i] > coins[k]) <br> printf("\n假币 %d 较重", i+1); <br> else <br> printf("\n假币 %d 较轻", j+1); <br>} <br><br>void eightcoins(int coins[]) { <br> if(coins[0]+coins[1]+coins[2] == <br> coins[3]+coins[4]+coins[5]) { <br> if(coins[6] > coins[7]) <br> compare(coins, 6, 7, 0); <br> else <br> compare(coins, 7, 6, 0); <br> } <br> else if(coins[0]+coins[1]+coins[2] > <br> coins[3]+coins[4]+coins[5]) { <br> if(coins[0]+coins[3] == coins[1]+coins[4]) <br> compare(coins, 2, 5, 0); <br> else if(coins[0]+coins[3] > coins[1]+coins[4]) <br> compare(coins, 0, 4, 1); <br> if(coins[0]+coins[3] < coins[1]+coins[4]) <br> compare(coins, 1, 3, 0); <br> } <br> else if(coins[0]+coins[1]+coins[2] <<br> coins[3]+coins[4]+coins[5]) { <br> if(coins[0]+coins[3] == coins[1]+coins[4]) <br> compare(coins, 5, 2, 0); <br> else if(coins[0]+coins[3] > coins[1]+coins[4]) <br> compare(coins, 3, 1, 0); <br> if(coins[0]+coins[3] < coins[1]+coins[4]) <br> compare(coins, 4, 0, 1); <br> } <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class Coins {<br> private int[] coins;<br> <br> public Coins() {<br> coins = new int[8];<br> for(int i = 0; i < 8; i++) <br> coins[i] = 10; <br> }<br> <br> public void setFake(int weight) {<br> coins[(int) (Math.random() * 7)] = weight;<br> }<br> <br> public void fake() {<br> if(coins[0]+coins[1]+coins[2] == <br> coins[3]+coins[4]+coins[5]) { <br> if(coins[6] > coins[7]) <br> compare(6, 7, 0); <br> else <br> compare(7, 6, 0); <br> } <br> else if(coins[0]+coins[1]+coins[2] > <br> coins[3]+coins[4]+coins[5]) { <br> if(coins[0]+coins[3] == coins[1]+coins[4]) <br> compare(2, 5, 0); <br> else if(coins[0]+coins[3] > coins[1]+coins[4]) <br> compare(0, 4, 1); <br> if(coins[0]+coins[3] < coins[1]+coins[4]) <br> compare(1, 3, 0); <br> } <br> else if(coins[0]+coins[1]+coins[2] < <br> coins[3]+coins[4]+coins[5]) { <br> if(coins[0]+coins[3] == coins[1]+coins[4]) <br> compare(5, 2, 0); <br> else if(coins[0]+coins[3] > coins[1]+coins[4]) <br> compare(3, 1, 0); <br> if(coins[0]+coins[3] < coins[1]+coins[4]) <br> compare(4, 0, 1); <br> } <br> }<br> <br> protected void compare(int i, int j, int k) {<br> if(coins[i] > coins[k]) <br> System.out.print("\n假币 " + (i+1) + " 较重"); <br> else <br> System.out.print("\n假币 " + (j+1) + " 较轻"); <br> }<br> <br> public static void main(String[] args) {<br> if(args.length == 0) {<br> System.out.println("输入假币重量（比10大或小）");<br> System.out.println("ex. java Coins 5");<br> return;<br> }<br> <br> Coins eightCoins = new Coins();<br> eightCoins.setFake(Integer.parseInt(args[0]));<br> eightCoins.fake();<br> }<br>}</pre>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -