GD Star Rating
loading...

Помогите придумать алгоритм
Нужна функция, принимающая два числа N и M, и возвращающая массив из M случайных чисел, которые в сумме дают N.

31 Responses to Помогите придумать алгоритмНужна функция, принимающая два числа N и M, и возвращающая массив из M случайных чисел, которые в сумме дают N.

  1. Mvxmac:

    Наивный вариант чем не устраивает? – генерить M-1, последнее будет N минус сумма генеренных.

  2. Aklre:

    я думаю здесь без генетических алгоритмов не обойтись

  3. Aklre:

    ну или берём N делим случайно неравно на две части X+Y=N
    получили массив из двух(К) элементов, М=К?
    берём Х, случайно делим на два слагаемых, Х1+Х2=Х
    Х1, Х21…Y21, Y1
    ну и так далее с двумя внутренними слагаемыми

    O(M)

  4. Aklre:

    : а вдруг отрицательные нельзя?

  5. Ovenode:

    очень просто же: представь что N не просто число а отрезок [0,N] тогда если тебе надо разбить его на M меньших отрезков, ты просто берёш M-1 случайных чисел [0,N], потом для простоты отсортируем их и назовём (n1,n2,..nm-1) получается M отрезков, сумма длин которых равна N. Длинну отрезка можно посчитать как n1-0, n2-n1, …, N-nm-1.

  6. VorYes:

    : то, что нужно, спасибо

  7. Mvxmac:

    : Я просто намекаю, что неплохо было бы понимать, что именно подразумевается под “случайными числами”.

  8. VorYes:

    : совсем не понял (а «получается M отрезков, сумма длин которых равна N» противоречит предыдущему шагу, если мы генерируем M-1 случайных чисен [0, N], то далеко не факт, что в сумме будет N).

  9. Ovenode:

    : вобща да это проще чем у меня, разделяй и властвуй прям по учебнику

  10. VorYes:

    : а какие есть варианты? )

  11. Aklre:

    : да я сам офигел. он ещё и рекурсивный. что, конечно, недостаток, но красиво.

  12. Aklre:

    : натуральные, целые, рациональные, иррациональные, содержащие тройку

  13. Ovenode:

    : не всё правильно мы же складываем не сами числа, а длинны отрезков на которые эти точки делят прямую.

  14. Fiaer:

    : то есть не хватит до n

  15. Fiaer:

    m-1 отрезков в интервале [0, n/m], последний – то, его не хватит до m.

  16. Hsvhlam:

    каких чисел? если вещественных, берём массив A из M случайных чисел и потом каждое число умножаем на N/sum(A).

  17. Rotko:

    > ты просто берёш M–1 случайных чисел [0,N]… получается M отрезков

    Возможно, неявно подразумеваются какие-то дополнительные требования относительно закона распределения. Например, неплохо было бы, если бы длины были распределены равномерно. Если же распределять равномерно правые концы, как в предложенном способе, то длины будут распределены не равномерно, а будут крутиться вокруг N/M.

  18. Remnode:

    Может быть я и не прав, но вот. Си, но суть ясна. http://codepad.org/P2cFtgBD

  19. VorYes:

    Числа должны быть целые положительные

  20. VorYes:

    : : объясните мне пожалуйста этот способ с отрезками, на примере может быть?

  21. Aklre:

    : тогда мой способ нужно доработать, ибо если при первом шаге X станет 1, его уже делить будет нельзя.

  22. VorYes:

    : угу, это я учёл, но очень криво получается http://pastebin.com/ZA0kbhJ0

  23. Ovenode:

    : ну вот изобразил пример http://jsfiddle.net//M6bhD/
    рисовать как это работает мне если чесно влом

  24. VorYes:

    : спасибо, теперь понятно, круто )

  25. Lekon:

    : предположим, что в предельном случае длины статистически отрезков предполагаются равным N/M. Что то типа суммы квадратов отклонений от N/M в одной выборке, которая должна иметь нормальное распределение – т.е. с одной стороны предельный случай это когда все отрезки равны, с другой – когда один очень большой, остальные по единице. И вот я думаю эта величина должна по идее иметь нормальное распределение. Тогда этот способ пригоден только если M является степенью двойки. Например, пусть М равно 3-м. По алгоритму получается так – делим пополам, потом одну из частей делим пополам. Длина одного из отрезков будет статистически получаться равной M/2.

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

  26. Aklre:

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

    N/2-1, 1, 1, N/2-1 тупиковая ситуация для моего способа.
    то есть возможно, да, нужно ввести ограничение x<=N/M на “наружное” случайное число

  27. Lekon:

    : Можно так наверное: возьмем произвольный шаг итерации. Пусть S – накапливаемая сумма, SM – число посчитанных элементов
    Рассчитываем диапазон возможных значений очередного числа – MIN: 1, MAX: (N – S – (M – SM – 1)).
    Просто случайная выборка на этом диапазоне даст нам мат. ожидание (MAX – MIN)/2.
    А нас это не устраивает, т.к. в этом случае получаются точки притяжения в виде N/2, N/4 и т.д.
    Т.е. нужно сгенерировать число с заданным законом распределения, можно как то так наверное. Задача – подвинуть мат. ожидание от (MAX-MIN)/2 к числу N/M.

  28. Lekon:

    : а проще наверное так – нагенерировать M каких нибудь чисел R1…RM, а потом нормализовать их – привести к виду Ki = Ri/sum(R).
    Ну а дальше разбиение построить как XI = KI*N.

  29. Aklre:

    : слишком усложняем.

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

  30. Lekon:

    : ну да, согласен – сдвиг мат. ожидания к N/M – то же самое что просто случайно точек на отрезке наставить 🙂
    Но вот если понадобится “не совсем случайно” разбиение генерировать…

Добавить комментарий