Lancer des chats hors des fenêtres

Imaginez que vous êtes dans un grand bâtiment avec un chat. Le chat peut survivre à une chute par une fenêtre basse, mais mourra s’il est jeté d’un étage élevé. Comment pouvez-vous déterminer la plus longue chute que le chat peut survivre, en utilisant le moins de tentatives?

De toute évidence, si vous n’avez qu’un seul chat, vous ne pouvez rechercher que linéairement. Jetez d’abord le chat du premier étage. S’il survit, jetez-le du second. Finalement, après avoir été jeté du sol f, le chat mourra. Vous savez alors que le plancher f-1 était le plancher sûr maximal.

Mais si vous avez plus d’un chat? Vous pouvez maintenant essayer une sorte de recherche logarithmique. Disons que la construction a 100 étages et que vous avez deux chats identiques. Si vous jetez le premier chat hors du 50ème étage et que celui-ci meurt, il vous suffit de chercher 50 étages linéairement. Vous pouvez faire encore mieux si vous choisissez un étage inférieur pour votre première tentative. Disons que vous choisissez de vous attaquer au problème 20 étages à la fois et que le premier étage mortel est le numéro 50. Dans ce cas, votre premier chat survivra aux vols des étages 20 et 40 avant de mourir du sol 60. Il vous suffit de vérifier les niveaux 41 à 49 individuellement. C’est un total de 12 tentatives, ce qui est beaucoup mieux que les 50 dont vous auriez besoin si vous aviez essayé d’utiliser l’élimination binary.

En général, quelle est la meilleure stratégie et la pire des situations pour un bâtiment de 2 étages avec n-étages? Qu’en est-il des n étages et des chats?

Supposons que tous les chats sont équivalents: ils survivront ou mourront tous d’une chute d’une fenêtre donnée. De plus, chaque tentative est indépendante: si un chat survit à une chute, il est complètement indemne.

Ce n’est pas un devoir, mais je l’ai peut-être résolu une fois pour une affectation scolaire. C’est juste un problème fantasque qui m’est venu à l’esprit aujourd’hui et je ne me souviens pas de la solution. Des points bonus si quelqu’un connaît le nom de ce problème ou de l’algorithme de la solution.

Vous pouvez facilement écrire un peu de DP (programmation dynamic) pour le cas général des n étages et des chats.

La formule principale, a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..n , devrait être explicite:

  • Si le premier chat est lancé à partir du kième étage et meurt, nous avons maintenant k - 1 étages pour vérifier (tous en dessous de k ) et m - 1 chats ( a[k - 1][m - 1] ).
  • Si le chat survit, il rest n - k étages (tous les étages supérieurs à k ) et toujours les chats.
  • Le pire des deux devrait être choisi, donc max .
  • + 1 provient du fait que nous venons d’utiliser une tentative (peu importe si le chat a survécu ou non).
  • Nous essayons tous les étages possibles pour trouver le meilleur résultat, donc min(f(k)) : for k in 1..n .

Il est en accord avec le résultat Google du lien de Gaurav Saxena pour (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]); 

Vous pouvez facilement trouver une stratégie (comment lancer le premier chat), si vous économisez le mieux dans un autre tableau.

Il y a aussi une solution plus rapide, ne impliquant pas de calculs O (n ^ 3), mais je suis déjà un peu endormi.

modifier
Oh oui, je me souviens où j'ai vu ce problème avant .

Selon un épisode récent de Radiolab (à propos de “Falling”) , un chat atteint sa vitesse finale au 9ème étage. Après cela, il se détend et est moins susceptible d’être blessé. Il y a des chats complètement indemnes après une chute au-dessus du 30ème. Les étages les plus risqués sont du 5 au 9.

Imaginez que vous êtes dans un grand bâtiment avec un chat. Le chat peut survivre à une chute par une fenêtre basse, mais mourra s’il est jeté d’un étage élevé. Comment pouvez-vous déterminer la plus longue chute que le chat peut survivre, en utilisant le moins de tentatives?

La meilleure stratégie pour résoudre ce problème consiste à étudier, en utilisant la loi de la physique, la probabilité que vos hypothèses soient vraies en premier lieu.

Si vous l’aviez fait, vous vous rendriez compte que les chances de survie du chat augmentent d’autant plus que la distance au sol est élevée. Bien sûr, en supposant que vous le lanciez depuis un bâtiment de plus en plus haut, tel que les tours Petronas, et non une montagne de plus en plus haute, comme le mont Everest.

Modifier:
En fait, vous verriez une dissortingbution inachevée de chameaux.
Premièrement, la probabilité que le chat meure est faible (très basse altitude), puis il monte (basse altitude), puis de nouveau plus bas (altitude plus élevée), puis à nouveau plus haut (très haute altitude).

