Lanciare gatti dalle finestre

Question

Immagina di essere in un alto edificio con un gatto. Il gatto può sopravvivere una caduta da una finestra bassa storia, ma morirà se gettato da un piano alto. Come si può capire il calo più lungo che il gatto può sopravvivere, utilizzando il minor numero di tentativi?

Ovviamente, se avete solo un gatto, allora si può cercare solo in modo lineare. In primo luogo gettare il gatto dal primo piano. Se sopravvive, gettarlo dal secondo. Alla fine, dopo essere stato gettato dal piano F, il gatto morirà. È quindi sa che piano f-1 è stato il piano di sicurezza massima.

Ma cosa succede se si dispone di più di un gatto? È ora possibile provare una sorta di ricerca logaritmica. Diciamo che la build ha 100 piani e si dispone di due gatti identici. Se si lancia il primo gatto fuori al 50 ° piano e muore, allora dovete solo cercare 50 piani in modo lineare. Si può fare ancora meglio se si sceglie un piano inferiore per il primo tentativo. Diciamo che si sceglie di affrontare il problema 20 piani alla volta e che il primo piano è fatale # 50. In tal caso, il primo gatto sopravviverà voli da piani 20 e 40 prima di morire dal pavimento 60. Basta controlla piani 41 attraverso 49 singolarmente. Ciò significa un totale di 12 tentativi, che è molto meglio che il 50 si sarebbe avuto bisogno si è tentato di utilizzare l'eliminazione binario.

In generale, qual è la strategia migliore ed è nel caso peggiore la complessità per un edificio n piani con 2 gatti? Che dire per n pavimenti e m gatti?

Si supponga che tutti i gatti sono equivalenti: saranno tutti di sopravvivere o morire da una caduta da una data finestra. Inoltre, ogni tentativo è indipendente:. Se un gatto sopravvive una caduta, è completamente illeso

Non si tratta di compiti a casa, anche se forse ho risolto per l'assegnazione della scuola una volta. E 'solo un problema bizzarro che mi è venuta in mente oggi e non mi ricordo la soluzione. I punti di bonus se qualcuno conosce il nome di questo problema o dell'algoritmo soluzione.

Answer 1

Si può facilmente scrivere un po 'di DP (programmazione dinamica) per il caso generale di n pavimenti e m gatti.

La formula principale, a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..n, dovrebbe essere auto-esplicativo:

• Se il primo gatto è gettato dal k-esimo piano e muore, ora abbiamo piani k - 1 da controllare (tutti al di sotto k) e gatti (m - 1 a[k - 1][m - 1]).
• Se sopravvive gatto, ci sei piani n - k sinistra (tutti i piani sopra k) e ancora gatti m.
• Il caso peggiore di due dovrebbe essere scelto, quindi max.
• + 1 deriva dal fatto che abbiamo appena usato un tentativo (indipendentemente dal fatto che il gatto è sopravvissuto o no).
• Cerchiamo ogni possibile piano per trovare il miglior risultato, quindi min(f(k)) : for k in 1..n.

E 'd'accordo con esito Google da Gaurav Saxena ' s per (100, 2).

int n = 100; // number of floors
int m = 20; // number of cats
int INFINITY = 1000000;

int[][] a = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++i) {
    // no cats - no game
    a[i][0] = INFINITY;
}

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        // i floors, j cats
        a[i][j] = INFINITY;

        for (int k = 1; k <= i; ++k) {
            // try throw first cat from k-th floor
            int result = Math.max(a[k - 1][j - 1], a[i - k][j]) + 1;
            a[i][j] = Math.min(a[i][j], result);
        }
    }
}

System.out.println(a[n][m]);

Per la ricerca di strategia (come gettare primo gatto), se si salva migliore k in un altro array.

C'è anche una soluzione più veloce, non coinvolge O (n ^ 3) calcoli, ma io sono già un po 'assonnato.

modifica
Oh sì, mi ricordo dove ho visto questo problema prima .

Answer 2

un recente episodio di Radiolab (di "Falling") , un gatto raggiunge velocità terminale dal 9 ° piano. Dopo di che, si rilassa ed è meno probabilità di essere ferito. Ci sono gatti completamente illesi dopo una caduta da sopra il 30 °. I pavimenti sono più rischiose 5 al 9.

