Initiation à l'algorithmique

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

Collecter l'eau de pluie entre les tours

Etant donné un tableau où chaque élément représente la hauteur d'une tour, s'il commence à pleuvoir, quelle est la quantité d'eau pouvant être collectée entre les tours?

On suppose que la largeur de chaque tour est 1

Exemple :
T=[1, 5, 2, 3, 1, 7, 2, 4]

La réponse est : 11

Procedure :
  • pour chaque tour, nous essayons de déterminer s'il y a une unité d'eau de pluie au-dessus, si oui, quelle en est la quantité?
  • continue d'ajouter la quantité d'eau de pluie fournie par chaque tour pour obtenir le total pour l'ensemble de tours donné
Pour une tour, comment pouvons-nous savoir s'il y a une unité d'eau de pluie dessus :
Pour que l'eau de pluie soit sur une tour, la hauteur de la tour doit être inférieure à celle d'une des tours voisines.
Exemple Tour 2
Quelle est la quantité maximale d'eau de pluie au-dessus de la tour actuelle :

tout d'abord en regardant à gauche de la tour actuelle et en recherchant la hauteur maximale(maxleft), puis en regardant à droite et en recherchant la hauteur maximale(maxright), et prenez
min(maxleft, maxright) - hauteur de la tour actuelle

  • Créer deux tableaux de la même taille que le tableau original, maxgauche, maxdroite
  • maxgauche[i] signifie la hauteur maximale sur le côté gauche de la tour tours[i], de même pour maxdroite[i]
  • Calculer pour chaque tour rainwater =min(maxgauche[i],maxdroite[i])-tours[i]
                def collecter(tab):
                    n=len(tab)

                    maxgauche = [0]*n 
                    maxdroite = [0]*n 
                    quantite = 0
                  
                    maxgauche[0] = tab[0] 
                    for i in range( 1, n): 
                        maxgauche[i] = max(maxgauche[i-1], tab[i]) 

                    maxdroite[n-1] = tab[n-1]
                    for i in range(n-2, -1, -1): 
                        maxdroite[i] = max(maxdroite[i+1], tab[i]); 

                    for i in range(n): 
                        quantite += min(maxgauche[i],maxdroite[i]) - tab[i] 
                  
                    return quantite 
            

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :