Нужен совет по алгоритму

← →
atruhin © (2014-08-07 13:18) [0]

Нужен совет по реализации алгоритма генерации случайных сумм чеков.
Система тестирования.
Дано:
- общая сумма чеков
- количество чеков в день
- мин и макс суммы чека (мин от 1 макс до общая сумма чеков)
Нужно:
создать список чеков, общая сумма и количество должны совпадать полностью, а суммы отдельных чеков должны быть случайными от мин до макс

← →
картман © (2014-08-07 13:22) [1]

рекомендую в налоговой спросить

← →
atruhin © (2014-08-07 13:25) [2]

Единственное, что приходит в голову: создать массив нужного кол-ва чеков, распределить всю сумму поровну, затем несколько итераций со случайными инкрементами одного чека и декрементами другого (случайного).

← →
atruhin © (2014-08-07 13:27) [3]

>> картман ©
Умно. Но не в тему

← →
short circuit (2014-08-07 17:57) [4]

можно разбить чеки на пары с одинаковой суммой = общая/кол-во*2 или часть пар - min+max, а часть - что останется/кол-во*2
внутри пары - рандомный разброс с учетом min

← →
codingbat (2014-08-07 18:02) [5]

можно сделать рекурсивную ф-цию, разбивающую заданное количество и сумму на две части по количествам и суммам с учетом min и max, и, если количество=1, заполнять выходной массив

← →
short circuit (2014-08-07 18:04) [6]

для верности 2 чека с min и max суммами формировать отдельно

← →
Дмитрий СС (2014-08-07 18:43) [7]

Как вариант сделать массив чеков с минимальной суммой чека. А потом в цикле добавлять по копейке (рублю) в случайный чек до тех пор пока сумма не получится равной необходимой.

← →
Mystic © (2014-08-07 19:21) [8]

Первое что приходит в голову

procedure GenInvoices(Sum, N, Min, Max: Integer); var NewMin, NewMax, Value: Integer; IsSafe: Boolean; begin repeat if N = 1 then begin { We have not any choice here and should return Sum } { The following condition is needed to avoid incorrect argument like GenInvoices(10, 1, 2, 3) } if (Sum >= Min) and (Sum <= Max) then begin PrintInvoice(Sum); end else begin Fail("Impossible!"); end; Exit; end; repeat { We have Min and Max values here, but we cannot just select value from this range } { Some values inside range would cause dead case } { So we try calculate new range whick contains only safe values } { This flag is used to indicate that all value from range [Min, Max] are valid } IsSafe := True; { Try to estimate new minimum and maximum values } { Assumt that all values in the range except last is equal to Max (Min) } { In this case we can calculate last invoice value } { And this is smallest (biggest) possible value in a range } NewMin := Sum - (N-1) * Max; NewMax := Sum - (N-1) * Min; { Tune new range } if NewMin > Min then begin Min := NewMin; IsSafe := False; end; if NewMax < Max then begin Max := NewMax; IsSafe := False; end; { If interval is not changed we can select value from it } if IsSafe then Break; { Empty interval, we can not generate invoiced } if Max < Min then begin Fail("Impossible!"); Exit; end; { In this point we reduce interval. Let"s try to reduct it again } until False; { Select random value from save interval } Value := Min + Random(Max-Min+1); PrintInvoice(Value); Sum := Sum - Value; N := N - 1; until False; end;

← →
MBo © (2014-08-07 21:22) [9]

Дано: N, Sum, Min
Сгенерировать N случайных чисел Ri от 0 до 1
Найти их сумму RSum
Вычислить коэффициент K = (Sum - N *Min) / RSum
Отмасштабировать числа
Ci = Min + Ri * K

← →
картман © (2014-08-08 02:29) [10]

а в данной отрасли суммы чеков распределены равномерно? Не, ну будь я налоговым инспектором...

← →
antonn © (2014-08-08 08:39) [11]

> а в данной отрасли суммы чеков распределены равномерно?

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

← →
oldman © (2014-08-08 09:23) [12]

Дано:
количество чеков N на общую сумму S1

Генерируем N-1 чек на общую сумму S2
Сумма последнего чека S1-S2

Необходимое условие: S2<S1

Решишь условие - решишь задачу

← →
atruhin © (2014-08-08 10:34) [13]

>> картман © ну куда ты лезешь со своим налоговым инспектором? Ты вообще знаком с торговой техникой: ККМ, ЭКЛЗ?
Я этим годами занимаюсь и не представляю где можно применить генерацию чеков себе во благо. Может поделишься?

>> antonn © Да я в общем то и написал сразу - система тестирования. Распределенная торговая система со всеми скидками бонусами + репликация.
Вот для контроля репликатора это и нужно.

>> Mystic © Спасибо. Смотрю разбираюсь.

>> MBo © Спасибо. Просто и элегантно. Вроде то что нужно.

← →
atruhin © (2014-08-08 10:36) [14]

>> oldman © Генерируем N-1 чек на общую сумму S2
Круто. Но в этом и был вопрос, как сделать это генерируем. :)

