문제 풀이 노트 (3) - 난수 선택

문제: 0, 1, 2... n - 1 에서 무 작위 로 m 개 수 를 선택 하고 각 수 에서 선택 할 확률 이 같 으 며 중복 이 허용 되 지 않 습 니 다.선택 한 수 를 순서대로 출력 합 니 다.예 를 들 어 0, 1, 2, 3, 4, 5 중에서 무 작위 로 3 개의 수 를 선택 하고 1, 4, 5 를 선택 하면 수출 순서 도 1, 4, 5 가 되 어야 한다.아래 실현 에서 사용 하 는 랜 덤 함 수 는 모두 C 의 라 이브 러 리 함수 입 니 다. 이 함수 가 발생 하 는 랜 덤 수의 범 위 는 한정 되 어 있 습 니 다. [0, 32767] 더 큰 랜 덤 수 를 만 들 려 면 랜 덤 함 수 를 따로 실현 하여 rand () 를 교체 해 야 합 니 다.예 를 들 어 아래 의 이 함수.

int bigrand()
{
	return RAND_MAX*rand()+rand();
}

《 프로 그래 밍 주옥 》 상의 해법 1.

void random1(int n,int m)
{
	for(int i=0;i<n;i++)
	{
		if(rand()%(n-i)<m)
		{
			cout<<i<<' ';
			m--;
		}
	}
}

        각 수가 선 택 될 확률 이 같다 는 것 을 간단하게 설명 하 세 요.계산 공식 은 p (i) = (m - (m / n) * i) / (n - i) = m / n, 그 중 m - (m / n) * i 는 나머지 선택 가능 한 개수 입 니 다.
        n 이 크 면 m 가 상대 적 으로 작 고 해법 1 의 시간 복잡 도가 크다.
《 프로 그래 밍 주옥 》 상의 해법 2.

void random2(int n,int m)
{
	set<int> s;
	while(s.size()<m)
		s.insert(rand()%n);

	set<int>::iterator iter=s.begin();
	for(;iter!=s.end();iter++)
		cout<<*iter<<' ';
}

        set 의 밑 층 은 빨간색 과 검은색 나무 로 하나의 요 소 를 삽입 하 는 시간 복잡 도 는 O (logn) 이기 때문에 해법 2 의 시간 복잡 도 는 O (m logm) 이다.하지만 set 가 소모 하 는 공간 은 비교적 크다.공간 에 민감 하 다 면 이런 방법 은 적합 하지 않다.
        해법 3 은 방향 을 바 꾸 어 n 개의 배열 요 소 를 흐 트 러 뜨 린 다음 에 앞의 m 개의 요 소 를 정렬 하여 출력 하면 된다.
《 프로 그래 밍 주옥 》 상의 해법 3.

void random3(int n,int m)
{
	int i;
	int *x=new int[n];
	for(i=0;i<n;i++)
		x[i]=i;
	for(i=0;i<m;i++)
	{
		int j=i+rand()%(n-i); //     i   n-1   
		if(i!=j)
		{
			int t=x[i];
			x[i]=x[j];
			x[j]=t;
		}
	}
	sort(&x[0],&x[m]);
	for(i=0;i<m;i++)
	     cout<<x[i]<<' ';
}

       이 알고리즘 은 O (n) 의 공간 과 O (n + mlogm) 의 시간 복잡 도 를 사용 합 니 다. 초기 화 된 시간 을 없 앨 수 있다 면 시간 복잡 도 는 O (mlogm) 로 낮 출 수 있 습 니 다.
       n 이 크 면 m 도 크다.이렇게 해결 할 수 있어.n - m 개 수 를 무 작위 로 생 성하 고 n 의 다른 수 를 출력 합 니 다.
       본인 은 블 로그 글 의 판권 을 가지 고 있 으 니, 전재 할 때 출처 를 표시 해 주 십시오. http://blog.csdn.net/wuzhekai1985