Answer 3

  

Immagina di essere in un alto edificio con un gatto. Il gatto può sopravvivere una caduta da una finestra bassa storia, ma morirà se gettato da un piano alto. Come si può capire il calo più lungo che il gatto può sopravvivere, utilizzando il minor numero di tentativi?

La strategia migliore per risolvere questo problema sta indagando, utilizzando la legge della fisica, della probabilità di vostre ipotesi vero essere, in primo luogo.

Se hai fatto, ti renderesti conto che le probabilità del gatto di sopravvivenza effettivamente aumentare maggiore è la distanza terra è. Naturalmente, supponendo che si lancia da un edificio sempre più in alto, come ad esempio le torri Petronas, e non una montagna sempre più in alto, come il monte Everest.

Modifica
In realtà, si vedrebbe una distribuzione cammello incompiuta.
In primo luogo, la probabilità che il gatto che muore è bassa (bassissima quota), poi diventa più alta (bassa quota), poi di nuovo inferiore (quota più elevata), e poi ancora più alto (molto alta quota).

Il grafico per la probabilità di morire gatto in funzione di altitudine al di sopra sguardi terra come questo:
(Finitura a 3, perché la distribuzione di cammello non finito)

Aggiornamento:
velocità terminale di un gatto è di 100 km / h (60 mph) [= 27.7m / s = 25.4 yards / s].
velocità terminale umana è di 210 km / h (130 mph). [= 75m / s = 68.58 yarde / s]

fonte velocità terminale:
http://en.wikipedia.org/wiki/Cat_righting_reflex
Credits:
Goooooogle
Ho bisogno di verificare in seguito:
http://en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov/WWW/K -12 / aereo / termv.html

Answer 4

ho letto questo problema in Steven Skiena di Algoritmo design manuale (esercizio 8.15). E 'seguito un capitolo sulla programmazione dinamica, ma non è necessario conoscere la programmazione dinamica per dimostrare limiti precisi sulla strategia . In primo luogo la dichiarazione del problema, allora la soluzione qui di seguito.

  pausa

uova quando è sceso da grande altezza sufficiente. Dato un edificio n piani, ci deve essere un piano f tale che le uova è sceso dal pavimento f pausa, ma le uova scesa dal piano F-1 sopravvivere. (In caso di rottura delle uova da qualsiasi piano, diremo f = 1. Se le sopravvive uovo da qualsiasi piano, diremo f = n + 1).

     

Si cercano di trovare il pavimento critica f. L'unica operazione che è possibile eseguire è far cadere un uovo fuori qualche piano e vedere cosa succede. Si inizia con le uova k, e cercate di eliminare le uova il minor numero di volte possibile. Uova rotte non possono essere riutilizzati (uova intatte can). Sia E (k, n) è il numero minimo di escrementi d'uovo che sarà sempre sufficiente.

     

  
1. Mostra che E (1, n) = n.
  
2. Mostra che E(k,n) = Θ(n**(1/k)).
  
3. Trova una ricorrenza per E (k, n). Qual è il tempo di esecuzione del programma dinamico di trovare E (k, n)?
  

---

Solo 1 uovo

La caduta del uovo da ogni piano a partire dal primo piano si trova la critica (at-peggiore) n operazioni.

Non c'è più veloce algoritmo. In qualsiasi momento in qualsiasi algoritmo, sia g il piano più alto da cui l'uovo è stato visto non rompere. Il piano di prova g algoritmo deve + 1 prima di qualsiasi piano superiore h> g + 1, altrimenti se l'uovo dovesse rompere dal pavimento h, potrebbe non distingue tra f = g + 1 e f = h.

2 uova

Per prima, consideriamo il caso k = 2 uova, quando n = r ** 2 è un quadrato perfetto. Ecco una strategia che prende O (sqrt (n)). Inizia facendo cadere il primo uovo in incrementi di pavimenti r. Quando i primi uovo si rompe, dicono a ar piano, sappiamo che il piano critico f deve essere (a-1)r < f <= ar. Abbiamo poi cadere il secondo uovo da ogni piano a partire da (a-1)r. Quando il secondo uovo si rompe, abbiamo trovato il pavimento critica. Abbiamo abbassato ogni uovo al massimo tempo r, quindi questo algoritmo prende in-peggiore 2r operazioni, che è T (sqrt (n)).

