2012-04-03 06:29:03Morris
[機率][問題] 檢驗策略？
假設某疾病 A 的檢驗費很貴，但得到 A 的機率是 0.01 (意思是 100人裡有 1 人會得到)，
現在有 10,000 人要做檢驗，每個人都會抽血，請使用策略讓檢驗的次數盡可能減少。
解說：
策略1：
每個人都做的話，基本的次數是 10,000 次，接著我們使用一種策略，
若每 10 個人分成一組，則會有 1000 組，讓 10 個人的血混合作一次檢驗(假設不會有問題)，
若該組有檢驗出來的話，那組每個人在做一次。
因此，
E[x] = 1000 * (1 + 10*(1-0.01^10)) ≒1956.179250
策略2：延伸策略1
分成 k 個人後，該組在持續切下去！
程式碼實踐：
In Strategy 1 :
E[(n,p)] = 1956.179250, every 10 people together.
In Strategy 2 :
E[(n,p)] = 882.240893
In 10000 people, Every 36 people together, then
In 36 people, Every 6 people together, then
In 6 people, Every 2 people together, then
End
import java.math.BigDecimal;
public class Bonus2 {
private double p;
private BigDecimal[] expect = new BigDecimal[10001];
private int[] choose = new int[10001];
private int n;
public Bonus2(double p, int n) {
this.p = p;
this.n = n;
for(int i = 0; i <= 10000; i++) {
expect[i] = new BigDecimal(i);
choose[i] = i;
}
strategyBuild1(n);
}
public void strategyBuild1(int n) {
BigDecimal A, B, C;
for(int i = 1; i <= Math.sqrt(n); i++) {
A = BigDecimal.valueOf((int)(n/i));
B = BigDecimal.valueOf(1).add(BigDecimal.valueOf(i).multiply(BigDecimal.valueOf(1).subtract(BigDecimal.valueOf(1-p).pow(i))));
A = A.multiply(B);
int another = n - n/i*i;
if(another != 0) {
B = BigDecimal.valueOf(1).add(BigDecimal.valueOf(another).multiply(BigDecimal.valueOf(1).subtract(BigDecimal.valueOf(p).pow(another))));
A = A.add(B);
}
if(expect[n].compareTo(A) == 1) {
expect[n] = A;
choose[n] = i;
}
}
System.out.printf("In Strategy 1 : \n");
System.out.printf("E[(n,p)] = %.6f, every %d people together.\n", expect[n].doubleValue(), choose[n]);
}
public void strategyBuild2() {
BigDecimal A, B, C;
int i, j;
for(i = 1; i <= n; i++) {
for(j = 1; j <= Math.sqrt(i); j++) {
A = BigDecimal.valueOf((int)(i/j));
B = BigDecimal.valueOf(1).add(expect[j].multiply(BigDecimal.valueOf(1).subtract(BigDecimal.valueOf(1-p).pow(j))));
A = A.multiply(B);
int another = i - i/j*j;
if(another != 0) {
B = BigDecimal.valueOf(1).add(expect[another].multiply(BigDecimal.valueOf(1).subtract(BigDecimal.valueOf(p).pow(another))));
A = A.add(B);
}
if(expect[i].compareTo(A) == 1) {
expect[i] = A;
choose[i] = j;
}
}
}
System.out.printf("In Strategy 2 : \n");
System.out.printf("E[(n,p)] = %.6f\n", expect[n].doubleValue());
int now = choose[n], before = n;
while(now != before) {
System.out.printf("In %d people, Every %d people together, then\n", before, now);
before = now;
now = choose[now];
}
System.out.printf("End\n");
}
public static void main(String[] args) {
Bonus2 test = new Bonus2(0.01, 10000);
test.strategyBuild2();
}
}
現在有 10,000 人要做檢驗，每個人都會抽血，請使用策略讓檢驗的次數盡可能減少。
解說：
策略1：
每個人都做的話，基本的次數是 10,000 次，接著我們使用一種策略，
若每 10 個人分成一組，則會有 1000 組，讓 10 個人的血混合作一次檢驗(假設不會有問題)，
若該組有檢驗出來的話，那組每個人在做一次。
因此，
E[x] = 1000 * (1 + 10*(1-0.01^10)) ≒1956.179250
策略2：延伸策略1
分成 k 個人後，該組在持續切下去！
程式碼實踐：
In Strategy 1 :
E[(n,p)] = 1956.179250, every 10 people together.
In Strategy 2 :
E[(n,p)] = 882.240893
In 10000 people, Every 36 people together, then
In 36 people, Every 6 people together, then
In 6 people, Every 2 people together, then
End
import java.math.BigDecimal;
public class Bonus2 {
private double p;
private BigDecimal[] expect = new BigDecimal[10001];
private int[] choose = new int[10001];
private int n;
public Bonus2(double p, int n) {
this.p = p;
this.n = n;
for(int i = 0; i <= 10000; i++) {
expect[i] = new BigDecimal(i);
choose[i] = i;
}
strategyBuild1(n);
}
public void strategyBuild1(int n) {
BigDecimal A, B, C;
for(int i = 1; i <= Math.sqrt(n); i++) {
A = BigDecimal.valueOf((int)(n/i));
B = BigDecimal.valueOf(1).add(BigDecimal.valueOf(i).multiply(BigDecimal.valueOf(1).subtract(BigDecimal.valueOf(1-p).pow(i))));
A = A.multiply(B);
int another = n - n/i*i;
if(another != 0) {
B = BigDecimal.valueOf(1).add(BigDecimal.valueOf(another).multiply(BigDecimal.valueOf(1).subtract(BigDecimal.valueOf(p).pow(another))));
A = A.add(B);
}
if(expect[n].compareTo(A) == 1) {
expect[n] = A;
choose[n] = i;
}
}
System.out.printf("In Strategy 1 : \n");
System.out.printf("E[(n,p)] = %.6f, every %d people together.\n", expect[n].doubleValue(), choose[n]);
}
public void strategyBuild2() {
BigDecimal A, B, C;
int i, j;
for(i = 1; i <= n; i++) {
for(j = 1; j <= Math.sqrt(i); j++) {
A = BigDecimal.valueOf((int)(i/j));
B = BigDecimal.valueOf(1).add(expect[j].multiply(BigDecimal.valueOf(1).subtract(BigDecimal.valueOf(1-p).pow(j))));
A = A.multiply(B);
int another = i - i/j*j;
if(another != 0) {
B = BigDecimal.valueOf(1).add(expect[another].multiply(BigDecimal.valueOf(1).subtract(BigDecimal.valueOf(p).pow(another))));
A = A.add(B);
}
if(expect[i].compareTo(A) == 1) {
expect[i] = A;
choose[i] = j;
}
}
}
System.out.printf("In Strategy 2 : \n");
System.out.printf("E[(n,p)] = %.6f\n", expect[n].doubleValue());
int now = choose[n], before = n;
while(now != before) {
System.out.printf("In %d people, Every %d people together, then\n", before, now);
before = now;
now = choose[now];
}
System.out.printf("End\n");
}
public static void main(String[] args) {
Bonus2 test = new Bonus2(0.01, 10000);
test.strategyBuild2();
}
}