Concevoir

Consigne : Tous les algorithmes doivent être écrits sous forme d'une fonction en langage Python et testés avec l'ordinateur.

Les fonctions , ln sont les fonctions sqrt() et log() disponibles dans le module math  ( from math import * en début de fichier)  

1) Plus petit nombre parmi 3

Ecrire une fonction mini3(a, b, c) calculant le plus petit des trois nombres a, b et c.
Le nombre d'opérations élémentaires (comparaisons et affectations) avant le retour du résultat doit être au maximum de 3.

2) Somme des cubes

Ecrire une fonction sc(n) (avec n ∈ N) calculant le nombre entier S n = Σ k = 1 n k 3 . Vérifier que sc(111) = 38638656.

3) Série harmonique alternée

Ecrire (sans la fonction puissance) une fonction sha(n) (avec n ∈ N * ) calculant  le réel S n = Σ k = 1 n ( - 1 ) k + 1 k .
Vérifier que sha(20) = 0.6687714031754279.

4) Deux suites convergeant vers le nombre d'or

  Le nombre d'or est ϕ = 1 + 5 2 . On définit les suites ( u n ) et ( v n ) sont par u 0 = v 0 = 1 et n N , u n + 1 = 1 + 1 u n et v n + 1 = 1 + u n . On admet que ces suites convergent vers le nombre d'or.

  Ecrire une fonction suites_or(n) (avec n ∈ N) calculant les couples de réels ( u k , v k ) pour k ∈ {1,...,n}. Laquelle des suites ( u n ) ou ( v n ) converge-t-elle le plus rapidement vers ϕ ? De beaucoup ?

5) La suite de Fibonacci

La suite ( F n ) de Fibonacci est définie par F 0 = F 1 = 1 et n N , F n + 2 = F n + 1 + F n .

  a) Ecrire une fonction fibo(n) (avec n ∈ N) calculant  l'entier F n . Vérifier que fibo(20) = 10946.
  b) Ecrire une fonction suite_fibo(n) (avec n ∈ N) affichant la liste [ F 0 , F 1 , ... F n ] .

6) Moyenne arithmético-géométrique

On définit les suites ( u n ) et ( v n ) par u 0 = a et v 0 = b dans R + et les relations: n N , u n + 1 = 1 2 ( u n + v n ) et v n + 1 = u n v n .
On montre qu'elles convergent vers un réel appelé moyenne arithmético-géométrique de a et b .

Ecrire une fonction suites_ag(a, b, n) (avec a, b ∈ R + ) calculant  le triplet de réels ( u n , v n , u n - v n ) .
Par exemple, suites_ag(1, 100, 5) = (26.21668872060001, 26.21668871984983, 7.501803622744774e-10)
Constater sur des exemples la convergence extrêmement rapide de ces suites.

7) Année bissextile

  On rappelle que n est une année bissextile si n est divisible par 4, mais pas par 100, exception faite des années n divisibles par 400 qui sont bissextiles. Ecrire (en une ligne) une fonction à valeur booléenne bissextile(n) (avec n ∈ N) valant True si et seulement si  l'année n est bissextile.

8) Factorisation partielle d'un entier

  Ecrire une fonction facto_partielle(n) (avec n ∈ N) affichant la chaîne de caractères “n = 2^p x q” avec (p, q) le couple d'entiers tel que n = 2 p × q avec q impair.

Par exemple, facto_partielle(1000) = “1000 = 2^3 x 125”.

9) Le plus petit sinus

Ecrire une fonction mini_sin(n) (avec n ∈ N) calculant l'entier p ∈ {1,...,n} pour lequel |sin(p)| est minimum.
Vérifier que mini_sinus(500) = 113.

10) Division euclidienne

  Ecrire une fonction div_eucl(a,b) (avec a ∈ N et b ∈ N * ) affichant la chaîne de caractères “a = bxq+ r” où (q, r)  est le couple d'entiers tels que a = bq + r  avec 0 ≤ r < b , sans utiliser les opérateurs *, /, //, %, .

Par exemple, div_eucl(1000, 31) = “1000 = 31 x 32 + 8”

11) Calcul de l'âge d'une personne