Quando n non è un quadrato perfetto, prendere r = ceil(sqrt(n)) ∈ Θ(sqrt(n)). L'algoritmo rimane T (sqrt (n)).

La prova che qualsiasi algoritmo richiede almeno sqrt (n). Supponiamo che ci sia un algoritmo più veloce. Prendere in considerazione la sequenza di piani da cui cade il primo uovo (a patto che non si rompe). Poiché diminuisce meno sqrt (n), ci deve essere un intervallo di almeno n / sqrt (n) che è sqrt (n). Quando f è in questo intervallo, l'algoritmo dovrà indagare con il secondo uovo, e che deve essere fatto piano per piano ricordando il caso 1-uovo. CONTRADDIZIONE.

k uova

L'algoritmo presentato per 2 uova può essere facilmente esteso alle uova k. Eliminare ogni uovo con intervalli costanti, che dovrebbero essere presi come i poteri della radice k-esima di n. Ad esempio, per n = 1000 e k = 3, intervalli di 100 piani verificare con il primo uovo, 10 con il secondo uovo, e 1 con l'ultimo uovo.

Allo stesso modo, siamo in grado di dimostrare che nessun algoritmo è più veloce Θ(n**(1/k)) per induzione dal k = 2 prova.

soluzione esatta

dedurre la ricorrenza ottimizzando dove cadere il primo uovo (piano g), presumendo sappiamo soluzioni ottimali per i parametri più piccoli. In caso di rottura delle uova, abbiamo il G-1 piani più in basso da esplorare con k-1 uova. Se i sopravvive a base di uova, abbiamo n-g piani sopra di esplorare con le uova k. Il diavolo sceglie il peggiore per noi. Così per k> 1 la ricorrenza

E(k,n) = min(max(E(k,n-g), E(k-1,g))) minimised over g in 1..n

Answer 5

non questo assume che si sta utilizzando "lo stesso gatto"?

È possibile avvicinarsi matematicamente, ma questa è la cosa bella di matematica ... con i presupposti giusti, 0 può essere uguale a 1 (per grandi valori di 0).

Da un punto di vista pratico, è possibile ottenere 'Gatti simili", ma non si può ottenere 'lo stesso gatto'.

Si potrebbe cercare di determinare la risposta empiricamente, ma vorrei pensare che ci sarebbe stato abbastanza differenze statistiche che la risposta sarebbe statisticamente insignificante.

Si potrebbe provare a utilizzare "lo stesso gatto", ma che non avrebbe funzionato, come, dopo la prima goccia, non è più lo stesso gatto. (Analogamente a, onecan mai passo nello stesso fiume due volte)

