Exercices corrigés sur les tableaux -TD1

def mise_a_jour_circulaire(tab):
    """
    Remplace chaque élément par la somme des deux suivants (circulaire)
    
    Complexité : O(n) temps, O(1) espace
    """
    n = len(tab)
    
    # Tableau invalide
    if n < 3:
        print("Tableau trop petit (n < 3)")
        return tab

    # Sauvegarder les premières valeurs
    first = tab[0]
    second = tab[1]

    # Mettre à jour les éléments jusqu'à l'avant-avant-dernier
    for i in range(n - 2):
        tab[i] = tab[i + 1] + tab[i + 2]

    # Mettre à jour l'avant-dernier élément
    tab[n - 2] = tab[n - 1] + first
    
    # Mettre à jour le dernier élément
    tab[n - 1] = first + second
    
    return tab


# Tests
T1 = [3, 4, 2, 1, 6]
T2 = [5, 2, 1, 3, 8]

print(f"Original: {T1}")
print(f"Modifié : {mise_a_jour_circulaire(T1)}")
print()
print(f"Original: {T2}")
print(f"Modifié : {mise_a_jour_circulaire(T2)}")

def max_bonbons(tab):
    """
    Calcule le nombre maximum de bonbons qu'on peut acheter
    sous les contraintes données.
    
    Complexité : O(n) temps, O(1) espace
    """
    n = len(tab)
    total = 0
    precedent = float('inf')  # on peut prendre autant qu'on veut du dernier type

    # Parcourir de la fin vers le début
    for i in range(n - 1, -1, -1):
        # On prend au maximum tab[i] mais aussi au maximum (precedent - 1)
        if precedent > 0:
            pris = min(tab[i], precedent - 1)
        else:
            pris = 0
        
        # On ne peut pas prendre de quantités négatives
        if pris < 0:
            pris = 0
        
        total += pris
        precedent = pris

    return total


# Tests
T1 = [1, 2, 1, 3, 6]
T2 = [1, 1, 1, 1]

print(f"Tableau {T1} → Nombre max de bonbons: {max_bonbons(T1)}")
print(f"Tableau {T2} → Nombre max de bonbons: {max_bonbons(T2)}")

def remplacer_par_diff_naive(tab):
    """
    Version naïve - O(n²)
    """
    n = len(tab)
    
    for i in range(n):
        pos_s = 0
        neg_s = 0

        # calculer la somme absolue des valeurs positives et négatives
        # de i+1 à n-1
        for j in range(i + 1, n):
            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)
    
    return tab


T = [-3, -4, -2, 5, 1, -2]
print(f"Original: {T}")
print(f"Naïve   : {remplacer_par_diff_naive(T)}")

def remplacer_par_diff_efficace(tab):
    """
    Version efficace - O(n)
    """
    n = len(tab)
    pos_s = 0
    neg_s = 0

    # Parcourir de la fin vers le début
    for i in range(n - 1, -1, -1):
        diff = abs(pos_s) - abs(neg_s)

        # Si l'élément courant est positif, l'ajouter à pos_s
        if tab[i] > 0:
            pos_s = pos_s + tab[i]
        # Sinon l'ajouter à neg_s
        else:
            neg_s = neg_s + tab[i]

        # Remplacer l'élément par la différence absolue
        tab[i] = abs(diff)

    return tab


# Tests
T1 = [1, -1, 2, 3, -2]
T2 = [-3, -4, -2, 5, 1, -2]

print(f"Original 1: [1, -1, 2, 3, -2]")
print(f"Résultat 1: {remplacer_par_diff_efficace([1, -1, 2, 3, -2])}")
print()
print(f"Original 2: [-3, -4, -2, 5, 1, -2]")
print(f"Résultat 2: {remplacer_par_diff_efficace([-3, -4, -2, 5, 1, -2])}")