时间戳

首页 > 解决方案 > 生成 N 个具有 X 位的随机数，使得差（从上到下减去的数字）为正

random - 生成 N 个具有 X 位的随机数，使得差（从上到下减去的数字）为正

问题描述

我正在尝试生成 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（一个正数），当一切都被减去并且我可以停止时

我也不介意我是否必须做几次，但我想将尝试次数保持在最低限度

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

标签： randomlanguage-agnosticdifference

解决方案

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

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

我在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

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

推荐阅读