生成N个随机数，其中X位数使得差值（从上到下减去的数字）为正

Question

我正在尝试生成 N 个数字为 X 的随机数，以便差值始终为正。

我能想到的最好的方法是生成 N 个数字

10,11,30,49,50 然后对它们进行排序，50,49,30,11,10 并找到差异 -50 如果它是负数，就像在这种情况下，我会重新做整个过程。

如你所想，这是一种非常暴力的方式，而且速度很慢。有更好的方法吗？

如果有帮助，N 和 X 最大为 5。

如果不清楚，

我需要的是生成一组数字。然后当你减去所有这些数字时，你会得到一个肯定的答案。在我的示例中，我生成的随机数是 10、11、30、49、50。我知道得到正数的最好方法是用最小的数减去最大的数。所以我把它们从大到小排序了。 50,49,30,11,10 然后减去它们，我得到 -50（负数）所以我必须重新开始，直到我得到类似 90,20,30,10,11 的东西，排序时给我 90,30 ,20,11,10 是 19（一个正数）当一切都被减去我可以停止

我也不介意多做几次，但我想尽量减少尝试次数

换句话说，我正在寻求生成一系列数字，其中最大值减去所有其他值的总和始终为正数

Answer 1

您可以使用基于斐波那契数列的随机方法生成一个数字。

在斐波那契数列中，您根据之前的数列生成一个数字。如果你想要一个随机的正数，只需要生成一个随机数并将其添加到最后一个，这将永远满足你的要求。

我在 python

中做了一个片段

import random

number_list=[]
r_number=0
while(r_number < 100):
    b_number=random.randint(1,10)
    r_number += b_number
    if r_number<100:
        number_list.append(r_number)
print(number_list)

结果：

第一次执行：

[4, 14, 22, 24, 26, 28, 29, 34, 35, 36, 46, 48, 51, 56, 64, 72, 79, 89, 98]

第二次执行：

[7, 13, 19, 27, 34, 35, 39, 43, 45, 48, 52, 58, 68, 74, 83, 86, 88, 93, 99]

这种方法的优点（如果您稍微优化一下代码可能会更好）是复杂度为 O(n)（线性），而不是您使用的任何一种排序算法。

希望我已经解决了你的疑惑最后，个人意见：最好的有序集合是已经有序的集合。

编辑 1：我看到您需要的最大数量大于其他数量的总和，这是一个简单的变化。

import random

number_list = []
r_number = random.randint(1, 10)
LIMIT=1000

while r_number < LIMIT:
    sum_ = sum(number_list)
    r_number = random.randint(sum_, sum_ + 10)
    number_list.append(r_number)

if number_list[-1] > LIMIT:
    del number_list[-1]

print(number_list)
print("Last element minus the rest equals",number_list[-1] - (sum(number_list) - number_list[-1]))

结果

[3, 4, 7, 21, 37, 72]
0

[9, 19, 38, 74]
8

[4, 4, 11, 20, 47, 96]
10

[4, 5, 10, 26, 55]
10

我刚刚尝试将 LIMIT 设置为 1e99 并对其计时：

Last element minus the rest equals 7

real    0m0,023s
user    0m0,020s
sys     0m0,000s

您可以从中推断出大量输出

./test.py |wc -c
17109

计算程序输出给出的字符数。在这种情况下，非常长的整数。

生成N个随机数，其中X位数使得差值（从上到下减去的数字）为正

generate N random numbers with X digits such that the difference(the numbers subtracted from top to bottom) is positive

language-agnostic

random

difference