- 浏览: 75956 次
文章分类
最新评论
-
wodentt:
....为什么楼主都英文的博客
用java解决百度之星移动火柴的问题 part 1 -
wensonzhou86:
思路明确,代码清晰,通俗易懂
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
carydeepbreathing:
代码比较干净
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
meiowei:
yangguo 写道i don't think it is a ...
用java解决百度之星移动火柴的问题 part 2 -
yangguo:
i don't think it is a good way ...
用java解决百度之星移动火柴的问题 part 2
Now it comes to the Scale class. The main job of it is to weight both sides. So the class is pretty simple, sum the weights of balls and compare.
Now based on these classes, the translation of the algorithm is straight forward:
Though this is a direct translation of the algorithm described in the book. There are 3 trivial cases served as the basis for the recursion. Taking into account that they are the base cases, they are not as trivial as one thinks.
Now based on these classes, the translation of the algorithm is straight forward:
java 代码
- package solve;
- import scale.Ball;
- import scale.Scale;
- import java.util.Set;
- import java.util.Iterator;
- import java.util.HashSet;
- public class ProblemSolver
- {
- private Set orignalballSet;
- private Scale scale = new Scale();
- public ProblemSolver(Set orignalballSet)
- {
- this.orignalballSet = orignalballSet;
- }
- public void findWeight()
- {
- findBadBall(this.orignalballSet);
- }
- private void findBadBall(Set ballSet)
- {
- int ballSetSize = ballSet.size();
- // recursion defaults
- if (ballSetSize == 1)
- {
- OneBallCaseSolver solver = new OneBallCaseSolver();
- solver.setScale(scale);
- solver.setOriginalBallSet(orignalballSet);
- solver.findWeight(ballSet);
- return;
- }
- else if (ballSetSize == 2)
- {
- TwoBallCaseSolver solver = new TwoBallCaseSolver();
- solver.setScale(scale);
- solver.setOriginalBallSet(orignalballSet);
- solver.findWeight(ballSet);
- return;
- }
- else if (ballSetSize == 3)
- {
- ThreeBallCaseSolver solver = new ThreeBallCaseSolver();
- solver.setScale(scale);
- solver.findWeight(ballSet);
- return;
- }
- // recursion starts here.
- // check whether all elements are marked. If so, then by the lemma,
- // It takes at most n times of weighing to point out the defect one
- // with the weigh, if N < 3^n, where N is the number of balls.
- // In order to check all balls, it's sufficient to check just one
- // because we either mark all or none.
- // With the marks, we definitely weigh less times.
- Ball firstBall = (Ball)ballSet.iterator().next();
- if (!firstBall.getStatus().equals(Ball.UNKNOWN))
- {
- findWithMarks(ballSet);
- return;
- }
- // if we get here, this means no mark is found, so we blindly populate
- // An extra good ball would reduce the size of the group, said in this lemma:
- // If an extra genuine good is available, when the defect ball can be found with
- // the weigh in N ball by n trials, where N <= (3^n - 1)/2.
- // In fact, using these two lemmas we can prove, by deduction, the entire problem:
- // Given N balls, if N <= (3^n - 3)/2, then we can findBadBall it with weigh in n trials.
- // This call is confusing: even the above if block is not marked, the whole set could have a good ball
- // one case is when we have a even scale, and this is the third group.
- Ball goodBall = Utils.findGoodBall(this.orignalballSet);
- int subsize = ballSetSize / 3; // divided into 3 groups
- if (goodBall != null)
- {
- subsize++; // for the good ball we are adding in.
- }
- else if (ballSetSize % 3 == 2)
- {
- subsize++; // use the groups with equal sizes.
- }
- HashSet group1 = new HashSet(subsize);
- HashSet group2 = new HashSet(subsize);
- HashSet group3 = new HashSet(ballSetSize - 2*subsize);
- if (goodBall != null) group1.add(goodBall);
- Iterator it = ballSet.iterator();
- // fill in group1 first.
- while (it.hasNext())
- {
- if (group1.size() < subsize) group1.add(it.next());
- if (group1.size() >= subsize) break;
- }
- // fill in group2 first.
- while (it.hasNext())
- {
- if (group2.size() < subsize) group2.add(it.next());
- if (group2.size() >= subsize) break;
- }
- // put the rest into group3
- while (it.hasNext())
- {
- group3.add(it.next());
- }
- int scaleResult = scale.weigh(group1, group2);
- if (scaleResult == Scale.EVEN)
- {
- Utils.markStatus(group1, Ball.NORMAL);
- Utils.markStatus(group2, Ball.NORMAL);
- findBadBall(group3);
- }
- else // the counterfeit is not in group3, it's in group1 or group2
- {
- Utils.markStatus(group3, Ball.NORMAL);
- Utils.markStatus(group1, Utils.convertToBallStatus(scaleResult));
- Ball goodput = Utils.findGoodBall(group1);
- if (goodput != null)
- {
- group1.remove(goodput);
- }
- Utils.markStatus(group2, Utils.convertToBallStatus(-scaleResult));
- goodput = Utils.findGoodBall(group2);
- if (goodput != null)
- {
- group2.remove(goodput);
- }
- Set newSet = new HashSet(group1.size() + group2.size());
- Iterator itt = group1.iterator();
- while (itt.hasNext()) newSet.add(itt.next());
- itt = group2.iterator();
- while (itt.hasNext()) newSet.add(itt.next());
- findWithMarks(newSet);
- }
- }
- //=======================================================================
- // Some big ugly codes go to here
- //=======================================================================
- private void findWithMarks(Set src)
- {
- int size = src.size();
- int subsize = size / 3; // divided into 3 groups
- if (size % 3 == 2) subsize++; // use the groups with equal sizes.
- HashSet group1 = new HashSet(subsize);
- HashSet group2 = new HashSet(subsize);
- HashSet group3 = new HashSet(size - 2*subsize); // this is the off scale group
- // now we need to populate in such a way so that group1 and group2
- // have equal number of same weigh, both for 1 and -1. The reason
- // we need this is because in some cases, we need to switch them in
- // forming nextGroup.
- evenlyDistribute(src, group1, group2, group3, subsize);
- if (group1.size() > 0)
- {
- int result = scale.weigh(group1, group2);
- if (result == Scale.EVEN)
- {
- // mark group1 and group2
- Utils.markStatus(group1, Ball.NORMAL);
- Utils.markStatus(group2, Ball.NORMAL);
- findBadBall(group3);
- }
- // get lighter balls from lighter groups, get heavier balls from heavier groups
- else if (result == Scale.HEAVIER)
- {
- Utils.markStatus(group3, Ball.NORMAL);
- HashSet nextGroup = new HashSet();
- getHeavier(group1, nextGroup);
- getLighter(group2, nextGroup);
- findBadBall(nextGroup);
- }
- else // -1
- {
- Utils.markStatus(group3, Ball.NORMAL);
- HashSet nextGroup = new HashSet();
- getHeavier(group2, nextGroup);
- getLighter(group1, nextGroup);
- findBadBall(nextGroup);
- }
- }
- else
- {
- findBadBall(group3);
- }
- }
- private void getHeavier(Set src, Set des)
- {
- for (Iterator it=src.iterator(); it.hasNext();)
- {
- Ball ball = (Ball)it.next();
- if (ball.getStatus().equals(Ball.HEAVIER)) des.add(ball);
- else ball.setStatus(Ball.NORMAL);
- }
- }
- private void getLighter(Set src, Set des)
- {
- for (Iterator it=src.iterator(); it.hasNext();)
- {
- Ball ball = (Ball)it.next();
- if (ball.getStatus().equals(Ball.LIGHTER)) des.add(ball);
- else ball.setStatus(Ball.NORMAL);
- }
- }
- // This will distribute src to des1, des2, and des3. Assuming src is marked
- // with proper weigh 1, -1. des1 and des2 should have the same number of
- // balls with weigh 1, and should have the same number of balls of weigh
- // -1. The rest of src goes to des3, which should be the off scale group.
- // size is the size of des1, des2.
- private void evenlyDistribute(Set src, Set des1, Set des2, Set des3, int size)
- {
- int heavierSum1 = 0;
- int lighterSum1 = 0;
- int heavierSum2 = 0;
- int lighterSum2 = 0;
- Ball heavierPair = null;
- int heavierPairMarker = 0; // 0 for no pair, 1 for pair
- Ball lighterPair = null;
- int lighterPairMarker = 0; // 0 for no pair, 1 for pair
- Iterator itm1 = src.iterator();
- while (itm1.hasNext())
- {
- Ball ball = (Ball)itm1.next();
- if (des1.size() >= size)
- {
- des3.add(ball);
- }
- else if (ball.getStatus().equals(Ball.HEAVIER))
- {
- if (heavierSum1 > heavierSum2)
- {
- des2.add(ball);
- heavierSum2++;
- }
- else if (heavierSum1 < heavierSum2)
- {
- des1.add(ball);
- heavierSum1++;
- }
- else // heavierSum1==heavierSum2
- {
- if (heavierPairMarker == 0) // this is the first one
- {
- // save this, set marker, wait for the next one.
- heavierPair = ball;
- heavierPairMarker = 1;
- }
- else // ==1, already a ball there, now set one for each group
- {
- des1.add(heavierPair);
- des2.add(ball);
- // reset marker to 0
- heavierPair = null;
- heavierPairMarker = 0;
- }
- }
- }
- else if (ball.getStatus().equals(Ball.LIGHTER))
- {
- if (lighterSum1 > lighterSum2)
- {
- des2.add(ball);
- lighterSum2++;
- }
- else if (lighterSum1 < lighterSum2)
- {
- des1.add(ball);
- lighterSum1++;
- }
- else // lighterSum1==lighterSum2
- {
- if (lighterPairMarker == 0) // this is the first one
- {
- // save this, set marker, wait for the next one.
- lighterPair = ball;
- lighterPairMarker = 1;
- }
- else // ==1, already a ball there, now set one for each group
- {
- des1.add(lighterPair);
- des2.add(ball);
- // reset marker to 0
- lighterPair = null;
- lighterPairMarker = 0;
- }
- }
- }
- else
- {
- System.out.println("This ball is not marked: " + ball + " !!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
- }
- }
- // At the very last, if there are any left, add them to des3 since des1 and des2 are full, by now.
- if (lighterPair != null) des3.add(lighterPair);
- if (heavierPair != null) des3.add(heavierPair);
- }
- public Scale getScale() { return this.scale; }
- }
Though this is a direct translation of the algorithm described in the book. There are 3 trivial cases served as the basis for the recursion. Taking into account that they are the base cases, they are not as trivial as one thinks.
发表评论
-
Revisit 一道应聘智力题的编程求解, Einstein puzzle
2010-03-09 00:36 1366Another brain teaser, titled 一道 ... -
Another Google question - drop glassballs from a building 5
2007-05-13 04:01 1030Here are some results are the t ... -
Another Google question - drop glassballs from a building 4
2007-05-13 03:42 1480The test cases are divided into ... -
Another Google question - drop glassballs from a building 3
2007-05-13 03:33 1039The next step is to find the ac ... -
Another Google question - drop glassballs from a building 2
2007-05-13 03:02 1055Here is the code following the ... -
Another Google question - drop glassballs from a building 1
2007-05-12 04:43 1159Here is the question: 原题: ... -
Given n coins and a pan balance,find the only counterfeit 4
2007-02-27 05:54 1087The Utils class is composed of ... -
Given n coins and a pan balance,find the only counterfeit 3
2007-02-27 05:50 1441In the 1-ball case, if the stat ... -
Given n coins and a pan balance, find the only counterfeit 1
2007-02-27 04:49 1295The problem is: There is one ... -
A Google's Interview Question - GLAT #20 series 4
2007-02-08 02:36 1041The entire class is as follows: ... -
A Google's Interview Question - GLAT #20 series 3
2007-02-08 02:36 1038The roadmap to compute all fixe ... -
A Google's Interview Question - GLAT #20 series 2
2007-02-08 02:24 1010Now, we can deduct the recursio ... -
A Google's Interview Question - GLAT #20 series 1
2007-02-08 02:22 1106Question: Consider a function ...
相关推荐
• Handle the counterfeit coin problem: a classic puzzle that consists of finding a counterfeit coin in a beam balance among eight coins in only two turns Who This Book Is For Developers and ...
Also at the bottom dropped a few coins. Years pass, but ... The Lost Watch II 3D Screensaver v1.0 build 3 Golden hours at the bottom of the river sparkling in the sun. Nobody does not initiate ...
The last game will have you running and jumping across platforms to collect coins and other exotic items. Throughout all these three games, you will create characters, make them move, and create some...
-Count coins & dollar bills in an image after creating a currency counter -Find Legend of Zelda rupees using a pattern matching algorithm -Design a face swapping app -Discuss the mathematical theory &...
poj 3260 The Fewest Coins.md
You also pick up some gold coins and gain experience points. Now you dream of finding a better bow... Off to the right, you spot a whole group of undead monsters that are surely guarding loot you ...
设有n 种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。 对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个...
Ethereum coins to buy and reward the prize for convenience in term of speed and also reduce the problems which is unable to be controlled by the government. For example, lottery agents (intermediaries...
coins needed to make change for a given amount, we can repeatedly select the largest-denomination coin that is not larger than the amount that remains. A greedy approach provides an optimal solution ...
coins-security-1.0jar包
Many real-world problems are optimization ... For example, the purchase is worth $5.27, how many coins and what coins does a cash register return after paying a $6 bill? The Make-Change algorithm:
2. Enhancing the safety of the Libra payment system with a robust compliance framework. 3. Forgoing the future transition to a permissionless system while maintaining its key economic properties. 4. ...
which gives you coins in four types of cryptocurrency, such as: Ethereum, Litecoin, Dash, Dogecoin, which directly and without decoding the received hex with a series of tricks. Advanced has managed ...
2019 Standard Catalog of World Coins, 2001-Date, 13th edition
get-the-coins
ESXI虚拟化网络配置.doc
magic_coins2.py A while-loop with multiple conditions. while_loop_multiple_conditions.py Looping through the wizard list. wizard_list_loop.py Chapter 7 A function to calculate your savings. savings....
I = imread( C:\MATLAB701\toolbox\images\imdemos\coins.png ) imshow(I) figure, imhist(I,64)
动态规划题解coins.cpp