Initiation à l'algorithmique

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 Mostafa Sedoki
Computer science teacher and the founder of the e-learning platform "developpement-informatique.com", my mission is to provide high-quality courses for free to all computer science students and teachers

Cours Similaires :