`

Given n coins and a pan balance,find the only counterfeit 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:

java 代码
 
  1. package solve;  
  2.   
  3. import scale.Ball;  
  4. import scale.Scale;  
  5.   
  6. import java.util.Set;  
  7. import java.util.Iterator;  
  8. import java.util.HashSet;  
  9.   
  10. public class ProblemSolver  
  11. {  
  12.     private Set orignalballSet;  
  13.   
  14.     private Scale scale = new Scale();  
  15.   
  16.     public ProblemSolver(Set orignalballSet)  
  17.     {  
  18.         this.orignalballSet = orignalballSet;  
  19.     }  
  20.   
  21.     public void findWeight()  
  22.     {  
  23.         findBadBall(this.orignalballSet);  
  24.     }  
  25.   
  26.     private void findBadBall(Set ballSet)  
  27.     {  
  28.         int ballSetSize = ballSet.size();  
  29.   
  30.         // recursion defaults  
  31.         if (ballSetSize == 1)  
  32.         {  
  33.             OneBallCaseSolver solver = new OneBallCaseSolver();  
  34.             solver.setScale(scale);  
  35.             solver.setOriginalBallSet(orignalballSet);  
  36.             solver.findWeight(ballSet);  
  37.             return;  
  38.         }  
  39.         else if (ballSetSize == 2)  
  40.         {  
  41.             TwoBallCaseSolver solver = new TwoBallCaseSolver();  
  42.             solver.setScale(scale);  
  43.             solver.setOriginalBallSet(orignalballSet);  
  44.             solver.findWeight(ballSet);  
  45.             return;  
  46.         }  
  47.         else if (ballSetSize == 3)  
  48.         {  
  49.             ThreeBallCaseSolver solver = new ThreeBallCaseSolver();  
  50.             solver.setScale(scale);  
  51.             solver.findWeight(ballSet);  
  52.             return;  
  53.         }  
  54.   
  55.         // recursion starts here.  
  56.   
  57.         // check whether all elements are marked. If so, then by the lemma,  
  58.         //     It takes at most n times of weighing to point out the defect one  
  59.         //     with the weigh, if N < 3^n, where N is the number of balls.  
  60.         // In order to check all balls, it's sufficient to check just one  
  61.         // because we either mark all or none.  
  62.         // With the marks, we definitely weigh less times.  
  63.         Ball firstBall = (Ball)ballSet.iterator().next();  
  64.         if (!firstBall.getStatus().equals(Ball.UNKNOWN))  
  65.         {  
  66.             findWithMarks(ballSet);  
  67.             return;  
  68.         }  
  69.   
  70.         // if we get here, this means no mark is found, so we blindly populate  
  71.         // An extra good ball would reduce the size of the group, said in this lemma:  
  72.         //     If an extra genuine good is available, when the defect ball can be found with  
  73.         //     the weigh in N ball by n trials, where N <= (3^n - 1)/2.  
  74.         // In fact, using these two lemmas we can prove, by deduction, the entire problem:  
  75.         //     Given N balls, if N <= (3^n - 3)/2, then we can findBadBall it with weigh in n trials.  
  76.         // This call is confusing: even the above if block is not marked, the whole set could have a good ball  
  77.         // one case is when we have a even scale, and this is the third group.  
  78.         Ball goodBall = Utils.findGoodBall(this.orignalballSet);  
  79.   
  80.         int subsize = ballSetSize / 3// divided into 3 groups  
  81.         if (goodBall != null)  
  82.         {  
  83.             subsize++; // for the good ball we are adding in.  
  84.         }  
  85.         else if (ballSetSize % 3 == 2)  
  86.         {  
  87.             subsize++; // use the groups with equal sizes.  
  88.         }  
  89.   
  90.         HashSet group1 = new HashSet(subsize);  
  91.         HashSet group2 = new HashSet(subsize);  
  92.         HashSet group3 = new HashSet(ballSetSize - 2*subsize);  
  93.   
  94.         if (goodBall != null) group1.add(goodBall);  
  95.   
  96.         Iterator it = ballSet.iterator();  
  97.         // fill in group1 first.  
  98.         while (it.hasNext())  
  99.         {  
  100.             if (group1.size() < subsize) group1.add(it.next());  
  101.             if (group1.size() >= subsize) break;  
  102.         }  
  103.   
  104.         // fill in group2 first.  
  105.         while (it.hasNext())  
  106.         {  
  107.             if (group2.size() < subsize) group2.add(it.next());  
  108.             if (group2.size() >= subsize) break;  
  109.         }  
  110.   
  111.         // put the rest into group3  
  112.         while (it.hasNext())  
  113.         {  
  114.             group3.add(it.next());  
  115.         }  
  116.           
  117.         int scaleResult = scale.weigh(group1, group2);  
  118.         if (scaleResult == Scale.EVEN)  
  119.         {  
  120.             Utils.markStatus(group1, Ball.NORMAL);  
  121.             Utils.markStatus(group2, Ball.NORMAL);  
  122.   
  123.   
  124.             findBadBall(group3);  
  125.         }  
  126.         else // the counterfeit is not in group3, it's in group1 or group2  
  127.         {  
  128.             Utils.markStatus(group3, Ball.NORMAL);  
  129.   
  130.             Utils.markStatus(group1, Utils.convertToBallStatus(scaleResult));  
  131.             Ball goodput = Utils.findGoodBall(group1);  
  132.             if (goodput != null)  
  133.             {  
  134.                 group1.remove(goodput);  
  135.             }  
  136.   
  137.             Utils.markStatus(group2, Utils.convertToBallStatus(-scaleResult));  
  138.             goodput = Utils.findGoodBall(group2);  
  139.   
  140.             if (goodput != null)  
  141.             {  
  142.                 group2.remove(goodput);  
  143.             }  
  144.   
  145.             Set newSet = new HashSet(group1.size() + group2.size());  
  146.             Iterator itt = group1.iterator();  
  147.             while (itt.hasNext()) newSet.add(itt.next());  
  148.             itt = group2.iterator();  
  149.             while (itt.hasNext()) newSet.add(itt.next());  
  150.   
  151.             findWithMarks(newSet);  
  152.         }  
  153.     }  
  154.   
  155.     //=======================================================================  
  156.     // Some big ugly codes go to here  
  157.     //=======================================================================  
  158.     private void findWithMarks(Set src)  
  159.     {  
  160.         int size = src.size();  
  161.   
  162.         int subsize = size / 3// divided into 3 groups  
  163.         if (size % 3 == 2) subsize++; // use the groups with equal sizes.  
  164.   
  165.         HashSet group1 = new HashSet(subsize);  
  166.         HashSet group2 = new HashSet(subsize);  
  167.         HashSet group3 = new HashSet(size - 2*subsize); // this is the off scale group  
  168.   
  169.         // now we need to populate in such a way so that group1 and group2  
  170.         // have equal number of same weigh, both for 1 and -1. The reason  
  171.         // we need this is because in some cases, we need to switch them in  
  172.         // forming nextGroup.  
  173.         evenlyDistribute(src, group1, group2, group3, subsize);  
  174.   
  175.         if (group1.size() > 0)  
  176.         {  
  177.             int result = scale.weigh(group1, group2);  
  178.             if (result == Scale.EVEN)  
  179.             {  
  180.                 // mark group1 and group2  
  181.                 Utils.markStatus(group1, Ball.NORMAL);  
  182.                 Utils.markStatus(group2, Ball.NORMAL);  
  183.                 findBadBall(group3);  
  184.             }  
  185.             // get lighter balls from lighter groups, get heavier balls from heavier groups  
  186.             else if (result == Scale.HEAVIER)  
  187.             {  
  188.                 Utils.markStatus(group3, Ball.NORMAL);  
  189.   
  190.                 HashSet nextGroup = new HashSet();  
  191.                 getHeavier(group1, nextGroup);  
  192.                 getLighter(group2, nextGroup);  
  193.                 findBadBall(nextGroup);  
  194.             }  
  195.             else // -1  
  196.             {  
  197.                 Utils.markStatus(group3, Ball.NORMAL);  
  198.   
  199.                 HashSet nextGroup = new HashSet();  
  200.                 getHeavier(group2, nextGroup);  
  201.                 getLighter(group1, nextGroup);  
  202.                 findBadBall(nextGroup);  
  203.             }  
  204.         }  
  205.         else  
  206.         {  
  207.             findBadBall(group3);  
  208.         }  
  209.     }  
  210.   
  211.     private void getHeavier(Set src, Set des)  
  212.     {  
  213.         for (Iterator it=src.iterator(); it.hasNext();)  
  214.         {  
  215.             Ball ball = (Ball)it.next();  
  216.             if (ball.getStatus().equals(Ball.HEAVIER)) des.add(ball);  
  217.             else ball.setStatus(Ball.NORMAL);  
  218.         }  
  219.     }  
  220.   
  221.     private void getLighter(Set src, Set des)  
  222.     {  
  223.         for (Iterator it=src.iterator(); it.hasNext();)  
  224.         {  
  225.             Ball ball = (Ball)it.next();  
  226.             if (ball.getStatus().equals(Ball.LIGHTER)) des.add(ball);  
  227.             else ball.setStatus(Ball.NORMAL);  
  228.         }  
  229.     }  
  230.   
  231.     // This will distribute src to des1, des2, and des3. Assuming src is marked  
  232.     // with proper weigh 1, -1. des1 and des2 should have the same number of  
  233.     // balls with weigh 1, and should have the same number of balls of weigh  
  234.     // -1. The rest of src goes to des3, which should be the off scale group.  
  235.     // size is the size of des1, des2.  
  236.     private void evenlyDistribute(Set src, Set des1, Set des2, Set des3, int size)  
  237.     {  
  238.         int heavierSum1 = 0;  
  239.         int lighterSum1 = 0;  
  240.         int heavierSum2 = 0;  
  241.         int lighterSum2 = 0;  
  242.         Ball heavierPair = null;  
  243.         int heavierPairMarker = 0// 0 for no pair, 1 for pair  
  244.         Ball lighterPair = null;  
  245.         int lighterPairMarker = 0// 0 for no pair, 1 for pair  
  246.   
  247.         Iterator itm1 = src.iterator();  
  248.         while (itm1.hasNext())  
  249.         {  
  250.             Ball ball = (Ball)itm1.next();  
  251.             if (des1.size() >= size)  
  252.             {  
  253.                 des3.add(ball);  
  254.             }  
  255.             else if (ball.getStatus().equals(Ball.HEAVIER))  
  256.             {  
  257.                 if (heavierSum1 > heavierSum2)  
  258.                 {  
  259.                     des2.add(ball);  
  260.                     heavierSum2++;  
  261.                 }  
  262.                 else if (heavierSum1 < heavierSum2)  
  263.                 {  
  264.                     des1.add(ball);  
  265.                     heavierSum1++;  
  266.                 }  
  267.                 else // heavierSum1==heavierSum2  
  268.                 {  
  269.                     if (heavierPairMarker == 0// this is the first one  
  270.                     {  
  271.                         // save this, set marker, wait for the next one.  
  272.                         heavierPair = ball;  
  273.                         heavierPairMarker = 1;  
  274.                     }  
  275.                     else // ==1, already a ball there, now set one for each group  
  276.                     {  
  277.                         des1.add(heavierPair);  
  278.                         des2.add(ball);  
  279.                         // reset marker to 0  
  280.                         heavierPair = null;  
  281.                         heavierPairMarker = 0;  
  282.                     }  
  283.                 }  
  284.             }  
  285.             else if (ball.getStatus().equals(Ball.LIGHTER))  
  286.             {  
  287.                 if (lighterSum1 > lighterSum2)  
  288.                 {  
  289.                     des2.add(ball);  
  290.                     lighterSum2++;  
  291.                 }  
  292.                 else if (lighterSum1 < lighterSum2)  
  293.                 {  
  294.                     des1.add(ball);  
  295.                     lighterSum1++;  
  296.                 }  
  297.                 else // lighterSum1==lighterSum2  
  298.                 {  
  299.                     if (lighterPairMarker == 0// this is the first one  
  300.                     {  
  301.                         // save this, set marker, wait for the next one.  
  302.                         lighterPair = ball;  
  303.                         lighterPairMarker = 1;  
  304.                     }  
  305.                     else // ==1, already a ball there, now set one for each group  
  306.                     {  
  307.                         des1.add(lighterPair);  
  308.                         des2.add(ball);  
  309.                         // reset marker to 0  
  310.                         lighterPair = null;  
  311.                         lighterPairMarker = 0;  
  312.                     }  
  313.                 }  
  314.             }  
  315.             else  
  316.             {  
  317.                 System.out.println("This ball is not marked: " + ball + " !!!!!!!!!!!!!!!!!!!!!!!!!!!!!");  
  318.             }  
  319.         }  
  320.         // At the very last, if there are any left, add them to des3 since des1 and des2 are full, by now.  
  321.         if (lighterPair != null) des3.add(lighterPair);  
  322.         if (heavierPair != null) des3.add(heavierPair);  
  323.     }  
  324.   
  325.     public Scale getScale() { return this.scale; }  
  326. }  

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.
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics