Aller au contenu

Activité - Complexité ?☘

Dans le dossier [NSI], créez le dossier [G01-Complexite].
Dans ce dossier, enregistrez sous les noms indiqués chacun des programmes que vous allez créer et compléter au fur et à mesure de cette activité.

Le problème

n est un entier strictement positif.
On souhaite déterminer l'ensemble des couples (a \, ; b) d'entiers positifs tels que a \times b = n.

TPG01.11 - Un premier algorithme☘

Copiez/collez et complétez la définition de la fonction algo01() qui prend pour paramètre un entier n strictement positif et qui renvoie un tableau constitué de tous les couples (a ; b) d'entiers positifs tels que a*b = n.
Le résultat peut contenir des « doublons ».

1
2
3
4
5
def algo01(n):
    """
    n - int, entier strictement positif
    Sortie: list - tableau des couples (a, b) d'entiers positifs tels que a*b = n
    """

Exemple de tests

L'exécution du second exemple peut prendre un peu de temps... 

>>> algo01(297)
[(1, 297), (3, 99), (9, 33), (11, 27), (27, 11), (33, 9), (99, 3), (297, 1)]

>>> algo01(18725)
[(1, 18725), (5, 3745), (7, 2675), (25, 749), (35, 535), (107, 175), (175, 107), (535, 35), (749, 25), (2675, 7), (3745, 5), (18725, 1)]

TPG01.12 - Un second algorithme☘

Copiez/collez et complétez la définition de la fonction algo02() qui réalise la même chose que la fonction algo01() mais en utilisant une seule boucle au lieu de deux.
Le résultat peut contenir des « doublons ».

1
2
3
4
5
def algo02(n):
    """
    n - int, entier strictement positif
    Sortie: list - tableau des couples (a, b) d'entiers positifs tels que a*b = n
    """

Que pouvez-vous constater en exécutant les tests suivants ?

Exemple de tests

>>> algo02(297)
[(1, 297), (3, 99), (9, 33), (11, 27), (27, 11), (33, 9), (99, 3), (297, 1)]

>>> algo02(18725)
[(1, 18725), (5, 3745), (7, 2675), (25, 749), (35, 535), (107, 175), (175, 107), (535, 35), (749, 25), (2675, 7), (3745, 5), (18725, 1)]
Réponse

L'appel algo02(18725) est exécuté quasi-instantanément contrairement à l'appel algo01(18725).

TPG01.13 - Comparaison☘

Afin de comparer l'efficacité des deux algorithmes précédents, on va enregistrer les temps mis par chacun d'eux pour trouver les couples d'entiers (a \, ; b) tels que a \times b = n avec n prenant successivement pour valeurs 100, 1100, 2100, ..., 10100.

On représente ensuite ces données dans un repère tel que :

  • sur l'axe des abscisses, on trouve les différentes valeurs de n ;
  • sur l'axe des ordonnées, on trouve le temps mis pour déterminer les couples (a \, ; b) correspondant.

Questions☘

  1. Téléchargez le fichier TPG01.13.py puis enregistrez-le dans le répertoire [G01-Complexite].
  2. Exécutez ce programme.

  3. Après un peu d'attente, on obtient deux courbes.
    Correspondent-elles aux constatations réalisées précédemment ?

    Les courbes à obtenir

    Courbes

  4. Quelles sont leur forme ?
    Les formes obtenues vous semblent-elles cohérentes ?