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

convertir une boucle Pour imbriquée en une boucle Pour simple

La technique de fenêtre coulissante est utile pour résoudre des problèmes dans les tableaux ou les chaînes,
en particulier il est considéré comme une technique qui pourrait réduire la complexité de temps de O(n2) à O(N).

Cette technique montre comment une boucle imbriquée dans peu de problèmes peut être convertie en une boucle Pour simple 

Il y a deux types de problèmes qui peuvent être résolus en utilisant cette technique

  • Longueur de fenêtre k est fixée : la longueur de la fenêtre est fixée et il vous est demandé de rechercher quelque chose dans la fenêtre, tel que la somme maximale de toutes les fenêtres, le nombre maximal ou médian de chaque fenêtre. Habituellement, nous avons besoin de types de variables pour maintenir l’état de la fenêtre. Certaines sont aussi simples qu’un entier ou peuvent être aussi compliquées que des structures de données avancées telles que list, files.
  • Deux pointeurs + critères: la taille de la fenêtre n'est pas fixée, il vous est généralement demandé de trouver le sous-tableau qui répond aux critères, par exemple, à partir d'un tableau d'entiers, recherchez le nombre de sous-tableaux dont la somme est égale à une valeur cible.

où on peut appliquer cette technique

Exemple :

Étant donné un tableau d'entiers de taille "n". Notre but est de calculer la somme maximale de ‘k’ consécutives éléments dans le tableau.

arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20} ; K=4
  39
arr[] = {100, 200, 300, 400} ; K=2
  700
Alors, analysons le problème avec l’approche "brute force".
Nous commençons avec le premier indice et la somme jusqu'au k-ième élément. Nous le faisons pour tous les blocs consécutifs possibles ou groupes de k éléments.
Cette méthode nécessite une boucle pour imbriquée, la boucle pour externe commence par l'élément de départ du bloc de k éléments et la boucle interne ou imbriquée calcule la somme jusqu'au k-ème élément.

la complexité est en O(k*n) car il contient deux boucles imbriquées.

                    import sys
                    INT_MIN = -sys.maxsize - 1
                    
                    def maxSomme(tab, n, k):
                    
                        max_somme = INT_MIN
                        for i in range(n - k + 1):
                            somme_courante = 0
                            for j in range(k):
                                somme_courante = somme_courante + tab[i + j]
                    
                            # Update result if required.
                            max_somme = max(somme_courante, max_somme)
                    
                        return max_somme
                    
            
Description du technique :
Généralement parlant, une fenêtre coulissante est une sous-liste qui s'étend sur une collection sous-jacente. I. e., si vous avez un tableau comme
[a b c d e f g h]
une fenêtre coulissante de taille 3 :
                [a b c]
                  [b c d]
                    [c d e]
                      [d e f]
                         [e f g]
                           [f g h]
            

Ceci est utile si par exemple vous voulez calculer une moyenne de k éléments adjacents, ou si vous souhaitez créer un ensemble de toutes les paires adjacentes etc.

Applications 

Considérons un tableau tab[] = {5, 2, -1, 0, 3} et une valeur de k = 3
  1. Nous calculons la somme des k premiers éléments en utilisant une boucle et stockant la somme dans la variable max_somme.
  2. Ensuite, nous allons parcourir le tableau jusqu'à la fin et en même temps garder une trace de la somme maximale.
  3. Pour obtenir la somme actuelle du bloc de k éléments, il suffit de soustraire le premier élément du bloc précédent et d’ajouter le dernier élément du bloc actuel.

Maintenant, il est évident que la complexité temporelle est linéaire O(n) car nous pouvons voir qu’une seule boucle est exécutée dans notre code.

                def SommeMax(tab, n, k):
                    # n doit etre superieur a k
                    assert n > k
                
                    # calculer la somme de k premiers elements
                    max_somme = 0
                    for i in range(k):
                        max_somme += tab[i]
                
                    somme_courante = max_somme
                    for i in range(k, n):
                        somme_courante += tab[i]-tab[i-k]
                        max_somme = max(max_somme, somme_courante)
                
                    return max_somme
                
                
                t = [1, 4, 2, 10, 2, 3, 1, 0, 20]
                print(SommeMax(t, len(t), 4))
                
            

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 :