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)
