Public Static Int Huntingtonhill Int Population Int Seats That Given The Population In Each State And The Number 1 (248.46 KiB) Viewed 47 times
public static int[] huntingtonHill(int[] population, int seats)that, given the population in each state and the number of seats todistribute across these states, creates and returns a new arraythat contains the counts of seats given to each state. To makeresults unambiguous for the JUnit fuzz test, whenever two statescurrently have the same priority quantity, the next seat is givento the state that is earlier in the population array. To write thismethod, first add the class Fraction from the class examplesproject into your labs project, to let you perform yourcalculations with exact integer fractions without any possibilityof integer overflow or floating point rounding error. Not even onefloating point number, let alone any calculation involving them,should appear inside your method! You should also note that eventhough the population of some state fits comfortably inside an intwithout any overflow, the square of that population will not beequally friendly once this population is in the millions, whichsurely is not an unrealistic case for electoral math! For thisreason, these population squaring operations absolutely have to beperformed using exact Fraction objects of unlimited range, not asprimitive int values. Just like it is too late to close the barndoor after the horse has escaped, it is too late to convert an intvalue into an unlimited BigInteger once the overflow has alreadytaken place! For example, instead of trying to be concise, normallya virtue in this place, by writing a statement num =BigInteger.valueOf(population * population); where the intmultiplication can overflow before conversion to BigInteger, splitthis into num = BigInteger.valueOf(population); num =num.multiply(population); to force the integer multiplicationtake place inside the BigInteger mechanism where there is enoughroom for all digits. On that note, everybody stand up in attention,eyes front to receive the following extremely importantinstruction! Just because an integer value fits into an int, itssquare might not do so. Just because the intermediate results ofyour computational formulas are not given explicit symbolic namesin your code, it doesn't mean that those intermediate resultssomehow magically wouldn't exist, nor be subject to the exact samelaws of computations as your named data items! Page 27 of 278 Wouldyour instructor really be so mean as to design the methodtestHuntingtonHill to fuzz populations that are too big to beaccurately handled with floating point operations? Would that sameinstructor also ensure that some states end up having almost equalpopulations that differ by a measly little one or two people? Comeon; at this stage of the studies, and especially if you havealready taken my earlier course CCPS 109, do you really even haveto ask? The best way to track of the relative priorities of thestates (each state identified as an integer as its position inpopulation table) is to keep them inside a PriorityQueue instancewith a custom Comparator object whose compareTo(Integer a, Integerb) method renders its verdict based on the current priorities ofthe states a and b. These priorities, of course, are kept up todate inside another array Fraction[] priorities that is defined asa local variable inside this huntingtonHill method, outside thenested comparator class. To find out which state gets the nextseat, simply poll the queue for the state whose priority iscurrently the highest. Update the priority for that state to thepriorities array, and offer the state back into the priority queue.As historically important as this algorithm has been to the fate ofthe free world and our ability to keep rocking in it, it also has amore mundane application in displaying rounded percentages based ona list of numbers from some real-world data. You know how yousometimes see a disclaimer phrased something like “Due to rounding,displayed percentages may not add up to exactly one hundred” undersome table of numbers and their associated rounds percentages?Well, dude, just use the correct algorithm to display your roundedpercentages, and the need for such disclaimers utterly vanishes!For example, to compute the percentages rounded to one decimalplace, simply distribute 1,000 virtual “seats” among your dataitems. Each of these virtual seats corresponds to one per mille,one tenth of a percentage point (yep, those are an actual thing, asevery Finn with a driver's license would surely know), to bedisplayed as the exact percentage share of that data item.
public static int[] huntingtonHill (int[] population, int seats) that, given the population in each state and the number of seats to distribute across these states, creates and returns a new array that contains the counts of seats given to each state. To make results unambiguous for the JUnit fuzz test, whenever two states currently have the same priority quantity, the next seat is given to the state that is earlier in the population array. To write this method, first add the class Fraction from the class examples project into your labs project, to let you perform your calculations with exact integer fractions without any possibility of integer overflow or floating point rounding error. Not even one floating point number, let alone any calculation involving them, should appear inside your method! You should also note that even though the population of some state fits comfortably inside an int without any overflow, the square of that population will not be equally friendly once this population is in the millions, which surely is not an unrealistic case for electoral math! For this reason, these population squaring operations absolutely have to be performed using exact Fraction objects of unlimited range, not as primitive int values. Just like it is too late to close the barn door after the horse has escaped, it is too late to convert an int value into an unlimited BigInteger once the overflow has already taken place! For example, instead of trying to be concise, normally a virtue in this place, by writing a statement num= BigInteger.valueOf (population * population); where the int multiplication can overflow before conversion to BigInteger, split this into num = BigInteger.valueOf (population); num = num.multiply (population); to force the integer multiplication take place inside the BigInteger mechanism where there is enough room for all digits. On that note, everybody stand up in attention, eyes front to receive the following extremely important instruction! Just because an integer value fits into an int, its square might not do so. Just because the intermediate results of your computational formulas are not given explicit symbolic names in your code, it doesn't mean that those intermediate results somehow magically wouldn't exist, nor be subject to the exact same laws of computations as your named data items!
Would your instructor really be so mean as to design the method testHuntingtonHill to fuzz populations that are too big to be accurately handled with floating point operations? Would that same instructor also ensure that some states end up having almost equal populations that differ by a measly little one or two people? Come on; at this stage of the studies, and especially if you have already taken my earlier course CCPS 109, do you really even have to ask? The best way to track of the relative priorities of the states (each state identified as an integer as its position in population table) is to keep them inside a PriorityQueue<Integer> instance with a custom Comparator<Integer> object whose compareTo (Integer a, Integer b) method renders its verdict based on the current priorities of the states a and b. These priorities, of course, are kept up to date inside another array Fraction[] priorities that is defined as a local variable inside this huntingtonHill method, outside the nested comparator class. To find out which state gets the next seat, simply poll the queue for the state whose priority is currently the highest. Update the priority for that state to the priorities array, and offer the state back into the priority queue. As historically important as this algorithm has been to the fate of the free world and our ability to keep rocking in it, it also has a more mundane application in displaying rounded percentages based on a list of numbers from some real-world data. You know how you sometimes see a disclaimer phrased something like "Due to rounding, displayed percentages may not add up to exactly one hundred" under some table of numbers and their associated rounds percentages? Well, dude, just use the correct algorithm to display your rounded percentages, and the need for such disclaimers utterly vanishes! For example, to compute the percentages rounded to one decimal place, simply distribute 1,000 virtual "seats" among your data items. Each of these virtual seats corresponds to one per mille, one tenth of a percentage point (yep, those are an actual thing, as every Finn with a driver's license would surely know), to be displayed as the exact percentage share of that data item.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!