수학은 부족하므로
태그 : 시뮬레이션, 브루트포스, 사이클 판정 로 구현해보자!
생각보다 막 ㅗㅜㅑ한 결과는 아닌 것 같다. 대강 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);
}
}
'ETC > 잡글' 카테고리의 다른 글
[잡글] 꼬맨틀 브루트포스 매크로 (0) | 2022.12.14 |
---|---|
블로그 개설 1년2개월, 10만 뷰! (2) | 2022.12.07 |
생일! (4) | 2022.10.19 |
백준 스트릭 365일 달성! (0) | 2022.09.25 |
2020~2022 엔딩 본 게임들 한줄평 (2) | 2022.09.05 |
댓글