Exercices corrigés sur les tableaux -TD1
É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]
6 3 7 9 7
tab[] = {5, 2, 1, 3, 8}
3 4 11 13 7
- Stockez les premier et deuxième éléments du tableau dans les variables first et second.
- 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]
- 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))
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)
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))
É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.
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
- Initialisez les sommes positives et négatives à 0.
- 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)
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)