algorithm - 如何找出没有疯狂递归量的随机生成的先前值？

Question

假设我需要生成 100 个数值。每次生成的值必须大于或等于上一次生成的值。问题是每个单独的值必须在需要时在现场生成，因此我们不存储任何数据。我有一个使用递归的解决方案，但问题是如果我想生成第 100 个值，它必须递归地生成并检查所有以前的值，你可以想象这很糟糕。问题更加复杂，因为如果我生成第 100 个值，我不确定第 99 个值是否准确。也许第 99 个值小于第 98 个值，所以第 99 个值必须进行检查 - 所以在生成第 100 个值时，我们不仅必须检查第 99 个值，还可能检查第 98 个值，等等...... 有没有什么方法可以在不事先生成和存储所有数据的情况下更雄辩地解决这个问题？谢谢！

标签： algorithmperformancerecursionmathdynamically-generated

Answer 1

每次生成的值必须大于或等于上一次生成的值。

只需从前一个值生成一个随机位移；喜欢：

    next_value = previous_value + get_random_value_from_zero_to_whatever();
    previous_value = next_value;

你需要担心的问题（不管你怎么做）是耗尽——当前一个值是可能的最高值时会发生什么（例如INT_MAX，如果你正在使用int）。您是否继续使用相同的最高可能值而完全没有随机性（以避免较小的值），或者......？