LINUX.ORG.RU
ФорумTalks

Получить из числа рандомные слагаемые

 , ,


0

1

Есть число. Например. 10 миллиардов. 10.000.000.000. 10^10
Мне нужно, получить сто достаточно рандомных слагаемых из этих 10^10, которые бы в сумме дали эти самые 10 миллиардов. И еще, пожалуй, стоит поставить условия, чтобы слагаемые не повторялись.
Как?

Спасибо.


Взять 100 произвольных чисел от 0 до 10^10, сложить, сумму нормализовать до 10^10, потом первые 99 взять нормализованные, а последнее тупо вычитанием, чтобы ошибки округления исчезли. Для создания дополнительной связи в твоем мозгу рекомендую посмотреть также теорему Фалеса.

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

Я могу складывать только палочками. Вы какие-то нецензурные слова говорите. Какой-то Фалос.

Составить рандом из диапазона не сложно, сложно:
1) Разбить число на достаточно рандомные слагаемые или выбрать такие, чтобы исключить недостатки генераторов.
2) Проследить, чтобы там не было двух и более одинаковых чисел.

E2-E4
() автор топика
Ответ на: комментарий от E2-E4

недостатки генераторов

Оказывается, jot - убогая и глючная поделка.
jot uses double precision floating point arithmetic internally and printf(3) for output format, which causes rounding and truncation issues.

E2-E4
() автор топика
Ответ на: комментарий от E2-E4

Чтобы повторов не было, надо брать несовпадающие диапазоны рандома для каждого числа. То есть загадывать от нуля до 10^10 для первого, от первого+1 до 10^10+первое для второго и так далее. Не тупи.

abraziv_whiskey ★★★★★
()

достаточно рандомных

Так рандомных или нет? Мы говорим о натуральных числах, да?

Короче, тебе надо выбрать 99 чисел от 2 до 10^10. x_1, x_2, ..., x_99. Тогда твои слагаемые: (x_1 - 0), (x_2 - x_1),..., (x_(i+1) - x_i), ..., (10^10 - x_99).

Ну а на повторения проверяй просто.

tyakos ★★★
()

Чисто академический ответ можно найти на первых страницах любого учебника по комбинаторике. Подсказка: смотреть число сочетаний с повторениями. В доказательстве черным по белому написан способ разбить число на сумму с помощью «шаров и перегородок».

https://ru.m.wikipedia.org/wiki/Сочетание

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

Проверять на ходу и отбрасывать, если какие-то числа совпали.

aquadon ★★★★★
()

1. Разделить число на 100

2. На каждую полученную пару n, n+1 генерировать рандомное k

3. Вычитать k из n и прибавлять k к n+1

4. Повторить шаги 2, 3 рандомное кол-во раз

Вот, что первое пришло в голову. Зело неэффективно, зато рандомно :)

Deleted
()
Последнее исправление: rj45 (всего исправлений: 1)

man Распределение Дирихле.

soomrack ★★★★
()

Алло! Писец! Это просто писец. Вы что, ударенные в голову?
Я вообще-то спрашиваю в соответствующем форуме. Задал вопрос, надеюсь, в соответствующей теме. Мне все это нужно организовать на шеле или же уже есть готовая тулза, которая может сделать аналогичное. Наподобие factor. Ферштейн?
Я не буду подбирать и искать слагаемые. За меня это должен сделать компьютер.
Ок, Давайте изменим условие задачи, поскольку выше названные цифры были примерными для множества выборок, которые мне нужно получить.

Разбить 1.000.000 на 20.000 слагаемых.


Вы предлагаете это делать ручками?!

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

Да, я дурак. Дуракам легче живется. Думать не надо.

На выше написанный случай, ручками это сделать нетрудно 19.999*(19.999+1)/2+(недостающее до миллиона). Но слагаемых может быть сотни тысяч, а в этом случае рандомом тут и не пахнет, не так ли?

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

