Онлайн-справочник по самым часто задаваемым вопросам из темы "Как сделать?" на форуме QSP.su
20.12. Как решить задачу по поиску случайного набора слагаемых?
В: Как решить задачу по поиску случайного набора слагаемых?
Например, есть набор чисел 2,3,5 и 9, и нужно случайным образом выбрать из них несколько чисел (можно одинаковых), которые в сумме составляют 9. Как это реализовать?
О:
Для начала разберём алгоритм для этого конкретного случая, а затем попытаемся написать более универсальную процедуру.
mass[0]=2
mass[1]=3
mass[2]=5
mass[3]=9
! задаём "сумму" выброшенных чисел = 9
summ = 9
! далее начинается цикл.
loop while 1:
! выкидываем число
! получаем индекс
index = rand(0,arrsize('mass')-1)
! фиксируем число
number=mass[index]
! проверяем, возможно ли вычитание
if summ - number = 0:
! если при вычитании числа из summ получается 0, значит мы нашли последнее число
! записываем его
search[]=number
jump 'cycle_end' & ! прерываем цикл
elseif summ - number < min('mass'):
! если разность summ и числа - меньше минимального значения в массиве, значит
! число, которое мы вытянули, нам не подходит
! и не подойдёт, его можно убрать из исходного массива
killvar 'mass',index
! записывать его не нужно
else
! во всех остальных случаях число нам подходит:
! запоминаем его в конечный массив
search[]=number
! уменьшаем summ на это число
summ -= number
end
end
:cycle_end
Как видим, алгоритм генерации случайного набора слагаемых довольно прост. Однако он предполагает, что нам изначально известны слагаемые, на которые может быть разложена исходная сумма.
Можно написать универсальную процедуру для подобных случаев (назовём её "summ.break"):
local summ = args[0] & ! Сумма, для которой мы получаем набор слагаемых
local $addiction = $args[1]+',' & ! набор слагаемых через запятую
local mass & ! локальный массив, в который мы будем помещать слагаемые
! предварительно вытаскиваем в массив mass[] наши слагаемые
loop while len($addiction)>0:
! запоминаем число
mass[]=val($mid($addiction,1,instr($addiction,",")-1))
! удаляем его из строки
if instr($addiction,",")<>len($addiction):
$addiction=$mid($addiction,instr($addiction,",")+1)
else
$addiction=''
end
end
! Теперь выполняем тот же алгоритм, что мы уже писали,
! только исключая лишние глобальные переменные
local index_, number_
! начинается цикл.
loop while 1:
! получаем число (слагаемое) из массива
! получаем индекс
index_ = rand(0,arrsize('mass')-1)
! фиксируем число
number_=mass[index_]
! проверяем, возможно ли вычитание
if summ - number_ = 0:
! если при вычитании числа из summ получается 0, значит мы нашли последнее число
! записываем его
search[]=number_
jump 'endandexit'
elseif summ - number_ < min('mass'):
! если разность summ и числа - меньше минимального значения в массиве, значит
! число, которое мы вытянули, нам не подходит
! и не подойдёт, его можно убрать из исходного массива
killvar 'mass',index_
! записывать его не нужно
elseif arrsize('mass')<1:
! защита от дурака. Если размер массива mass упал до нуля, значит мы перебрали все
! возможные варианты и значит изначальное условие задано неверно или
! решение, которое начал подбирать алгоритм изначально неверно подбиралось
! *pl 'неверное решение'
! $result = 'false'
jump 'endandexit'
else
! во всех остальных случаях число нам подходит:
! запоминаем его в конечный массив
search[]=number_
! уменьшаем summ на это число
summ -= number_
end
end
! результат прописывается в массив search
! массив mass удаляем, он был временным
:endandexit
Вариант вызова для исходной задачи:
Данный алгоритм не включает в себя защиту от некоторых ошибок. Две очевидные:
- Вы не знаете изначально можно ли получить для данного числа хоть один набор слагаемых из тех, что даны.
- Перечень слагаемых включает числа, из которых можно получить набор слагаемых, но не во всех случаях.
Обе эти ошибки не должны приводить к зацикливанию, но их всё равно стоит избегать.
См. так же: тянем карту из колоды, сортировка данных.