对最近播放列表进行随机播放的问题
Published:
有这么一种音乐播放器，它有一个最近播放列表，其中总共能保存 n 首歌。当选择某一首歌曲播放时，播放器将删除最近播放列表中第 n 首歌，并将第 1 至第 n − 1 首歌向后移一个排位，最后将选择播放的歌曲放入第一个排位，得到新的最近播放列表。注意，同一首歌曲能在最近播放列表中出现多次。
这个音乐播放器还有一种随机播放功能，即对一个有 n 首歌曲的播放列表，它能以每首歌 1/n 的概率抽取其中一首播放。重复的歌曲是单独计算的，即如果一首歌出现了m 次，总共就有 m/n 的概率播放这首歌。
我们的问题是，假设最初最近播放列表中有 n 首不同的歌曲，现在对最近播放列表进行随机播放操作。那么经过多长时间（即多少次播放）之后，最近播放列表中会仅剩下一首歌？每一首歌被剩下的概率又是多少？如果初始情况不是每首歌只出现一次，又会怎样呢？