1. Разделить число на 100
2. На каждую полученную пару n, n+1 генерировать рандомное k
3. Вычитать k из n и прибавлять k к n+1
4. Повторить шаги 2, 3 рандомное кол-во раз

Ок, как мне это сделать на шелле?

E2-E4
() автор топика

1. Генеришь N рандомных чисел Yn от 1 до твоего X, можно даже до X.

2. Находишь коэффициент C как результат от деления суммы твоих N чисел (S) на X.

3. Делишь каждое число Yn на C, округляешь результат до целого вверх.

4. Проверяешь все числа Yn на повторения, повторяющиеся числа рандомно увеличиваешь или уменьшаешь на 1, пока не перестанут повторяться.

5. Находишь разницу между суммой получившихся целых чисел (снова S) и твоим X.

6. Далее рандомно увеличиваешь (если S<X) или уменьшаешь (если S>X) свои получившиеся числа на 1, пока S не станет равна X, при этом следишь, чтобы результаты уменьшения/увеличения не повторялись.

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

В общем-то, усё. Если слагаемых надо много - можно извернуться куда эффективнее древовидным разбиением, но описывать таковое лениво.

AlexAT
()

Мне нужно, получить сто достаточно рандомных слагаемых из этих 10^10, которые бы в сумме дали эти самые 10 миллиардов. И еще, пожалуй, стоит поставить условия, чтобы слагаемые не повторялись.

Если тебе нужен простой алгоритм то можно вот так примерно(могу в чем-то ошибиться я ведь не математик, но суть должна быть понятна):
Дано: сумма X, количество слагаемых Y, сумма уже полученных слагаемых Z=0, сумма натурального ряда K=(N(N+1))/2.
Считаем от последнего числа к первому, где N номер текущего числа.
Для каждого числа получаем диапазон: от K для текущего числа(минимальное число, нужно чтоб остатка гарантированно хватало с учетом того чтоб не повторялось для остальных чисел) до X-Z. Генерируем случайное число в этом диапазоне, полученное число добавляем в Z. И так для каждого числа, полученные числа сортируем.
Дальше надо отсортировать и пробежаться от большого к малому, если видим два одинаковых числа то отнимаем часть числа и прибавляем его к самому последнему(оно и есть большое) и так до конца. Да в этом случае будет тенденция к тому что самое большое число на большом количестве генераций будет сильно больше. Но можно и другой алгоритм раскидывания частей чисел придумать.

V1KT0P ★★
()

Есть число. Например. 10 миллиардов. 10.000.000.000. 10^10
Мне нужно, получить сто достаточно рандомных слагаемых из этих 10^10, которые бы в сумме дали эти самые 10 миллиардов. И еще, пожалуй, стоит поставить условия, чтобы слагаемые не повторялись.

переводя на нормальный язык - есть диапазон 1..N надо поделить на K отрезков, так чтобы длины отрезков были уникальны и независимы.

шаг 1: порождаем ряд 1..K+1 (последовательно возрастающие числа, количеством K). Сумма ряда=S.. TC может посчитать на досуге, это из 2-го класса.

шаг 2: набрасываем К случайных чисел в диапазоне от S до N (или от 0 до N-S); Уникальность не требуется. - это та сумма которую надо распеределить (добавить) по ряду из шаг1 чтобы сумма получилась N.

шаг 3: длины отрезков из шага 2 сортируем по возрастанию и попарно складываем с числами из шаг 1.

ВСЁ.

MKuznetsov ★★★★★
()
Последнее исправление: MKuznetsov (всего исправлений: 1)

рандомные слагаемые

чтобы слагаемые не повторялись.

Есть мнение, что ты сам не понимаешь, что делаешь.

webmonkey
()

если 100 из 10 миллиардов, то есть вероятность выпадения повторяющихся чисел крайне мала, то в лоб проще всего

>>> pairs = []
>>> while len(pairs) < 200:
...     i1 = random.randint(0, 10000000000)
...     i2 = 10000000000 - i1
...     if not i1 in pairs and not i2 in pairs:
...             pairs += [i1, i2]

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