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

Exercices corrigés sur les tableaux -TD1

Exercice 1 : 

Étant donné un tableau tab [] de taille n, la tâche consiste à remplacer chaque élément du tableau par la somme des deux éléments suivants consécutifs de manière circulaire, à savoir
, ,… .

  • tab[0] = tab[1] + tab[2]
  • tab[1] = tab [2] + tab[3]
  • ...
  • tab[n-1] = tab[0]+tab[1]

Exemple :
 tab[] = {3, 4, 2, 1, 6}
6 3 7 9 7

tab[] = {5, 2, 1, 3, 8}
3 4 11 13 7
  1. Stockez les premier et deuxième éléments du tableau dans les variables first et second.
  2. pour chaque élément sauf le dernier et l'avant-dernier élément du tableau
    • mettez à jour tab[i] = tab[i+1] +tab[i+2]
  3. Puis mettez à jour le dernier et l'avant dernierélément
    • tab [n-2] = tab [n-1] + premier
    • tab [n - 1] = premier + deuxième
def Update(tab, n):

    # tableau invalid
    if (n < 3):
        return

    first = tab[0]
    second = tab[1]

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

    tab[n-2] = tab[n - 1] + first
    tab[n-1] = first + second
    print(tab)


T = [3, 4, 2, 1, 6]
Update(T, len(T))
            
Exercice 2 : 

Soit un tableau tab[] de taille n où tab[i] est la quantité de bonbons de type i. Vous avez une somme illimitée d'argent. La tâche consiste à acheter le plus grand nombre possible de bonbons répondant aux conditions suivantes: , :

  • Si vous achetez x (i) des bonbons de type i (clairement, 0 ≤ x (i) ≤ tab [i])
  • alors pour tout j (1 ≤ j ≤ i), au moins un des éléments suivants doit être respecté :
    • x(j) < x(i) (vous avez acheté moins de bonbons de type j que de type i)
    • x(j)=0 (vous avez acheté 0 bonbons de type j)

Exemple :
 tab[] = {1, 2, 1, 3, 6}
10

{1, 1, 1, 1}
1

Nous pouvons utiliser une approche gloutonne et commencer à la fin du tableau.
Si nous prenons x bonbons du type i+1, nous ne pouvons prendre que des min (tab[i], x-1) bonbons du type i.
Si cette valeur est négative, nous ne pouvons pas acheter de bonbons du type actuel.

def Update(tab, n):

    # tableau invalid
    if (n < 3):
        return

    first = tab[0]
    second = tab[1]

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

    tab[n-2] = tab[n - 1] + first
    tab[n-1] = first + second
    print(tab)


T = [3, 4, 2, 1, 6]
Update(T, len(T))

            
Exercice 3 : 

Étant donné un tableau d'éléments positifs et négatifs.
La tâche consiste à remplacer chaque i-ème élément du tableau par la différence absolue des sommes absolues des éléments positifs et négatifs dans l’intervalle i + 1 à N. C’est-à-dire trouver la somme absolue de tous les éléments positifs et la somme absolue de tous les éléments négatifs dans la plage i+1 à N.
Maintenant, trouvez la différence absolue entre ces deux sommes et remplacez-le par le i-ème élément.


Exemple :
 N = 5, tab[] = {1, -1, 2, 3, -2}
tab[] = {2, 3, 1, 2, 0}

N = 6, tab[] = {-3, -4, -2, 5, 1, -2}
tab[] = {2, 2, 4, 1, 2, 0}

Solution naive

L’approche naïve consiste à exécuter deux boucles et pour tous les i-èmes éléments, calculer la valeur absolue de la somme de tous les éléments positifs et négatifs dont l’indice est compris entre i + 1 et N. Trouvez maintenant la différence absolue des deux sommes et remplacez avec le i-ème élément.

La complexité temporelle de cette approche sera O(N2) où N est le nombre d'éléments dans le tableau.

                def RemplacerTab(N, tab):
                    for i in range(N):
                        pos_s = 0
                        neg_s = 0
                
                        # calculer la somme absolue des valeurs positives et négative
                        # de i+1 à N
                        for j in range(i + 1, N, 1):
                            if (tab[j] > 0):
                                pos_s += tab[j]
                            else:
                                neg_s += tab[j]
                
                        diff = abs(pos_s) - abs(neg_s)
                
                        # remplacer le ième élément par la différence
                        tab[i] = abs(diff)
                
                
                T = [-3, -4, -2, 5, 1, -2]
                N = 6
                RemplacerTab(N, T)
                print(T)
            

Solution Efficace

  1. Initialisez les sommes positives et négatives à 0.
  2. Exécutez maintenant une boucle pour du dernier élément au premier
    • calculez diff = abs (pos_s) - abs (neg_s)
    • si le i-ème élément est positif, ajoutez-le à pos_s sinon ajoutez-le à neg_s
    • remplacez le i-ème élément par la différence absolue, à savoir abs (diff)
Complexité: O(N), où N est le nombre d'éléments.
                def RemplacerTab(N, tab):
                    pos_s = 0
                    neg_s = 0
                
                    for i in range(N - 1, -1, -1):
                        diff = abs(pos_s) - abs(neg_s)
                
                        # si le i-ème élément est positif
                        # ajoutez-le à pos_s
                        if (tab[i] > 0):
                            pos_s = pos_s + tab[i]
                
                        # sinon ajoutez-le à neg_s
                        else:
                            neg_s = neg_s + tab[i]
                
                        # remplacez le i-ème élément par la différence absolue
                        tab[i] = abs(diff)
            

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 :