In alternativa, si potrebbe aggregare la salute del gatto, il campionamento a intervalli estremamente stretti, e trovare le altezze per cui il gatto è "per lo più in vita" (al contrario di "la maggior parte morti" da "La storia fantastica"). I gatti sopravvivono in media (fino all'ultimo intervallo).

credo di aver deviato dalla intento originale, ma se si sta andando via empirica, io voto per l'avvio di più in alto possibile e continuare a cadere gatti come l'altezza diminuisce fino a quando non statisticamente sopravvivere. E poi ri-test a sopravvivere gatti per essere sicuri.

Answer 6

ho preso un metodo leggermente diverso per produrre una soluzione.

Ho iniziato lavorando il pavimento massima che potrebbe essere coperto utilizzando x gatti e y congetture utilizzando il metodo seguente.

Inizia con 1 piano e continuare ad aumentare il numero di tentativi tenendo traccia di piani controllati, che immagino sono stati controllati e quanti gatti sono stati rimanente per ogni piano.
Ripetere questa operazione fino a y volte.

Questo molto il codice inefficiente per calcolare la risposta data, ma comunque utile per il piccolo numero di gatti / piani.

codice Python:

def next_step(x, guess):
  next_x = []
  for y in x:
    if y[0] == guess:
      if y[1] != 1:
        next_x.append((guess+1, y[1] - 1))
    next_x.append(y)
    if y[0] == guess:
      next_x.append((guess+1, y[1]))
  return next_x

x = [(1, TOTAL_NUM_CATS)]
current_floor = 1
while len(x) <= TOTAL_NUM_FLOORS:
  x = next_step(x, current_floor)
  current_floor += 1
  print len(x)

Per 2 gatti i piani massimo che possono essere identificati in x congetture è:
1, 3, 6, 10, 15, 21, 28 ...

Per 3 gatti:
1, 3, 7, 14, 25, 41, 63 ...

Per 4 gatti:
1, 3, 7, 15, 30, 56, 98 ...

Dopo approfondite ricerche (che coinvolge per lo più numeri di battitura sequenze in OEIS ) ho notato che i pavimenti massimi per x segue un pattern di combinazione a tratti.

Per 2 gatti:
n <2: 2 ^ n - 1
n> = 2: C (n, 1) + C (n, 2)

Per 3 gatti:
n <3: 2 ^ n - 1
n> = 3: C (n, 1) + C (n, 2) + C (n, 3)

Per 4 gatti:
n <4: 2 ^ n - 1
n> = 4: C (n, 1) + C (n, 2) + C (n, 3) + C (n, 4)

Da qui ho preso l'approccio semplice di semplici incrementare n fino a quando mi passa il numero di piani.

codice Python:

def find_smallest(floors, eggs):
  maximum_floors = 0
  n = 0
  while maximum_floors < floors:
    maximum_floors = 0
    n += 1
    if n < eggs:
      maximum_floors = 2**n - 1
    else:
      count = 0
      for x in xrange(1, eggs+1):
        maximum_floors += combination(n, x)
  print n

In questo modo la soluzione corretta per (100, 2) = 14.
Per tutti coloro che desiderano controllare qualcosa di meno banale, dà (1 000 000, 5) = 43.

Questo viene eseguito in O (n), dove n è la risposta al problema (i più gatti 'il migliore).
Tuttavia sono sicuro che un qualcuno con un più alto livello della matematica potrebbe semplificare le formule per calcolare a tratti in O (1).

Answer 7

O(m*(n^(1/m))) algorithm.

Let 'x' be the maximum number of attempts needed.  

m = 1 => linear => x=n

m = 2:  
Let the floors be split into 'k' partitions. The first cat is thrown at the end of each partition (max 'k' times). 
When it dies, the second cat is used to go up from the beginning of this partition.   
x = k + n/k.   
Minimize x by diff wrt k and setting = 0, to get k = n^(1/2) and x = 2 * n^(1/2).

m = 3:  
x = k + 2*(y^(1/2)), where y = n/k  
diff wrt x and set = 0, to get k = n^(1/3) and x = 3 * n^(1/3)

for general m:  
x = m * n^(1/m). 

Answer 8

Non riesco a leggere il blogspot Google su questo (grazie a opere blogwall), ma non credo che una scala di ricerca binaria stile sarebbe meglio. Il motivo è che una ricerca binaria si basa sul concetto che la risposta che state cercando ha la stessa probabilità di essere in qualsiasi indice indice nella lista. Tuttavia, in questo caso, il che non è vero. In questo caso la risposta avrà una maggiore probabilità di essere più vicino a una delle estremità del campo rispetto agli altri. Non ho idea di come fattore che nella ricerca, ma è un pensiero interessante.

Answer 9

tutto questo parlare pazzo di cats..and è solo una supposizione il problema numero con tentativi minimi (numero dei gatti). non ci dovrebbe essere una necessità di artificialmente (e correttamente) definiscono infinito come parte della soluzione sia. la variabile avrebbe dovuto essere chiamato upper bound o max-prova o qualcosa del genere. la definizione del problema (la cosa gatto) ha alcuni problemi seri, però, con persone che rispondono al potenziale crudeltà sugli animali e anche le molteplici sfaccettature di un tale problema posto nella vita reale, per esempio air-trascinamento, gravità è l'accelerazione, e altri tali parametri reali del problema. così forse avrebbe dovuto essere chiesto in un modo completamente diverso.