ghira ha scritto:Per il tuo metodo ottengo un tempo medio di 23310.0016686485 secondi per trovare 70 diamanti.
Per il mio ottengo un tempo medio di 19869.2388921697 secondi.
Per il tuo ho usato una catena di Markov.
Gli stati sono $(n,i,j)$ dove $n$ è il numero del diamante che stiamo cercando, $i$ è la probabilità (in $n$-esimi) di trovare il prossimo diamante se facciamo uno scavo di 48 secondi adesso, e $j$ è la posizione nel ciclo degli scavi. $j$ può essere 0, 1 o 2. Quando è 0 facciamo uno scavo da 48 secondi.
Cominciamo in stato $(1,1,0)$. Vogliamo sapere quanto costa mediamente arrivare in uno degli stati $(71,1,0)$, $(71,1,1)$ o $(71,1,2)$. I costi partendo da questi tre stati sono 0.
Per gli altri stati:
$c(n,i,j)=48+c(n+1,1,j+1 mod 3)$ se $i=n$ e $j=0$
$c(n,i,j)=48+\frac{i}{n}c(n+1,1,j+1 mod 3)+\frac{n-i}{i}c(n,i+1,j+1 mod 3)$ se $j=0$ e $i<n$
$c(n,i,j)=20+c(n,i,j+1 mod 3)$ se $j=1$ o $2$ e $i=n$
$c(n,i,j)=20+c(n,i+1,j+1 mod 3)$ se $j=1$ o $2$ e $i<n$.
Puoi confermare che tutto questo è quello che intendi?
Il mio programma per calcolare il costo $c(1,1,0)$ è:
- Codice:
#!/usr/bin/perl
#ciclo 48,20,20
#stato iniziale 1,1,0
$c[71][1][0]=0;
$c[71][1][1]=0;
$c[71][1][2]=0;
#prossimo diamante, prob in n-esimi, ciclo, old/new
#esattamente tot iterazioni - tutti i fallimenti possibili
while (1) {
for ($n=70;$n>0;$n--) {
#print $n."\n";
for ($i=$n;$i>0;$i--) {
#print $i."\n";
for $j (0..2) {
#print $j."\n";
$j2=($j+1)%3;
if ($j==0) {
if ($i==$n) {
$c[$n][$i][$j]=48+$c[$n+1][1][$j2];
} else {
$c[$n][$i][$j]=48+$i/$n*$c[$n+1][1][$j2]+($n-$i)/$n*$c[$n][$i+1][$j2];
}
} else {
if ($i<$n) {
$i2=$i+1;
} else {
$i2=$i;
}
$c[$n][$i][$j]=20+$c[$n][$i2][$j2];
}
#print "$n $i $j $c[$n][$i][$j]\n";
}
}
}
print $c[1][1][0]."\n";
}
e dice
23310.0016686485
ma il programma potrebbe non essere perfetto.
Almeno il metodo che sto provando ad usare è quello che descrivi tu? Billy fa scavi inutili da 20 secondi quando potrebbe trovare il diamante con probabilità 1 facendo uno scavo da 48 secondi?
Per il mio metodo eseguo il mio programma (visto qualche messaggio fa) per tutti i valori di $n$ da 1 a 70:
(modificato per stampare solo il costo partendo dallo stato $1$ per ogni diamante).
- Codice:
#!/usr/bin/perl
for (1..70) {
system "perl diamanti.p $_";
}
e sommo i risultati.
- Codice:
#!/usr/bin/perl
while (<>) {
chomp;
$t+=$_;
}
print "$t\n";
- Codice:
~/matematicamente$ ./diamantiloop.p | ./summer.p
19869.2388921697
Se vuoi che Billy faccia altre cose puoi modificare il programma o scriverne uno migliore ovviamente. La mia soluzione dovrebbe essere quella col tempo medio più basso.
non so se lo hai incluso nell'algoritmo, ma la probabilità crescente in questione si riferisce alla probabilità che il diamante appaia, poi c'è la parte del raccoglierlo in cui solo lo scavo da 48 secondi può farlo. Se il diamante appare ma non viene raccolto ( ad esempio il diamante appare mentre billy esegue uno scavo da 20 sec) il diamante poi non rimane lì allo scavo successivo ma scompare rimanendo però sempre soggetto a quella percentuale
