#file #stream
#файл #поток
Вопрос:
этот вопрос был задан в интервью..
предположим, что ваш компьютер считывает символы один за другим из потока (вы не знаете длину потока до окончания). Обратите внимание, что у вас есть только один символ места для хранения (поэтому вы не можете сохранить прочитанные символы во что-то вроде сильного). Когда вы закончите чтение, вы должны вернуть символ из потока с равной вероятностью.
как подойти к этой проблеме?? есть идеи??
есть какой-нибудь способ сделать это??
Ответ №1:
Это один из тех приемов, которые вы либо знаете, либо нет:
Берем первый символ, с вероятностью 1/2 берем следующий, в противном случае сохраняем первый, с вероятностью 1/3 берем следующий, в противном случае сохраняем и т.д.
Это работает, потому что каждый раз, когда вы выбираете n-й символ с вероятностью 1 / n или сохраняете предыдущий (с вероятностью 1 / (n-1), чтобы быть там) с вероятностью (1-n) / n, и 1-n отменяется.
Комментарии:
1. просто для придирчивости: где вы храните
n? 🙂2. @Andre Holzner вы можете быть еще более придирчивым и спросить, как вы генерируете случайное число, не используя никакого места в памяти, или как вы получаете доступ к потоку, не требуя места в памяти для ссылки или указателя на объект stream.
3. @Andre Holzner если серьезно, то помимо памяти для
charи вызовов функций потока и генератора случайных чисел, этот метод требует хранения одногоdoubleсимвола, представляющего вероятность получения или сохранения. Он может быть обновлен как p = 1 /((1/p) 1).