Initiation à l'algorithmique

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 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 :