출처: http://www.gpgstudy.com/gpgiki/Shuffling

시작
  선언, 할당 flag[11] //1...10의 각 수가 쓰였는지를 판단하기 위한 플래그
                      //(false로 초기화된다고 가정)
  선언, 할당 N[10]

  루프 ( 각각의 N[i]에 대해 ) {

    R = 난수(1~10)

    루프 (flag[R]이 true가 아닐 때까지)
       {   R = 난수(1~10) }

    N[i] = R
    flag[R] = true
  }


일반적으로 이렇게 생각하기 쉬운데..저 로직은 같은난수가 반복적으로 나올때 몇번의 루프를 비효율적으로 돌수있다는 단점이있다..
----------------------------------------------

조금 더 간단한 방법.

TAOCP에서 소개된 방법으로 알고있습니다.

시작

  선언, 할당  N[10]

  루프 i=0에서 9
  {   N[i] = i+1 // N[0]=1, N[1]=2,....N[9]=10  }

  루프 (i=0 에서 9)   {
    대상 = 난수(i~9)
    교환 ( N[i], N[대상])
  }


실행시간은 바꾸고자 하는 컨테이너의 크기에 비례하고, 적어도 각각의 요소를 한번씩은 봐야하므로 이것이 제일 빠른 방법입니다.



'Programing > 알고리즘' 카테고리의 다른 글

표준 rand()함수보다 유용한 랜덤 생성 알고리즘 – MT, WELL  (0) 2012.03.07
100개 따조 모으기  (0) 2012.01.16
중복하지 않는 난수생성..  (0) 2011.12.09
Crypt Kicker  (0) 2011.12.07
Jolly Jumpers  (0) 2011.12.07
DisplayLCD  (0) 2011.12.07
Posted by 패스맨

댓글을 달아 주세요