Domaine : Récursivité 1 - Question n° 1

Soit le programme Python suivant :


       
  1. Que vaut la variable a après l'exécution de ce programme (justifiez votre réponse) ?

    Les appels récursifs dans la fonction fct(n) sont :

    a = fct(2) = 2 + fct(3) = 2 + (3 + fct(4)) = 2 + (3 + (4 + fct(5))) = 2 + (3 + (4 + (5 + fct(6))))

    Le dépilement des appels récursifs donne :

    a = 2 + (3 + (4 + (5 + 1))) = 2 + (3 + (4 + 6)) = 2 + (3 + 10) = 2 + 13 = 15

    Donc a = 15 après l'exécution du programme.

  2. Ecrire une version itérative de cette fonction.

    
              

Domaine : Récursivité 1 - Question n° 2

Soit le programme Python suivant :


       
  1. Que vaut la variable a après l'exécution de ce programme (justifiez votre réponse) ?

    Les appels récursifs dans la fonction fct(n) sont :

    a = fct(5) = 5 - fct(4) = 5 - 4 - fct(3) = 5 - 4 - (3 - fct(2)) = 5 - 4 - (3 - (2 - fct(1)) = 5 - 4 - (3 - (2 - (1 - fct(0))) = 5 - 4 - (3 - (2 - (1 - 0)))

    Le dépilement des appels récursifs donne :

    a = 5 - 4 - (3 - (2 - 1)) = 5 - 4 - (3 - 1) = 5 - 4 - (-2) = 1 + 2 = 3

    Donc a = 3 après l'exécution du programme.

  2. Ecrire une version itérative de cette fonction.

    
              

Domaine : Récursivité 1 - Question n° 3

Soit le programme Python suivant :


       
  1. Que vaut la variable a après l'exécution de ce programme (justifiez votre réponse) ?

    Les appels récursifs dans la fonction fct(n) sont :

    a = fct(2) = 2 - fct(3) = 2 - (3 - fct(4)) = 2 - (3 - (4 - fct(5)) = 2 - (3 - (4 - (5 - fct(6)) = 2 - (3 - (4 - (5 - 0)))

    Le dépilement des appels récursifs donne :

    a = 2 - (3 - (4 - (5 - 0))) = 2 - (3 - (4 - 5)) = 2 - (3 - (-1)) = 2 - (3 + 1) = 2 - 4 = -2

    Donc a = -2 après l'exécution du programme.

  2. Ecrire une version itérative de cette fonction.

    
              

Domaine : Récursivité 1 - Question n° 4

Soit le programme Python suivant :


       
  1. Que vaut la variable a après l'exécution de ce programme (justifiez votre réponse) ?

    Les appels récursifs dans la fonction fct(n) sont :

    a = fct(4) = 4 + fct(3) = 4 + (3 + fct(2)) = 4 + (3 + (2 + fct(1)) = 4 + (3 + (2 + (1 + fct(0))) = 4 + (3 + (2 + (1 + 0)))

    Le dépilement des appels récursifs donne :

    a = 4 + (3 + (2 + 1)) = 4 + (3 + 3) = 4 + 6 = 10

    Donc a = 10 après l'exécution du programme.

  2. Ecrire une version itérative de cette fonction.

    
              

Domaine : Récursivité 2 - Question n° 5

La suite de Syracuse est définie par :

avec $u_0$ un entier quelconque plus grand que 1.

  1. Ecrire une fonction itérative syracuse_iterative(u_n)

    qui affiche les valeurs successives de la suite $u_n$ tant que $u_n$ est plus grand que 1.

  2. Ecrire une fonction récursive syracuse_récursive(u_n)

    qui affiche les valeurs successives de la suite $u_n$ tant que $u_n$ est plus grand que 1.


          

La conjecture de Syracuse affirme que quelle que soit la valeur de $u_0$, il existe un indice n dans la suite tel que $u_n = 1$

Cette conjecture défie toujours les mathématiciens ...

Domaine : Récursivité 2 - Question n° 6

L'algorithme d'Euclide permet de déterminer le PGCD (le plus Grand Diviseur Commun) de deux entiers non nuls.

Il est basé sur une suite de divisions euclidiennes.

PGCD(a,b) = PGCD(b,r) avec r le reste dans la division euclidienne de a par b.

Exemple : PGCD(546,462) = PGCD(462,84) car 546 = 462x1 + 84 (84 est le reste de la division euclidienne de 546 par 462).

On réitère le processus : PGCD(462,84) = PGCD(84,42) car 462 = 84x5 + 42 (42 est le reste de la division euclidienne de 462 par 84.)

On réitère le processus : PGCD(84,42) = PGCD(42,0) car 84 = 42x2 + 0 (0 est le reste de la division euclidienne de 84 par 42.)

L'algorithme s'arrête lorsque le reste obtenu est nul.

Et le PGCD est alors le dernier reste non nul.

Ecrire une fonction Python itérative nommée PGCD_iteratif(a,b) qui implémente l'algorithme de calcul du PGCD des entiers a et b.


          

Domaine : Plus de place sur la clef USB - Question n° 7

Plus beaucoup de place sur ta clef USB ?

Nous disposons d'une clef USB bien remplie sur laquelle il ne reste que 5 Go de libre. Nous souhaitons copier sur cette clef des fichiers vidéos pour l'emporter en voyage. Chaque fichier a un poids et chaque vidéo a une durée. La durée n'est pas proportionnelle à la taille car les fichiers sont de formats différents (avec des taux de compression différents. Le tableau qui suit présente les 7 fichiers disponibles avec les durées données en minutes.

NomDurée en minPoids
Vidéo A1144,57 Go
Vidéo B802,71 Go
Vidéo C32630 Mo
Vidéo D201,65 Go
Vidéo E182,15 Go
Vidéo F5320 Mo
Vidéo G485 Mo

Problème : Quelles vidéos copier sur la clef USB pour que la durée des vidéos soient la plus grande possible tout en ne dépassant pas un poids de 5 Go ?

  1. Quelle est la valeur que l'on cherche à maximiser/minimiser ? Quelle est la contrainte ?

    On cherche à maximiser la durée totale des vidéos copiées sur la clef USB.

    La contrainte est la taille restante sur la clef USB. La taille cumulée des vidéos copiées sur la clef USB ne doit pasd dépasser 5 Go.

  2. Quel problème reconnaissez-vous ici ?

    On reconnait le problème du sac à dos.

Dans le programme Python ci-dessous, vous trouverez deux fonctions :


       

       

Les données sur les vidéos (nom, durée en minutes et poids en Go) sont modélisées par 3 listes :

  1. Etudiez le code de la fonction remplit_clef et donner le type d'algorithme utilisé par cette fonction.

  2. Il s'agit d'un problème d'optimisation comme celui du sac à dos traité avec un algorithme glouton.

  3. Dans le corps de la fonction remplit_clef_recur, remplacez dans les lignes avec des pointillés par un code Python correct.

    
              

Domaine : Plus de place sur la clef USB - Question n° 8

Plus beaucoup de place sur ta clef USB ?

Nous disposons d'une clef USB bien remplie sur laquelle il ne reste que 5 Go de libre. Nous souhaitons copier sur cette clef des fichiers vidéos pour l'emporter en voyage. Chaque fichier a un poids et chaque vidéo a une durée. La durée n'est pas proportionnelle à la taille car les fichiers sont de formats différents (avec des taux de compression différents. Le tableau qui suit présente les 7 fichiers disponibles avec les durées données en minutes.

NomDurée en minPoids
Vidéo A1144,57 Go
Vidéo B802,71 Go
Vidéo C32630 Mo
Vidéo D201,65 Go
Vidéo E182,15 Go
Vidéo F5320 Mo
Vidéo G485 Mo

Problème : Quelles vidéos copier sur la clef USB pour que la durée des vidéos soient la plus grande possible tout en ne dépassant pas un poids de 5 Go ?

  1. Quelle est la valeur que l'on cherche à maximiser/minimiser ? Quelle est la contrainte ?

    On cherche à maximiser la durée totale des vidéos copiées sur la clef USB.

    La contrainte est la taille restante sur la clef USB. La taille cumulée des vidéos copiées sur la clef USB ne doit pasd dépasser 5 Go.

  2. Quel problème reconnaissez-vous ici ?

    On reconnait le problème du sac à dos.

Dans le programme Python ci-dessous, vous trouverez deux fonctions :


       

       

Les données sur les vidéos (nom, durée en minutes et poids en Go) sont modélisées par une liste nommée liste_videos dont les éléments sont des tuples de la forme (nom_video,duree_video,poids_video).

  1. Etudiez le code de la fonction remplit_clef et donner le type d'algorithme utilisé par cette fonction.

    Il s'agit d'un problème d'optimisation comme celui du sac à dos traité avec un algorithme glouton.

  2. Dans le corps de la fonction remplit_clef_recur, remplacez dans les lignes avec des pointillés par un code Python correct.

    
                     

Domaine : ReplIt 1 - Question n° 9

Sur votre compte ReplIt traiter le projet nommé Somme des entiers impairs.

Ne pas oublier de cliquer sur "Submit" une fois votre programme codé, commenté et testé.

En utilisant votre programme, donner le résultat de somme_entiers_impairs(liste_cubes).


          

Domaine : ReplIt 1 - Question n° 10

Sur votre compte ReplIt traiter le projet nommé Produit des entiers pairs.

Ne pas oublier de cliquer sur "Submit" une fois votre programme rédiger

En utilisant votre programme, donner le résultat de produit_entiers_pairs(liste_carres).


          

Domaine : Bonus : ReplIt 2 - Question n° 11

Sur votre compte ReplIt traiter le projet nommé Nombres parfaits.

Ne pas oublier de cliquer sur "Submit" une fois votre programme codé, commenté et testé.


         

Domaine : Bonus : ReplIt 2 - Question n° 12