← →
oldman © (2014-08-08 11:38) [15]

> atruhin © (08.08.14 10:36) [14]

Для первого чека min=1, max=(S1/N)*2 (генерируется чек на сумму k1)
Для второго чека min=1, max=((S1-k1)/(N-1))*2 (генерируется чек на сумму k2)
Для третьего чека min=1, max=((S1-k1-k2)/(N-2))*2 (генерируется чек на сумму k3)
...

Принцип понятен?

Протестировал. Подумал. Понял что могу отказаться от max, изменив/разделив тесты, в итоге использовал вариант MBo ©.
Но если перевести задачу на теоретический уровень, то пока решения нет.

>> Mystic © близко, но на первой половине съедается дин.диапазон, а дальше идет сплошной min.
Вызов: GenInvoices(15000, 15,100, 7000);
100 316 6042 1498 1722 3003 552 256 402 317 124 227 110 210 121
Здесь все более менее нормально.

Вызов: GenInvoices(15000, 15,100, 5000);
392 1537 4595 1903 3896 650 886 388 138 104 101 103 103 101 103
А здесь проблема.

>> MBo © не учитывается max. В итоге низкий динамический диапазон значений.
GenInvoices(15000, 15,100, 5000);
1555 592 949 363 1641 606 1462 1821 968 1665 1558 136 349 353 983

> oldman © (08.08.14 11:38) [15]

Именно это и привел выше Mystic © (07.08.14 19:21) [8]. Получается нисходящая последовательность, т.е. нужно тасовать. Главная проблема что очень быстро в ней остаются одни min.

> atruhin © (08.08.14 10:34) [13]
>
> >> картман © ну куда ты лезешь со своим налоговым инспектором?
> Ты вообще знаком с торговой техникой: ККМ, ЭКЛЗ?
> Я этим годами занимаюсь и не представляю где можно применить
> генерацию чеков себе во благо. Может поделишься?

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

>не учитывается max. В итоге низкий динамический диапазон значений.
Подозреваю, что невозможно соблюсти все условия одновременно.
А большие значения в наборах встречаются (я строил гистограммы распределения), только при значительных соотношениях F =N*Max/Sum их будет очень мало, что естественно.
Можно подбирать закон распределения случайной величины, отличный от равномерного, чтобы получить более заметное количество больших значений - но это будет работать только при определенных F

> картман ©56 после рабочего дня стираешь все пробитые чеки за день

Да, так и было, до полного введения ЭКЛЗ в 2007 году, в ЭКЛЗ встроен криптопроцессор (закрытый ключ контролируется ФСБ), каждый чек подписывается кпк который можно проверить на открытом сайте. Ни какой информации о взломе КПК не слышал, хотя занимаюсь этим более 15 лет.
Так что поверь, но если бы я хотел что то скрывать, то уж догадался бы вместо слова чек, написать слово число.

> MBo © Подозреваю, что невозможно соблюсти все условия одновременно.

Математически да, наверное невозможно. Ладно, спасибо за помощь и участие. Вопрос решен. Тему можно считать закрытой.

> >> Mystic © близко, но на первой половине съедается дин.
> диапазон, а дальше идет сплошной min.

Ну... это же первое, что приходит в голову. Дальше можно улучшать. Я же не знаю всех требований. Опять же, навскидку

1. Использовать не равномерное случайное распределение Min..Max, а какое-то другое. Например, S/N можно взять в качестве математического ожидания, ассиметрия должна быть компенсировать разницу в интервалах Min..S/N, S/N..Max.

2. В конце заняться подгонкой последовательность, например N раз добавляя единицу и некоторого члена со значением X < S/N и вычитая единицу у некоторого другого члена X > S/N.

Нужен совет по алгоритму Найти похожие ветки