Problème de codage quotidien 24  Bon retour avec un autre problème à résoudre ! Aujourd’hui, nous avons affaire à des œufs tombant des toits avec ce problème vraiment sympa, qui impliquera deux solutions possibles : une assez naïve et une plus intelligente. Ce dernier nous donnera également l'occasion de parler d'un algorithme assez célèbre.  Comme toujours, le problème d'aujourd'hui est fourni par la merveilleuse newsletter  , auquel vous pouvez vous abonner gratuitement pour relever également votre défi de codage quotidien. Vérifiez-le et essayez également de résoudre vos problèmes !   Problème de codage quotidien  Assez parlé alors ; voyons le problème !  Le problème  Ce problème a été posé par Goldman Sachs lors d'un entretien d'embauche. Voyons le problème.      œufs identiques et accédez à un bâtiment de   étages. Votre tâche est de trouver l'étage le plus bas qui provoquera la rupture d'un œuf s'il tombe de cet étage. Une fois qu’un œuf se brise, il ne peut plus être laissé tomber. Si un œuf se brise lorsqu'il tombe du   étage, vous pouvez supposer qu'il se brisera également lorsqu'il tombe d'un étage supérieur à   . Vous recevez N k xth x   Écrivez un algorithme qui trouve le nombre minimum d'essais nécessaires, dans le pire des cas, pour identifier cet étage.      et   , nous devrons essayer de laisser tomber l'œuf à chaque étage, en commençant par le premier, jusqu'à atteindre le cinquième étage, notre solution sera donc   . Par exemple, si N = 1 k = 5 5  Ainsi, on nous donne des œufs à lancer depuis différents étages d’un immeuble. Nous sommes tristes qu'à partir d'un certain étage (que nous appellerons   ), les œufs jetés ne se brisent pas en tombant au sol. targetFloor  De cet étage à tous les étages inférieurs, les œufs ne se briseront pas lorsqu'ils seront jetés par la fenêtre. Ce qu'on nous demande de faire, c'est de trouver une méthode efficace pour trouver le   . targetFloor  Comme prévu, nous verrons deux méthodes pour résoudre ce problème : une méthode très simple, qui forcera brutalement la solution, mais elle ne sera pas efficace. Le second sera beaucoup plus efficace et tentera de résoudre le problème en cassant le moins d'étapes possible.  Cela nous donnera également l’occasion de parler d’un algorithme vraiment célèbre et important ; un de ceux qu’il faut savoir faire… en gros n’importe quoi !  Configuration de l'environnement  Pour commencer, nous devons configurer un peu l'environnement, à savoir le bâtiment et le   . Pour créer le bâtiment, nous créons simplement un tableau contenant les numéros des étages, du rez-de-chaussée jusqu'au nᵗʰ étage. Ensuite, nous générons un nombre aléatoire qui sera notre   . targetFloor targetFloor  Nous allons réécrire ce problème en Go : assez simple pour être lisible, mais suffisamment complexe pour comprendre la mécanique interne.   https://gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go  On crée d'abord le tableau qui nous servira de bâtiment : on peut lui donner la taille que l'on veut, plus la taille est grande, plus le bâtiment sera haut. Après cela, nous créons une instance de   à l'aide du module   intégré à Go. targetFlor math/rand  En gros, nous créons un nouvel entier aléatoire entre 0 et la hauteur du bâtiment (… la longueur du tableau :D) en utilisant comme source l'heure actuelle.  La solution de force brute  Bien entendu, la solution la plus simple possible serait de jeter chaque œuf à chaque étage, afin de voir à quel étage les œufs commencent à se casser. Puisque nous avons une variable contenant ces informations, on pourrait simplement faire une boucle for pour résoudre le problème :   https://gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go  Bien qu’il s’agisse de la solution la plus simple, elle s’avère malheureusement très inefficace. Imaginez si l'étage de droite est celui du haut : il faut casser 100 000 œufs pour résoudre le problème : ce serait une énorme omelette mais tout un gaspillage !  D’une manière générale, cette solution a une complexité temporelle de O(n) car la complexité de la solution croît linéairement avec la complexité du problème d’entrée. Ce n’est cependant pas la solution la plus efficace à laquelle nous pourrions penser.  Une solution efficace  Réfléchissons alors à une solution efficace. Au lieu de marcher étage par étage pour casser chaque œuf à chaque étage, nous pourrions faire une supposition et, en fonction du résultat de cette supposition, ajuster la supposition suivante.  Voici un exemple : supposons que nous ayons un bâtiment de 10 étages et que le   soit le 7ème étage (nous ne le savons pas, bien sûr). Nous pourrions faire les suppositions suivantes :  targetFloor  Fondamentalement, nous supposons que le   est l’étage intermédiaire du bâtiment. Nous jetons l’œuf à partir de là, et les résultats possibles sont au nombre de deux : targetFloor  l'œuf se brise, ce qui signifie que nous sommes trop hauts. Nous pouvons écarter l'étage supérieur à celui-ci, inclus, et continuer nos suppositions.  L'œuf ne se casse pas, ce qui signifie que nous sommes trop bas ou au bon étage. Nous rejetons tous les étages inférieurs à celui-ci, inclus, et  Compte tenu de cela, nous prenons maintenant une autre hypothèse éclairée sur l’étage intermédiaire ou le bâtiment « restant », et appliquons la même stratégie vue ci-dessus. Nous pouvons poursuivre cette approche jusqu’à ce qu’il ne nous reste plus qu’un étage.  Si vous reconnaissez cette approche, vous avez parfaitement raison : il s’agit simplement d’une   appliquée à un problème du « monde réel ». La recherche binaire est un algorithme simple et   , ce qui signifie qu'à chaque étape, la taille du problème est réduite de moitié jusqu'à ce que nous trouvions la solution. recherche binaire soigné de type diviser pour régner  Cela signifie que cet algorithme, comparé au précédent, est bien plus rapide. Voyons le code !   https://gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go  Examinons plus en profondeur. La fonction de recherche binaire prend 4 arguments :    , un tableau d'entiers, qui est le bâtiment sur lequel nous effectuons une boucle ; overArray    , l'index du bas du bâtiment ; bottom    , l'index du dernier étage du bâtiment ; top    , la variable contenant   pour vérifier si on peut le trouver dans le bâtiment. breakFloor targetFloor  Après cela, on boucle sur le bâtiment tandis que   est plus bas que   : en recherche binaire, lorsque les deux arguments de position s'entrelacent et s'échangent, cela signifie que l'élément recherché n'a pas été trouvé. bottom top  Par conséquent, si l'algorithme se retrouve dans cette situation, la boucle se termine et nous renvoyons   , ce qui signifie que l'élément que nous recherchons n'était pas présent dans le tableau. Si nous recherchons toujours l'élément, nous appliquons ce qui est montré dans l'image ci-dessus. -1  Nous calculons l'élément   comme plancher entre   et   et nous vérifions si   . Si c'est le cas, nous renvoyons le   comme résultat. middlePoint bottom top middlePoint == breakFloor middlePoint  Si ce n'est pas le cas, nous ajustons   ou   en conséquence : si   est supérieur à   , cela signifie que nous sommes trop haut sur le bâtiment, nous réduisons donc notre prédiction en définissant le   étage possible à   . bottom top middlePoint breakFloor top middlePoint — 1  Si   est plus petit que   , nous ajustons notre   en définissant comme   . middlePoint breakFloor bottom middlePoint+1  Maintenant, pour tout vérifier, dans la fonction   , nous générons l'environnement comme avant, et créons une nouvelle variable appelée   qui contiendra notre résultat. main bsFloor  Pour confirmer que notre algorithme nous a amené au bon résultat, nous imprimons à la fois   et   , qui étaient auparavant générés de manière aléatoire. bsFloor targetFloor  Complexité temporelle  Comme nous l’avions prévu précédemment, cet algorithme est bien plus rapide que l’algorithme linéaire. Puisque nous réduisons de moitié le bâtiment à chaque étape, nous pouvons trouver le bon étage dans log₂(n) où n est égal à   . len(building)  Cela signifie que la complexité temporelle de cet algorithme est   . Pour vous donner une comparaison entre la solution linéaire et cette dernière, si le bâtiment a 100 étages, l'algorithme linéaire prend dans le pire des cas 100 itérations, tandis que l'algorithme de recherche binaire prend log₂100 = 6,64, donc 7 itérations. O(log(n))  Aussi, cette dernière est de plus en plus efficace que la linéaire car plus le bâtiment s'agrandit, plus la recherche binaire est efficace. Pour un bâtiment de 1.000.000.000 d'étages, le linéaire prend 1.000.000.000 pas, tandis que le binaire prend log₂1.000.000.000 = 29,9, donc 30 pas. Une énorme amélioration!   Conclusion  Ça y est ...! J'espère que vous avez apprécié l'article autant que j'ai eu du plaisir à essayer de résoudre le défi ! Si c'est le cas, laissez un applaudissement ou deux, ce serait un grand soutien ! Si vous aimez ce type d'articles et souhaitez en voir plus, suivez la page car je publie ce type de contenu chaque fois que je le peux.  Enfin, si vous avez trouvé cet article intéressant ou utile et que vous souhaitez y contribuer en offrant un café, n'hésitez pas à le faire sur mon  page!   Kofi  Et comme toujours, merci d'avoir lu!   Nicolas   Également publié  ici

Read My Stories

Cet audio est produit dans la langue originale de l'histoire !

Quand vous devez jeter des œufs depuis le toit : problème de codage quotidien

About Author

COMMENTAIRES

ÉTIQUETTES

CET ARTICLE A ÉTÉ PARU DANS

Related Stories

Le modèle Bitcoin UTXO, alimentant un écosystème unique

Des forums aux flux : comment les algorithmes des réseaux sociaux façonnent l'interaction numérique

Les couches invisibles : pourquoi les entretiens avec les utilisateurs sont un atout irremplaçable

Comment améliorer votre flux de travail par 10 : 17 applications essentielles

Le modèle Bitcoin UTXO, alimentant un écosystème unique

Des forums aux flux : comment les algorithmes des réseaux sociaux façonnent l'interaction numérique

Les couches invisibles : pourquoi les entretiens avec les utilisateurs sont un atout irremplaçable

Comment améliorer votre flux de travail par 10 : 17 applications essentielles

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps