题目：

从大小为n的整数数组A中随机选出m个整数，要求每个元素被选中的概率相同。

思路：

n选m，等概率情况下，每个数被选中的概率为m/n。

方法：

初始化：从A中选择前m个元素作为初始数组；

随机选择：从第m个元素开始，依次遍历数组下标i，并通过随机生成器生成数字k（生成0~n），如果k<m，则将A[i]替换A[k]。

证明：

归纳法：假设数组A大小为n，需要选m个元素，每个元素被选中的概率为m/n。

对于初始化的m个元素而言，其选中的概率自然为m/n；

而对于第n+1个元素，该元素被选中的概率m/(n+1)（根据随机生成器），

而对于此时前m个元素，根据第n+1个元素的选中与否情况：

第n+1个没选中的概率为1-m/(n+1)，则全部留下的可能性为P1：m/n*(1-m/n+1)，

第n+1个被选中的概率为m/(n+1)有一个被替换后留下的可能性为P2：m/n*m/(n+1)*(m-1)/m，

总的留下概率为：P1+P2=m/(n+1)

因此得证。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;void pickM(const vector
         
           &A,int m,vector
          
            &pick){ int n=A.size(); for(int i=0;i
           
            >n>>m){ vector
            
              A(n); for(int i=0;i
             
              >A[i]; vector
              
                pick; pickM(A,m,pick); for(int i=0;i