Как разделить число на целые числа, каждое из которых кратно n?

Question

Трудно было придумать краткое название для этого. Я уверен, что есть условия для того, чего я хочу достичь, и нет никаких сомнений в том, что есть общий алгоритм для достижения того, чего я добиваюсь - я просто еще не знаю о них.

Мне нужно разбить число на n частей, каждая из которых кратна 50. Число само по себе кратно 50. Вот пример: Разделите 5000 на 3 и получите три числа, каждое из которых кратно 50:

• 1650
• 1700
• 1650

Я также хотел бы, чтобы числа распределялись так, чтобы они переворачивались взад и вперед, вот пример с большим количеством чисел, чтобы проиллюстрировать это: Разделите 5000 на 7 и получите 7 чисел, каждое из которых кратно 50:

• 700
• 750
• 700
• 750
• 700
• 700
• 700

Обратите внимание, что в приведенном выше примере меня не беспокоит, что дополнительные 50 не центрированы в ряду, то есть мне не нужно иметь что-то вроде этого:

• 700
• 700
• 750 <--- обратите внимание, что '50' центрированы </li>
• 700
• 750 <--- обратите внимание, что '50' центрированы </li>
• 700
• 700

Надеюсь, я спросил это достаточно ясно, чтобы вы поняли, чего я хочу достичь.

Обновление: вот функция, которую я буду использовать.

var number = 5000;
var n = 7;
var multiple = 50;

var values = getIntDividedIntoMultiple(number, n, multiple)

function getIntDividedIntoMultiple(dividend, divisor, multiple)
{
    var values = [];
    while (dividend> 0 && divisor > 0)
    {
        var a = Math.round(dividend/ divisor / multiple) * multiple;
        dividend -= a;
        divisor--;
        values.push(a);
    }

    return values;
}

Answer 1

var number = 5000;
var n = 7;

var values = [];
while (number > 0 && n > 0) {
    var a = Math.floor(number / n / 50) * 50;
    number -= a;
    n--;
    values.push(a);
}  // 700 700 700 700 700 750 750

Редактировать

Вы можете чередовать Math.floor и Math.ceil для получения желаемого результата:

while (number > 0 && n > 0) {
    if (a%2 == 0)
        a = Math.floor(number / n / 50) * 50;
    else
        a = Math.ceil(number / n / 50) * 50;
    number -= a;
    n--;
    values.push(a);
}  // 700 750 700 750 700 700 700

Answer 2

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

Например, разделив 10000 долларов на 7 почти равных пачек 50-долларовых банкнот.

function getBundles(sum, denomination, count, shuffle)
{
  var p = Math.floor(sum / denomination);
  var q = Math.floor(p / count);
  var r = p - q * count;

  console.log(r + " of " + ((q + 1) * denomination)
      + " and " + (count - r) + " of " + (q * denomination));

  var b = new Array(count);
  for (var i = 0; i < count; i++) {
    b[i] = (r > 0 && (!shuffle || Math.random() < .5 || count - i == r)
        ? (--r, q + 1) : q)
      * denomination;
  }

  return b;
}

// Divide 10,000 dollars into 7 near-equal bundles of 50-dollar bills
var bundles = getBundles(10000, 50, 7, true);

console.log("bundles: " + bundles);

Выход:

4 of 1450 and 3 of 1400
bundles: 1400,1450,1450,1400,1450,1400,1450

Если последний аргумент shuffle равен true, дополнительная сумма распределяется случайным образом между пакетами.

Answer 3

Ваша проблема такая же, как деление числа X на N целых чисел, которые находятся в пределах 1 друг от друга (просто умножьте все на 50 после того, как вы нашли результат) . Сделать это легко - установите все N числа на Floor(X/N), затем добавьте 1 к X mod N из них.

Answer 4

Позвольте a быть вашим начальным числом, k - количеством частей, на которые вы хотите разделить.
Предположим, что b = a / n.
Теперь вы хотите разделить b на k близких целочисленных частей.

• Взять k чисел, каждое из которых равно b / k (целочисленное деление).
• Добавьте 1 к первым b% k числам.
• Умножьте каждое число на n.

Пример: a = 5000, n = 50, k = 7.
b = 100
Начальная серия {14, 14, 14, 14, 14, 14, 14}
Добавьте 1 к первым 2 целым числам {15, 15, 14, 14, 14, 14, 14}.
Умножить на 50 {750, 750, 700, 700, 700, 700, 700}.

Answer 5

// i - an integer multiple of k
// k - an integer
// n - a valid array length
// returns an array of length n containing integer multiples of k
// such that the elements sum to i and the array is sorted,
// contains the minimum number of unique elements necessary to
// satisfy the first condition, the elements chosen are the
// closest together that satisfy the first condition.
function f(i, k, n) {
  var minNumber = (((i / k) / n) | 0) * k;
  var maxNumber = minNumber + k;
  var numMax = (i - (minNumber * n)) / k;
  var nums = [];
  for (var i = 0; i < n - numMax; ++i) {
    nums[i] = minNumber;
  }
  for (var i = n - numMax; i < n; ++i) {
    nums[i] = maxNumber;
  }
  return nums;
}

Итак, ваш второй пример будет

f(5000, 50, 7)

, что дает

[700,700,700,700,700,750,750]

Answer 6

Мой алгоритм обеспечивает равномерное распределение остатка по частям:

function splitValue(value, parts, multiplicity)
{
    var result = [];
    var currentSum = 0;
    for (var i = 0; i < parts; i++)
    {
        result[i] = Math.round(value * (i + 1) / parts / multiplicity) * multiple - currentSum;
        currentSum += result[i];
    }
    return result;
}

Для значения = 5000, частей = 7, кратности = 50 возвращается

[ 700, 750, 700, 700, 700, 750, 700 ]

Answer 7

Вот мой дубль:

public static void main(String[] args) {
    System.out.println(toList(divide(50, 5000, 3)));
    System.out.println(toList(divide(50, 5000, 7)));
    System.out.println(toList(divide(33, 6600, 7)));
}

private static ArrayList<Integer> toList(int[] args) {
    ArrayList<Integer> list = new ArrayList<Integer>(args.length);
    for (int i : args)
        list.add(i);
    return list;
}

public static int[] divide(int N, int multiplyOfN, int partsCount) {
    if (N <= 0 || multiplyOfN <= N || multiplyOfN % N != 0)
        throw new IllegalArgumentException("Invalid args");

    int factor = multiplyOfN / N;
    if (partsCount > factor)
        throw new IllegalArgumentException("Invalid args");

    int parts[] = new int[partsCount];
    int remainingAdjustments = factor % partsCount;
    int base = ((multiplyOfN / partsCount) / N) * N;

    for (int i = 0; i < partsCount; i ++) {
        parts[i] = (i % 2 == 1 && remainingAdjustments-- > 0) ? base + N : base;
    }

    return parts;
}