Le graphique de la probabilité que le chat meurt en fonction de l’altitude au-dessus du sol ressemble à ceci:
(terminer à 3, car dissortingbution de chameaux inachevée)

texte alt

Mettre à jour:
La vitesse finale d’un chat est de 100 km / h (60 mph) [= 27,7 m / s = 25,4 verges / s].
La vitesse terminale humaine est de 210 km / h (130 mph) [= 75 m / s = 68,58 verges / s].

Source de vitesse du terminal:
http://en.wikipedia.org/wiki/Cat_righting_reflex

Crédits:
Goooooogle

Je dois vérifier plus tard:
http://en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov/WWW/K-12/airplane/termv.html

J’ai d’abord lu ce problème dans le manuel de conception d’algorithme de Steven Skiena (exercice 8.15). Il a suivi un chapitre sur la programmation dynamic, mais vous n’avez pas besoin de connaître la programmation dynamic pour prouver des limites précises sur la stratégie . D’abord, le problème, puis la solution ci-dessous.

Les œufs se cassent lorsqu’ils sont tombés d’une hauteur suffisante. Étant donné un bâtiment à n étages, il doit y avoir un plancher tel que les œufs tombent du sol et que les œufs tombent du sol f-1. (Si l’œuf se casse d’un plancher, nous dirons f = 1. Si l’œuf survit d’un étage, nous dirons f = n + 1).

Vous cherchez à trouver le sol critique f. La seule opération que vous pouvez effectuer est de déposer un œuf par terre et de voir ce qui se passe. Vous commencez avec k oeufs et cherchez à laisser tomber des oeufs aussi peu de fois que possible. Les oeufs cassés ne peuvent pas être réutilisés (les oeufs intacts peuvent). Soit E (k, n) le nombre minimum d’excréments d’œufs qui suffira toujours.

  1. Montrer que E (1, n) = n.
  2. Montrer que E(k,n) = Θ(n**(1/k)) .
  3. Trouvez une récurrence pour E (k, n). Quelle est la durée d’exécution du programme dynamic pour trouver E (k, n)?

1 seul oeuf

Laisser tomber l’œuf de chaque étage en commençant par le premier trouvera le sol critique dans (au pire) n opérations.

Il n’y a pas d’algorithme plus rapide. À tout moment dans n’importe quel algorithme, laissez le plus haut niveau à partir duquel l’œuf a été vu pour ne pas se casser. L’algorithme doit tester le sol g + 1 avant tout étage supérieur h> g + 1, sinon, si l’œuf devait se détacher du sol h, il ne pourrait pas distinguer f = g + 1 et f = h.

2 oeufs

Considérons d’abord le cas de k = 2 oeufs, lorsque n = r ** 2 est un carré parfait. Voici une stratégie qui prend du temps O (sqrt (n)). Commencez par laisser tomber le premier œuf par paliers. Lorsque le premier oeuf se casse, disons au sol, on sait que le plancher critique f doit être (a-1)r < f <= ar . Nous déposons ensuite le deuxième oeuf de chaque étage à partir de (a-1)r . Lorsque le deuxième œuf se brise, nous avons trouvé le sol critique. Nous avons supprimé chaque oeuf au plus tard, donc cet algorithme prend au pire les opérations 2r, soit is (sqrt (n)).

Lorsque n n'est pas un carré parfait, prenez r = ceil(sqrt(n)) ∈ Θ(sqrt(n)) . L'algorithme rest Θ (sqrt (n)).

