Распределение номеров

Question

Проблема: у нас есть x флажков, и мы хотим равномерно их проверить y.

Пример 1: выбрать 50 флажков из 100 всего.

[-]
[x]
[-]
[x]
...

Пример 2: выбрать 33 флажкаиз 100 всего.

[-]
[-]
[x]
[-]
[-]
[x]
...

Пример 3: установите 66 флажков из 100 всего:

[-]
[x]
[x]
[-]
[x]
[x]
...

Но у нас возникают проблемы с формулой для проверки их в коде,особенно когда вы идете 11/111 или что-то подобное.У кого-нибудь есть идея?

Answer 1

Давайте сначала предположим, что y делится на x. Тогда мы обозначаем p = y/x и решение простое. Просмотрите список, все элементы p, отметьте 1 из них.

Теперь, скажем, r = y%x не ноль. Все еще p = y/x, где / - целочисленное деление. Итак, вам необходимо:

• В первых p-r элементах отметьте 1 элемент
• В последних r элементах отметьте 2 элемента

Примечание: Это зависит от того, как вы определяете равномерно распределенных . Возможно, вы захотите распределить секции r с элементами x+1 между секциями p-r с элементами x, что опять-таки является той же проблемой и может быть решено рекурсивно.

Хорошо, так что это не совсем правильно. Я думаю, что это будет делать, хотя:

Независимо от делимости:

• если y > 2*x, то отмечать 1 элемент каждые p = y/x элементов, x раз.
• если y < 2*x, то пометьте все и выполните предыдущий шаг, сняв отметки y-x из y (как и в предыдущем случае, но x заменяется на y-x)

Примечание: Это зависит от того, как вы определяете равномерно распределенных . Возможно, вы захотите изменить элементы p и p+1, например, чтобы лучше их распределить.

Answer 2

Вот простое решение с использованием целочисленной арифметики:

void check(char boxes[], int total_count, int check_count)
{
    int i;

    for (i = 0; i < total_count; i++)
        boxes[i] = '-';

    for (i = 0; i < check_count; i++)
        boxes[i * total_count / check_count] = 'x';
}

total_count - это общее количество блоков, а check_count - это количество блоков для проверки.

Во-первых,это устанавливает каждую клетку на непроверенную.Затем он проверяет check_count ящиков, масштабируя счетчик по количеству ящиков.

Предостережение: это смещение влево, а не вправо, как в ваших примерах.То есть печатается x--x--, а не --x--x.Вы можете перевернуть его, заменив

        boxes[i * total_count / check_count] = 'x';

на:

        boxes[total_count - (i * total_count / check_count) - 1] = 'x';

Корректность

Предполагая 0 <= check_count <= total_count, и что boxes имеет место как минимум для total_count пунктов, мы можем доказать, что:

• Никакие галочки не будут перекрываться.i * total_count / check_count увеличивается по крайней мере на одну на каждую итерацию, потому что total_count >= check_count.

• Это не будет переполнять буфер.Индекс i * total_count / check_count

  • будет >= 0.i, total_count и check_count будут >= 0.

  • будут < total_count.Когда n > 0 и d > 0:

    (n * d - 1) / d < n
    

    Другими словами, если мы возьмем n * d / d и подтолкнем числитель вниз, частное тоже уменьшится.

    Поэтому(check_count - 1) * total_count / check_count будет меньше total_count с учетом сделанных выше предположений.Деление на ноль не произойдет, потому что если check_count равно 0, рассматриваемый цикл будет иметь нулевые итерации.

Answer 3

Bresenham -подобный алгоритм подходит для равномерного распределения флажков. Вывод 'x' соответствует изменению Y-координаты. Можно выбрать начальную ошибку в качестве случайного значения в диапазоне [0..places), чтобы избежать смещения.

def Distribute(places, stars):
err = places // 2
res = ''
for i in range(0, places):
    err = err - stars
    if err < 0 :
        res = res + 'x'
        err = err + places
    else:
        res = res + '-'
print(res)

Distribute(24,17)
Distribute(24,12)
Distribute(24,5)

