Pascal's Triangle

Q: Quelle est la complexité temporelle de la génération du triangle de Pascal ?

O(n²) pour n lignes : le triangle contient environ n²/2 éléments et chacun nécessite une addition. C’est optimal, puisque tu dois écrire chaque élément du résultat. L’espace supplémentaire, en dehors du résultat, est de O(1) .

Q: Quel est le lien entre le triangle de Pascal et les coefficients binomiaux ?

L’entrée k de la ligne r , en comptant à partir de 0, est C(r, k) , le nombre de façons de choisir k éléments parmi r . La règle de la somme est l’identité C(r, k) = C(r-1, k-1) + C(r-1, k) , et la somme de la ligne r est égale à 2^r , le nombre de sous-ensembles de r éléments.

Q: Peux-tu calculer une ligne sans construire les lignes au-dessus ?

Oui. Commencez par 1 et obtenez chaque entrée suivante à partir de la précédente : C(r, k) = C(r, k-1) × (r-k+1) / k . Multipliez avant de diviser afin que la division soit exacte, et utilisez un entier de 64 bits pour le produit. La ligne r prend alors un temps O(r) .

FacileProgrammation dynamique

+10

Dans le triangle de Pascal, la première ligne est [1]. Chaque ligne suivante comporte une entrée de plus, commence et se termine par 1, et chaque entrée intermédiaire est la somme des deux entrées directement au-dessus. On vous donne un entier numRows. Renvoyez les numRows premières lignes du triangle, en commençant par la ligne du haut, chaque ligne étant un tableau d'entiers.

Fonction

generate(numRows: integer) → integer-2d-array

numRowsinteger: combien de lignes du triangle construire
Renvoieinteger-2d-array: les numRows premières lignes, en commençant par la ligne du haut

Contraintes

1 ≤ numRows ≤ 30
Chaque valeur des 30 premières lignes tient dans un entier signé de 32 bits. La plus grande est 77558760, au milieu de la ligne 30.

Exemples

Entrée: numRows = 5
Sortie: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Explication: Chaque entrée intérieure additionne les deux entrées situées au-dessus. Quatrième ligne : 3 = 1 + 2 et 3 = 2 + 1. Cinquième ligne : 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1.

Entrée: numRows = 1
Sortie: [[1]]
Explication: Avec une seule rangée, le triangle se réduit à son sommet, [1].

Pour aller plus loin

Peux-tu ne conserver qu’un seul tableau et le mettre à jour sur place, ligne après ligne ? Dans quel sens la boucle interne doit-elle s’exécuter, et pourquoi ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Un élément est la somme de deux éléments de la rangée au-dessus. Réévaluer cette règle depuis le début pour chaque élément recalcule les mêmes valeurs, et le travail double à chaque rangée. Les rangées que tu renvoies sont les réponses mémorisées à ces problèmes plus petits ; construis donc le triangle de haut en bas, chaque rangée à partir de celle qui la précède.

Calculez chaque entrée récursivement

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Numérotez les lignes et les positions à partir de 0. La définition devient une fonction : entry(row, col) vaut 1 sur les bords, où col vaut 0 ou row, et sinon entry(row-1, col-1) + entry(row-1, col). Elle est correcte parce que c’est la définition.

La récursion s’arrête uniquement sur les bords, qui renvoient 1, donc une entrée de valeur v nécessite environ 2v appels. La ligne r totalise jusqu’à 2^r, donc 30 lignes nécessitent environ 2^31 appels, soit plus de deux milliards.

Algorithme

Écris entry(row, col) : renvoie 1 si col vaut 0 ou si col est égal à row.
Sinon, renvoie entry(row-1, col-1) + entry(row-1, col).
Pour chaque row de 0 à numRows-1, collecte entry(row, col) pour chaque col de 0 à row.
Renvoie la liste des lignes.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

Construisez chaque ligne à partir de la ligne précédente

Intuition

La récursion continue à demander des entrées des lignes précédentes, et tu construis quand même ces lignes. Calcule donc les lignes de haut en bas et, pendant que tu remplis la ligne r, lis la ligne r-1, qui est déjà terminée. Chaque entrée nécessite une addition : le tableau des réponses plus petites constitue lui-même le résultat.

Initialiser chaque ligne avec r + 1 uns définit ses deux bords, donc les lignes 0 et 1, qui n’ont pas de positions intérieures, ne nécessitent aucun cas particulier. Le triangle contient 1 + 2 + ... + n, soit environ n²/2, entrées ; le travail est donc en O(n²) et ne nécessite aucune mémoire au-delà du résultat : 465 entrées pour 30 lignes, au lieu de deux milliards d’appels.

Algorithme

Commencez avec une liste de lignes vide.
Pour chaque row de 0 à numRows-1, créez row + 1 uns.
Pour chaque col de 1 à row-1, définissez sa valeur comme la somme des positions col-1 et col de la ligne précédente.
Ajoutez la ligne et continuez. Retournez la liste.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

Pièges et cas limites

Renvoyer numRows + 1 lignes. En commençant la numérotation à 0, la dernière ligne nécessaire est numRows-1.
Parcourir les arêtes avec la boucle interne. La position 0 n’a pas de parent à gauche et la position row n’en a pas à droite ; leur lecture provoque donc un dépassement des limites.
Une plage qui échoue pour les petites lignes. En Swift, 1..<row provoque une erreur lorsque row vaut 0, et en R, 2:(row-1) compte à rebours jusqu’à 1 lorsque row vaut 2.
Calculer les valeurs à l’aide de factorielles. C(29, 14) tient dans un int, mais 29! provoque un dépassement même pour un entier de 64 bits.
Ajouter le même tableau pour chaque ligne, puis le modifier. Toutes les lignes de la réponse deviennent alors la dernière.

Questions fréquentes3

Quelle est la complexité temporelle de la génération du triangle de Pascal ?

O(n²) pour n lignes : le triangle contient environ n²/2 éléments et chacun nécessite une addition. C’est optimal, puisque tu dois écrire chaque élément du résultat. L’espace supplémentaire, en dehors du résultat, est de O(1).

Quel est le lien entre le triangle de Pascal et les coefficients binomiaux ?

L’entrée k de la ligne r, en comptant à partir de 0, est C(r, k), le nombre de façons de choisir k éléments parmi r. La règle de la somme est l’identité C(r, k) = C(r-1, k-1) + C(r-1, k), et la somme de la ligne r est égale à 2^r, le nombre de sous-ensembles de r éléments.

Peux-tu calculer une ligne sans construire les lignes au-dessus ?

Oui. Commencez par 1 et obtenez chaque entrée suivante à partir de la précédente : C(r, k) = C(r, k-1) × (r-k+1) / k. Multipliez avant de diviser afin que la division soit exacte, et utilisez un entier de 64 bits pour le produit. La ligne r prend alors un temps O(r).

def generate(numRows):
    # Écrivez le code ici

Test #1

Test #2

Argument

numRows = 5

Résultat attendu

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]