Preuve que tout algorithme prend au moins sqrt (n) temps. Supposons qu'il existe un algorithme plus rapide. Considérons la séquence d'étages à partir de laquelle il laisse tomber le premier œuf (à condition qu'il ne se casse pas). Comme il est inférieur à sqrt (n), il doit y avoir un intervalle d'au moins n / sqrt (n) qui est sqrt (n). Lorsque f est dans cet intervalle, l'algorithme devra l'examiner avec le deuxième œuf, et cela doit être fait au sol, rappelant le cas de 1 œuf. CONTRADICTION.

k oeufs

L'algorithme présenté pour 2 oeufs peut être facilement étendu à k oeufs. Déposez chaque oeuf avec des intervalles constants, qui doivent être considérés comme les puissances de la kième racine de n. Par exemple, pour n = 1000 et k = 3, recherchez les intervalles de 100 étages avec le premier œuf, 10 avec le deuxième œuf et 1 avec le dernier œuf.

De même, on peut prouver qu'aucun algorithme n'est plus rapide Θ(n**(1/k)) en induisant de la preuve k = 2.

Solution exacte

Nous en déduisons la récurrence en optimisant l’abandon du premier œuf (étage g), en supposant que nous connaissions des solutions optimales pour des parameters plus petits. Si l'œuf se casse, nous avons les étages de g-1 ci-dessous à explorer avec des œufs de k-1. Si l'œuf survit, nous avons des planchers supérieurs à explorer avec k œufs. Le diable choisit le pire pour nous. Ainsi pour k> 1 la récurrence

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

Cela ne signifie-t-il pas que vous utilisez “The Same Cat”?

Vous pouvez vous en approcher mathématiquement, mais c’est bien avec les maths … avec les bonnes hypothèses, 0 peut être égal à 1 (pour les grandes valeurs de 0).

D’un sharepoint vue pratique, vous pouvez obtenir des “chats similaires”, mais vous ne pouvez pas obtenir “le même chat”.

Vous pourriez essayer de déterminer la réponse de manière empirique, mais je pense qu’il y aurait suffisamment de différences statistiques pour que la réponse soit statistiquement dénuée de sens.

Vous pourriez essayer d’utiliser “The Same Cat”, mais cela ne fonctionnerait pas, car après la première chute, ce n’est plus le même chat. (De même, onecan ne peut jamais entrer deux fois dans la même rivière)

Ou, vous pouvez agréger la santé du chat, en échantillonnant à des intervalles extrêmement rapprochés, et trouver les hauteurs pour lesquelles le chat est “principalement vivant” (opposé à “principalement mort” de “The Princess Bride”). Les chats survivront en moyenne (jusqu’au dernier intervalle).

Je pense que je me suis éloigné de l’intention initiale, mais si vous suivez la voie empirique, je vote pour commencer aussi haut que possible et continuer à laisser tomber les chats alors que la taille diminue jusqu’à ce qu’ils survivent statistiquement. Et puis re-tester sur les chats survivants pour être sûr.

J’ai pris une méthode légèrement différente pour produire une solution.

J’ai commencé par travailler sur le plancher maximum pouvant être couvert à l’aide de x cats et de variables en utilisant la méthode suivante.

Commencez avec 1 étage et continuez à augmenter le nombre de suppositions tout en gardant une trace des planchers vérifiés, qui devinent qu’ils ont été vérifiés et combien de chats restaient pour chaque étage.
Répétez cette opération jusqu’à y fois.

Ce code très inefficace pour calculer la réponse donnée mais néanmoins utile pour un petit nombre de chats / étages.

Code 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) 

Pour 2 chats, le nombre maximum d'étages pouvant être identifiés dans les x suppositions est le suivant:
1, 3, 6, 10, 15, 21, 28 ...

Pour 3 chats:
1, 3, 7, 14, 25, 41, 63 ...

Pour 4 chats:
1, 3, 7, 15, 30, 56, 98 ...

Après des recherches approfondies (impliquant principalement des séquences de nombres dans l' OEIS ), j'ai remarqué que le nombre maximal d'étages pour x suit une combinaison par morceaux.

Pour 2 chats:
n <2: 2 ^ n - 1
n> = 2: C (n, 1) + C (n, 2)

Pour 3 chats:
n <3: 2 ^ n - 1
n> = 3: C (n, 1) + C (n, 2) + C (n, 3)

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

À partir de là, j'ai opté pour une méthode simple d'incrémentation jusqu'à ce que je dépasse le nombre d'étages requirejs.

Code 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 

Cela donne la solution correcte pour (100, 2) = 14.
Pour quiconque souhaite vérifier quelque chose de moins sortingvial, cela donne (1 000 000, 5) = 43.

Cela se passe en O (n) où n est la réponse au problème (plus il y a de chats, mieux c'est).
Cependant, je suis sûr que quelqu'un avec un niveau plus élevé de mathématiques pourrait simplifier les formules par morceaux à calculer dans O (1).

 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). 

Je ne peux pas lire le blog de google à ce sujet (merci à blogwall), mais je ne pense pas qu’une recherche de style binary soit la meilleure. La raison en est qu’une recherche binary est basée sur la notion que la réponse que vous recherchez a la même chance d’être à un index de la liste. Cependant, dans ce cas, ce n’est pas vrai. Dans ce cas, la probabilité de se trouver plus près d’une extrémité de la gamme est grande. Je ne sais pas comment intégrer cela dans la recherche, mais c’est une pensée intéressante.

Tout ce discours fou sur les chats … et il suffit de deviner le problème du nombre avec des suppositions minimales (nombre de chats). il ne devrait pas non plus y avoir besoin de définir artificiellement (et incorrectement) l’infini dans le cadre de la solution. la variable devrait avoir été nommée borne supérieure ou max-try ou une telle. la définition du problème (la chose du chat) pose cependant de sérieux problèmes, avec des personnes réagissant au potentiel de cruauté envers les animaux et aux nombreuses facettes d’un tel problème posé dans la vie réelle. du problème. alors peut-être aurait-il dû être demandé d’une manière totalement différente.