云南开放大学算法设计与分析第九章 随机算法

习题

• 设有一个文件含有x个记录。
• 试设计一个算法随机抽取该文件中y个记录。
• 如果事先不知道文件中记录个数，应如何随机抽取其中的y个记录

2. 2. 试设计一个算法随机地产生范围在1~n中的m个随机整数，且要求这m个随机整数互不相同。

3．采用数组模拟有序链表的数据结构，设计一个舍伍德型排序算法，使得算法最坏情况下的平均计算时间为O(n^3/2)。

4．设p是一个奇素数，1<= x <= p-1，如果存在一个整数y，1<= y <= p-1，使得，则称y是x的模p平方根。例如63是55的模103平方根。试设计一个求整数x的模p平方根的拉斯维加斯算法。