[잡글] 평균적으로 몇잔씩 사라질까요?

 

수학은 부족하므로

 

태그 : 시뮬레이션, 브루트포스, 사이클 판정 로 구현해보자!

 

 

생각보다 막 ㅗㅜㅑ한 결과는 아닌 것 같다. 대강 0.5잔에 수렴하는듯. 다만 검증은 안해봤다! 아 그리고 술 마시고 싶은 사람은 자기 자신을 고를 경우 바로 사이클이 생기므로 마실 수 있다.

...

 

 

import java.io.IOException;
import java.util.HashSet;
import java.util.Random;
public class Main {
    private static int cnt(int[] to, int dst) {
        int cnt = 0;
        int tmp = dst;
        do {
            tmp = to[tmp];
            cnt++;
        } while (tmp!=dst);
        return cnt;
    }
    private static int rec(HashSet<Integer> chk, boolean[] v, int[] to, int cur) {
        if (chk.contains(to[cur]))
            return cnt(to, cur);
        chk.add(cur);
        v[cur] = true;
        rec(chk, v, to, to[cur]);
        return 0;
    }
    private static final int MIN_N = 1;
    private static final int MAX_N = 100;
    private static final int TASE_CASE = 10000;
    private static final int ㅗㅜㅑ퍼센트 = 30;
    public static void main(String[] args) throws IOException {
        Random rand = new Random(System.currentTimeMillis());
        StringBuilder sb = new StringBuilder();
        for (int n = MIN_N; n <= MAX_N; n++) {
            int tc = TASE_CASE;
            long sum = 0;
            while (tc-->0) {
                int[] to = new int[n];
                for (int i = 0; i < n; i++) {
                    to[i] = rand.nextInt(n);
                }
                boolean[] v = new boolean[n];
                for (int i = 0; i < n; i++) {
                    if (v[i]) continue;
                    HashSet<Integer> chk = new HashSet<>();
                    chk.add(i);
                    v[i] = true;
                    sum += rec(chk, v, to, i);
                }
            }
            double avg = 1d*sum/TASE_CASE;
            sb.append(String.format("%d명일 때 평균 %.2f잔이 사라짐!! %s\n", n, avg, avg/n*100>=ㅗㅜㅑ퍼센트 ? "ㅗㅜㅑ" : ""));
        }
        System.out.println(sb);
    }
}