LINUX.ORG.RU

Разделение числа на заданное числа кусков разной длинны.

 , ,


0

1

Есть делимое, например 36000, делитель может быть от 50 до 20000 к примеру. И мне надо разделить так, чтобы каждый кусок генерировался случайным размером. Т.е. первый может быть 15, второй 567, третий 20000 и т.д. и их будет заданное заранее количество, а их сумма будет равна начальному числу. Как это проще реализовать? Реализую на PHP, но вопрос задал тут, т.к. алгоритм не связан с языком, а мне нужен сам алгоритм для этой операции.

★★

Условие о заданном числе кусков несовместимо с предположением о равномерном случайном распределении от n1 до n2. Надо какое-то из двух условий ослабить.

Deleted
()
Ответ на: комментарий от Deleted

Ну почему же несовместимо? Если самый простой пример. Число 10 разбить случайно на 3 части. Это и 1 3 6 это и 2 4 4. Есть сумма, есть число частей. Предположим мне не важна равномерность все таки, а скорее мне нужно просто со случаным расстоянием между числами (у меня это как бы применяется за временную прямую, разделяю я именно время, и мне надо разбить на случайные временные отрезки)

Bupyc ★★
() автор топика
Ответ на: комментарий от Deleted

о равномерном случайном распределении

а где такое в условии?

в этом видимо и есть задача, понять, что есть равномерно в данном случае.

dimon555 ★★★★★
()

n-часть = 36000/(n-1)

потом находим n-часть-эффективная = рандом от 50 до 36000/(n - 1)

n-часть-остаток = n-часть - n-часть-эффективная

так ты найдёшь n-1 частей, а последняя будет сумма остатков.

dimon555 ★★★★★
()

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

swwwfactory ★★
()

может ещё отнимишь 50/(n-1), чтобы всегда 50 оставалось и какую-нить манипуляцию, чтобы не больше 20000 если n = 2.

dimon555 ★★★★★
()

Нагенерируй случайных чисел нужное количество. Сложи, а потом каждое число подели на сумму. Получишь случайные числа с суммой равной 1.0

Теперь умножь каждое на желаемую сумму. Если в результате сумма не сойдется, то вычисли одно число, как разницу суммы и суммы остальных n-1 чисел.

vertexua ★★★★★
()

делитель может быть от 50 до 20000

первый может быть 15

anonymous
()

Есть делимое ... делитель ...
а их сумма будет равна начальному числу

Может для начала почитать учебник за четвертый класс :)

arson ★★★★★
()
Ответ на: комментарий от dimon555

последняя будет сумма остатков

а если она получится меньше 50?

anonymous
()
Ответ на: комментарий от vertexua

беда с минимальной границей, но в принципе хорошее решение

anonymous
()

Путь тебе нужно N кусков. Генерируешь N случайных чисел, вычисляешь их сумму. Пусть сумма оказалась равна S. Теперь каждое число умножаешь на 36000 и делишь на S. Это и есть размеры твоих искомых кусков.

При вычислении суммы и при умножении важно не наткнуться на целочисленное переполнение или на флоатпоинт потерю точности (из-за неправильного порядка суммирования).

Осталось разобраться с округлением до целых, оставим это тебе в качества домашнего задания.

Manhunt ★★★★★
()
Ответ на: комментарий от Manhunt

Вроде я понял что вы имели в виду. Если проще сказать мы переводим размерность суммы случайных чисел в нужную нам размерность. Удобный вариант. Надо будет попробовать его. Если конечно не появятся варианты лучше. Но вообще по идее получается то что надо - будут и маленькие куски и большие и можно манипулировать именно расстоянием между точками.

Bupyc ★★
() автор топика
Ответ на: комментарий от anonymous

С минимальной границей, как раз, никаких проблем нет. Если у него минимум равен 20, то целиться нужно не в 36000, а в 36000-N*20. Когда будет получено разбиение для такой цели, останется добавить к каждому куску по 20.

Manhunt ★★★★★
()

на самом деле задача решается как «выкинуть N уникальных случайных чисел в диапазоне от Min до Max»

function unirand($min,$max,$count) {
  $generated=0;
  $found=array();
  while($generated<$count) {
    $num=rand($min,$max);
    if (array_key_exists($num,$found))
       continue;
    $found[$num]=true;
    $generated++;
  }
  return array_keys($found);
}
сниппет не проверял, но мысль надеюсь понятна

MKuznetsov ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.