Ecrire une fonction calcul_age(jn, mn, an, jc, mc, ac) (les paramètres sont des nombres entiers possibles) calculant le triplet d'entiers (a, m, j) donnant l'âge d'une personne en  jours, mois et années.
Cette personne est née le jn / mn / an et le jour du calcul est le jc / mc / ac.
Dans un premier temps, on pourra faire l'hypothèse que tous les mois ont 30 jours, puis dans un second temps on tiendra compte des mois de différentes longueurs et d'une éventuelle année bissextile. Par exemple:

calcul_age(15, 7, 1928, 30, 6, 2014)renvoie:
Date de naissance:  15 / 7 / 1928
Date de calcul:  30 / 6 / 2014
Age:  85 ans 10 mois 15 jours

12) Factorielle

Ecrire une fonction facto(n) (n ∈ N) calculant l'entier n! . Par exemple facto(20) = 2432902008176640000.

13) Combinaisons

Ecrire une fonction combi(p,n) calculant et affichant l'entier ( n p ) pour des entiers n et p tels que 0 ≤ p ≤ n.

On rappelle que lorsque , on a pour 0 < p n : ( n p ) = n ( n - 1 ) ( n - 2 ) ... ( n - p + 1 ) 1 2 3 .. p , et que ( n 0 ) = 1

L'objectif est de ne pas utiliser de factorielle et faire une unique boucle “for”.
On veut que le résultat soit un entier, donc on ne peut pas utiliser la division / sur les réels qui provoque des erreurs d'arrondis, mais seulement la division entière // .  Par exemple, combi(5, 12) = 792 .

14) Nombre premier

Un entier n ≥ 2 est premier lorsque ses seuls diviseurs entiers sont 1 et n .
Les plus petits nombres premiers sont 2,3,5,7,11,13,19,...

On rappelle qu'un entier n 2 est premier lorsqu'il n'a aucun diviseur d compris entre 2 et [ n ] .

a) Ecrire une fonction à valeurs booléennes test_premier(n) (avec n ∈ N et n ≥ 2) valant True si et seulement si n est premier .

b) Ecrire une fonction plus_petit_diviseur(n) (avec n ∈ N et n ≥ 2) calculant le plus petit diviseur d > 1 de n.

On demande d'écrire ces deux fonctions avec une boucle “while”.

15) Factorisation d'un entier

Ecrire une fonction factorisation(n) (avec n  entier ≥ 2) affichant la factorisation de n en produit de facteurs premiers.
La chaîne de caractères peut  être obtenue en concaténant les facteurs au fur et à mesure ou bien en utilisant la méthode join() sur la liste des facteurs.
Par exemple, factorisation (5040) → 5040 = (2^4) x (3^2) x 5 x 7

Des conseils pour cet exercice 15).  Il y a deux difficultés:

    (1) le calcul de la décomposition n = d 1 k 1 ... d q k q de n en facteurs premiers
    (2) le calcul de la chaîne de caractères n = (d1^k1) x ... x (dq^kq) constituant la réponse

Pour le point (1) : on va diviser n autant de fois que l'on peut par d = 2, puis par d = 3, puis par d = 4, ..., jusqu'au maximum par d = [ n ] . Si cette division par un facteur d est possible k fois, avec k ≥ 1, on récupère le facteur d k dans la décomposition de n.
A la fin des divisions, le facteur n restant est égal à 1 ou bien est premier.

L'algorithme suivant (en pseudo-code) affiche tous les couples (d, k) de la factorisation de n.

d=2
tant que d n :
    k = 0
    tant que d divise n:
        k = k + 1
        n = n / d
    si k > 0:
        afficher (d, k)
    d = d + 1
si n > 1:
    afficher (n, 1)

Pour le point (2) : on peut procéder de deux façons:

    (2a) De façon élémentaire. On fabrique par concaténations successives la chaîne de réponse rep au fur et à mesure du calcul des couples (d, k). Il faut faire attention à ne pas afficher (si k = 1), d^1, mais seulement d et à insérer les symboles x entre les d^k

    (2b) De façon plus “Pythonesque”. On stocke les couples (d, k) dans une liste que l'on traite en fin d'algorithme pour fabriquer la chaine réponse. Les méthodes format() et join() sont alors très efficaces.

© 2014 - Eric Obermeyer      Powered by      Corrigé