output:

x-xxx-xx-xx-xxx-xx-xxx-x

-x-x-x-x-x-x-x-x-x-x-x-x

--x----x----x---x----x--

Answer 4

Я думаю, что ключ заключается в том, чтобы подсчитать, сколько ящиков вы ожидаете иметь на один чек.

Допустим, вы хотите 33 чека в 100 коробках.100 / 33 = 3.030303..., так что вы ожидаете иметь один чек каждые 3.030303 ... коробки.Это означает, что каждые 3.030303 ... ящики, вам нужно добавить чек.66 проверок в 100 коробках означают одну проверку каждые 1.51515 ... ящиков, 11 проверок в 111 коробках означают одну проверку каждые 10.090909 ... ящиков и т. Д.

double count = 0;
for (int i = 0; i < boxes; i++) {
    count += 1;
    if (count >= boxes/checks) {
        checkboxes[i] = true;
        count -= count.truncate(); // so 1.6 becomes 0.6 - resetting the count but keeping the decimal part to keep track of "partial boxes" so far
    }
}

Вы могли бы лучше использовать decimal в отличие от double для count, или существует небольшая вероятность того, что последнее поле будет пропущено из-за ошибок округления.

Answer 5

Скажем, количество флажков - C, а число X - N.

В вашем примере указано, что C = 111 и N = 11 - ваш самый неприятный случай.

Попробуйте это:разделить C / N.Назовите это D. Имейте индекс в массиве как двойное число I. Имейте другую переменную как счетчик, M.

double D = (double)C / (double)N;
double I = 0.0;
int M = N;
while (M > 0) {
    if (checkboxes[Round(I)].Checked) { //  if we selected it, skip to next
        I += 1.0;
        continue;
    }
    checkboxes[Round(I)].Checked = true;
    M --;
    I += D;
    if (Round(I) >= C) { //  wrap around the end
        I -= C;
    }
}

Обратите внимание, что Round (x) должен вернуть ближайшее целое значение для x.

Этот может работать на тебя.

Answer 6

Как насчет использования Фишера-Йейтса shuffle ?

Создать массив, перемешать и выбрать первые n элементов. Вам не нужно перетасовывать их все, только первые n массива. Перестановки можно найти в большинстве языковых библиотек.

Answer 7

Адаптируйте код из один ответ на вопрос или другой ответ с ранее в этом месяце. Установите N = x = количество флажков и M = y = число для проверки и примените формулу (N*i+N)/M - (N*i)/M для размеров сечения. (Также см. Ответ Джои Адамса.)

В Python адаптированный код:

  N=100; M=33; p=0;
  for i in range(M):
     k = (N+N*i)/M
     for j in range(p,k-1): print "-",
     print "x",
     p=k

который производит
- - x - - x - - x - - x - - [...] x - - x - - - x
, где [...] представляет 25 --x повторений. С M=66 код дает
x - x x - x x - x x - x x - [...] x x - x x - x - x
, где [...] представляет в основном xx- повторений, с одним x- в середине.

Примечание, в C или Java :
Замените for (i=0; i<M; ++i) вместо for i in range(M):.
Заменить for (j=p; j<k-1; ++j) вместо for j in range(p,k-1):.

Правильность: Обратите внимание, что флажки M = x отмечены, потому что print "x", выполняется M раз.

Answer 8

Быстрое решение html / javascript:

<html>
<body>
<div id='container'></div>
<script>
var cbCount = 111;
var cbCheckCount = 11;
var cbRatio = cbCount / cbCheckCount;
var buildCheckCount = 0;

var c = document.getElementById('container');

for (var i=1; i <= cbCount; i++) {
  // make a checkbox
  var cb = document.createElement('input');
  cb.type = 'checkbox';

  test = i / cbRatio - buildCheckCount;
  if (test >= 1) {
    // check the checkbox we just made
    cb.checked = 'checked';
    buildCheckCount++;
  }

  c.appendChild(cb);
  c.appendChild(document.createElement('br'));
}
</script>
</body></html>