(после некоторых обширных правок:)
Если у вас есть только 2 избирателя, вы можете сгенерировать только следующие проценты для кандидатов А и В:
0+100, 100+0, or 50+50
Если у вас есть 3 избирателя, то у вас есть
0+100, 100+0, 33.33+66.67, 66.67+33.33 [notice the rounding]
Так что это забавная задача о дробях.
Если вы можете сделать 25%, то вам нужно иметь как минимум 4 человека (так что вы можете сделать 1/4, так как 1/2 и 1/3 не будут сокращать его). Вы можете сделать это больше (то есть 2/8 = 25%), но проблема требует наименьшего.
Однако для более интересных дробей требуются числа больше 1 в числителе:
2/5 = 40%
Так как вы не можете получить это ни с чем, кроме 2 или более в числителе (1 / x никогда не обрежет это).
Вы можете сравнивать на каждом шаге и увеличивать числитель или знаменатель, что намного эффективнее, чем итерация по всему пространству выборки для j, а затем увеличение i;
т.е. если у вас есть процент в 3%, проверка решений до 96/99, 97/99, 98/99, прежде чем даже перейти к х / 100, - пустая трата времени. Вместо этого вы можете увеличить числитель или знаменатель в зависимости от того, насколько хорошо работает ваше текущее предположение (больше или меньше), например
int max = 5000; //we only need to go half-way at most.
public int minVoters (double onePercentage) {
double checkPercentage = onePercentage;
if (onePercentage > 50.0)
checkPercentage = 100-onePercentage; //get the smaller percentage value
double i=1;
double j=1; //arguments of Math.round must be double or float
double temp = 0;
while (j<max || i<max-1) { //we can go all the way to 4999/5000 for the lesser value
temp = (i/j)*100;
temp = Math.round(temp);
temp = temp/100;
if (temp == checkPercentage)
return j;
else if (temp > checkPercentage) //we passed up our value and need to increase the denominator
j++;
else if (temp < checkPercentage) //we are too low and increase the numerator
i++;
}
return 0; //no such solution
}
Пошаговый пример поиска знаменателя, который может дать 55%
55/100 = 11/20
100-55 = 45 = 9/20 (checkPercentage will be 45.0)
1/1 100.0%
1/2 50.00%
1/3 33.33%
2/3 66.67%
2/4 50.00%
2/5 40.00%
3/5 60.00%
3/6 50.00%
3/7 42.86% (too low, increase numerator)
4/7 57.14% (too high, increase denominator)
4/8 50.00%
4/9 44.44%
5/9 55.56%
5/10 50.00%
5/11 45.45%
6/11 54.54%
6/12 50.00%
6/13 46.15%
6/14 42.86%
7/14 50.00%
7/15 46.67%
7/16 43.75%
8/16 50.00%
8/17 47.06%
8/19 42.11%
9/19 47.37%
9/20 45.00% <-bingo
Приятной особенностью этого метода является то, что он будет выполнять только (i + j) шагов, где i - числитель, а j - знаменатель.