Разбить число на несколько случайных диапазонов
Есть исходное число, к примеру 100.
Есть рандом, к примеру 5-50.
Надо разбить 100 на случайные числа в диапазоне 5-50 которые в сумме дадут 100.
На выходе получаем 35, 50, 15
Целый день голову ломаю, не могу придумать как решить.
Подскажите пожалуйста.
Ответы (2 шт):
Количество чисел неограниченно (пусть n чисел), поэтому будем получать n-1 случайное число и проверять, входит ли разность суммы полученных чисел и исходного числа в заданный диапазон:
$inputInt = 100;
$inputMin = 5;
$inputMax = 50;
$output = array();
$error1 = false;
$error2 = false;
$error3 = false;
if ($inputInt < $inputMin) exit;
while (true) {
if ($inputInt < $inputMax && $inputInt > $inputMin) {
$output[] = $inputInt;
break;
} else {
$newInt = random_int($inputMin, $inputMax);
if ($inputInt-$newInt > $inputMin) {
$output[] = $newInt;
$inputInt -= $newInt;
} else {
$error1 = true;
$len = count($output);
for ($i = 1; $i <= $len; $i++) {
$num = ($output[$len-$i] + $inputInt) / 2;
$isInt = is_int($num);
if ($num > $inputMin && $num < $inputMax) {
$output[$len-$i] = $isInt? $num : $num-0.5;
$output[] = $isInt? $num : $num+0.5;
break;
}
if ($i == $len) {
if ($error2) {
$inputInt += array_shift($output);
$error3 = true;
} else {
$error2 = true;
}
}
}
}
}
}
if ($error1) echo "Остаток меньше минимума\n";
if ($error2) echo "Случайное число не может войти в ответ\n";
if ($error3) echo "Алгоритм удалил один из элементов\n";
for ($c = 0; $c < count($output); $c++) {
echo $output[$c]." ";
}
Пример вывода:
//Хороший случай
19 6 45 30
//Неплохой случай
Остаток меньше минимума
13 43 44 24 26
//Плохой случай
Остаток меньше минимума
Случайное число не может войти в ответ
47 8 45
//Очень плохой случай
Остаток меньше минимума
Случайное число не может войти в ответ
Алгоритм удалил один из элементов
42 29 29
P.S. немного доработал алгоритм: если последнее число меньше минимума, то пытаемся найти число в массиве, среднее арифметическое с остатком которого даст нам число в диапазоне.
P.P.S статистика на 1 миллион разбиений числа 100:
Всего ошибок: 23657 // остаток оказался вне диапазона (меньше минимума)
Ошибок №2: 9820 // случайное число не подошло
Ошибок №3: 945 // второе случайное не число не подошло, первый элемент удалён
Пример на C#, методом подбора ряда рандомных чисел:
int number = 100;
int min = 5;
int max = 50;
Random rng = new Random();
List<int> numsList = new List<int>();
do
{
if (numsList.Sum() > number)
{
numsList.RemoveAt(0);
continue;
}
numsList.Add(rng.Next(min, max + 1));
} while (numsList.Sum() != number);
foreach (int item in numsList) Console.WriteLine(item);