########################### Rectangles et triangles ###########################

# 1)

def rectangle(n, p):
    for i in range(n):
        for j in range(p):
            print('*', end='')
        print()

# En une ligne :

def rectangle(n, p):
    print(("*" * p + "\n") * n)


# 2)

def triangle(n):
    for i in range(n):
        for j in range(i+1):
            print('*', end='')
        print()


# 3) Première méthode : avec une variable qu'on incrémente après affichage.

def remplissage_lignes1(n, p):
    a = 1
    for i in range(n):
        for j in range(p):
            print(a, end=" ")
            a = a + 1
        print()

# Deuxième méthode : avec une formule.

def remplissage_lignes(n, p):
    for i in range(n):
        for j in range(p):
            print(p*i + j + 1, end=" ")
        print()


# 4) Première méthode :

def remplissage_colonnes(n, p):
    for i in range(n):
        a = i + 1  # numéro de la ligne
        for j in range(p):
            print(a, end=" ")
            a = a + n
        print()

# Deuxième méthode :

def remplissage_colonnes(n, p):
    for i in range(n):
        for j in range(p):
            print(i + n*j + 1, end=" ")
        print()


# 5)

# Première méthode :

def floyd(n):
    a = 1
    for i in range(n):
        for j in range(i+1):
            print(a, end=" ")
            a = a + 1
        print()

# Deuxième méthode :

def floyd(n):
    for i in range(n):
        for j in range(i+1):
            print(i*(i+1)//2 + j + 1, end=" ")
        print()


########################## Tableaux bidimensionnels ##########################

# 1)

def table(n):
    t = []
    for i in range(1, n+1):
        ligne = []
        for j in range(1, n+1):
            ligne.append(i*j)
        t.append(ligne)
    return t

# ou avec des listes par compréhension :

def table(n):
    return [[i*j for j in range(1, n+1)] for i in range(1, n+1)]


# 2) a)

def est_dans(x, t):
    for L in t:
        for y in L:
            if y == x:
                return True
    return False

# Si on préfère itérer sur des range :

def est_dans(x, t):
    for i in range(len(t)):
        for j in range(len(t[i])):
            if t[i][j] == x:
                return True
    return False

# 2) b) Dans le meilleur des cas, l'élément cherché est le premier élément du
# tableau et on ne fait qu'une comparaison.

# Dans le pire des cas, l'élément cherché n'est pas dans le tableau et on fait
# n*p comparaisons.


# 3)

def max_2D(t):
    m = t[0][0]
    for L in t:
        for x in L:
            if x > m:
                m = x
    return m

# Si on préfère itérer sur des range :

def max_2D(t):
    m = t[0][0]
    for i in range(len(t)):
        for j in range(len(t[i])):
            if t[i][j] > m:
                m = t[i][j]
    return m


# 4) Ici on a besoin des indices, donc il faut itérer sur des range.

def coords_max_2D(t):
    m = t[0][0]
    imax, jmax = 0, 0
    for i in range(len(t)):
        for j in range(len(t[i])):
            if t[i][j] > m:
                m = t[i][j]
                imax, jmax = i, j
    return imax, jmax


################## Valeurs les plus proches dans une liste ##################

# 1)

def distance(x, y):
    return abs(x - y)


# 2)

def valeurs_les_plus_proches(L):
    ecartmin = distance(L[0], L[1])
    a, b = 0, 1
    for i in range(len(L)):
        for j in range(i):
            d = distance(L[i], L[j])
            if d < ecartmin:
                ecartmin = d
                a, b = i, j
    return L[a], L[b]

# On peut aussi donner la valeur +infini à l'ecart minimal au début :

def valeurs_les_plus_proches(L):
    ecartmin = float('inf')
    for i in range(len(L)):
        for j in range(i):
            d = distance(L[i], L[j])
            if d < ecartmin:
                ecartmin = d
                a, b = i, j
    return L[a], L[b]


# 3) Chaque calcul de distance effectue une soustraction. Pour chaque valeur de i,
# j prend i-1 valeurs.

# La fonction effectue donc 1 + 2 + ... + (n-1) = n(n-1)/2 soustractions.


# 4) Il suffit de comparer les distances entre deux éléments consécutifs.

def valeurs_les_plus_proches_liste_triee(L):
    ecartmin = distance(L[0], L[1])
    imin = 0
    for i in range(1, len(L)-1):
        d = distance(L[i], L[i+1])
        if d < ecartmin:
            ecartmin = d
            imin = i            
    return L[imin], L[imin+1]

# Cette fonction ne fait que n-1 soustractions.


# 5)

def valeurs_les_plus_proches_2(L):
    return valeurs_les_plus_proches_liste_triee(sorted(L))


# 6) a)

from random import randint

def liste_aleatoire1(n, N):
    L = []
    for i in range(n):
        L.append(randint(1, N))
    return L

# ou avec une liste par compréhension :

def liste_aleatoire(n, N):
    return [randint(1, N) for i in range(n)]


# 6) b) La deuxième fonction est nettement plus rapide que la première lorsque
# la longueur de la liste est grande.