Как выяснить предыдущее значение, которое генерируется случайным образом без сумасшедшего количества рекурсии?

Question

Допустим, мне нужно сгенерировать 100 числовых значений. Значение, которое генерируется каждый раз, должно быть больше или равно предыдущему сгенерированному значению. Проблема заключается в том, что каждое отдельное значение ДОЛЖНО быть сгенерировано на месте, когда это необходимо, поэтому мы не храним никаких данных. У меня есть решение с использованием рекурсии, но проблема в том, что если я хочу сгенерировать сотое значение, ему придется рекурсивно go просмотреть, сгенерировать и проверить все предыдущие значения, что, как вы можете себе представить, ужасно. Проблема усложняется еще и тем, что, если я генерирую сотое значение, я точно не знаю, точно ли 99-е значение. Возможно, 99-е значение меньше, чем 98-е значение, поэтому 99-е значение должно выполнить эту проверку - поэтому при генерации 100-го значения мы должны проверять не только 99-е значение, но и, возможно, 98-е значение, т. Е. c ... Есть ли способ решить эту проблему более красноречиво, не создавая и не сохраняя все данные заранее? Спасибо!

Answer 1

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

Просто сгенерировать случайное смещение из предыдущего значения; например:

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

Проблема, о которой вам нужно беспокоиться (независимо от того, как вы это делаете) - это исчерпание - что происходит, когда предыдущее значение было максимально возможным (например, INT_MAX, если вы используете int). Используете ли вы постоянно одно и то же максимально возможное значение без какой-либо случайности (чтобы избежать меньшего значения), или ...?

Answer 2

Вы на самом деле должны хранить только одно значение, а не все из них. Доказательством служит индукция:

• Если вы генерируете значение, и это самый первый раз, это значение будет тривиально больше или равно всем предыдущим
• Если вы знаете ранее сгенерированное значение v , который по индукции больше или равен всем предыдущим значениям, тогда вам просто нужно сгенерировать значение, большее v , чтобы оно было больше или равно всем предыдущим

Вы также можете просто сгенерировать 100 значений и затем отсортировать их.