Exercices corrigés - Algorithmes : écrire et analyser des algorithmes en maths

n=0
H=0
Tant que (H<a) faire
  n=n+1
  H=H+1/n
Fin tant que
Afficher n.

n=1
H=0
Tant que (H<a) faire
  H=H+1/n
  n=n+1
Fin tant que
Afficher n-1.

def pascettelimite():
    S=1
    n=1
    while (S<1.2020560199):
        n=n+1
        S=S+1/n**3
    print(n)

VARIABLES : 
  p entier
  r entier
  u,v réel
Traitement
  p=0,9
  r=1
  u=p^r-1/r
  v=u
  Tant que (u<=v) faire
    u=v
    r=r+1
    v=p^r-1/r
  Fin Tant Que.
  Afficher r-1  

1. D'après la relation de Chasles, on sait que $$\int_0^1 f(t)dt=\sum_{k=0}^{n-1}\int_{k/n}^{(k+1)/n}f(t)dt.$$ Mais, puisque $f$ est croissante, pour tout $t\in\left[\frac kn,\frac{k+1}n\right]$, on a $$f(t)\geq f(k/n)\implies \int_{k/n}^{(k+1)/n}f(t)dt\geq \int_{k/n}^{(k+1)/n}f(k/n)dt\geq\frac 1n f(k/n).$$ Il suffit de sommer ces relations pour $k$ allant de $1$ à $n$ pour trouver que $U_n\leq \int_0^1 f(t)dt$. La preuve est similaire pour $V_n$.
2. On sait que $$0\leq \int_0^1 f(t)dt-U_n\leq V_n-U_n.$$ Pour que $U_n$ soit une valeur approchée (par défaut) à $10^{-3}$ près de $\int_0^1 f(t)dt$, il suffit que $V_n-U_n\leq 10^{-3}$. Notre algorithme va donc calculer les valeurs de $U_n$ et $V_n$ jusqu'à ce que cette condition soit remplie.

   n=1
   Répète
     U=0
     V=0
     Pour k allant de 0 à n-1 faire
        U=U+exp((k*k)/(n*n))/n
        V=V+exp(((k+1)*(k+1))/(n*n))/n
     Fin pour
     n=n+1
   Jusqu'à ((V-U)<0.001)
   Afficher U
   

   Codé en Python, ceci donne la fonction suivante :

   def integral(ecart):
        n=0
        u=0
        v=1
        while ((v-u)>ecart):
             u=0
             v=0
             n=n+1
             for k in range(n):
                  u=u+math.exp((k*k)/(n*n))/n
                  v=v+math.exp((k+1)*(k+1)/(n*n))/n
        return (u,v,n)
   

1. On a $I_0=e-1$. Pour obtenir la relation de récurrence, on va faire une intégration par parties, en posant $u'(x)=\exp(x)$ et $v(x)=(1-x)^{n+1}$, de sorte que $u(x)=\exp(x)$ et $v'(x)=-(n+1)(1-x)^n$. On trouve \begin{align*} I_{n+1}&=\left[ e^x (1-x)^{n+1}\right]_0^1 +(n+1)\int_0^1 e^x (1-x)^n dx\\ &=(n+1)I_n-1. \end{align*}
2. En utilisant $I_0=e-1$, une fonction qui convient est la suivante :

   from math import *
   
   def suite(n):
       I=exp(1)-1;
       for k in range(n):
           I=(k+1)*I-1
       return I
   

   L'utilisation de cet algorithme donne des valeurs décroissantes pour $I_n$, positives pour $n\leq 17$ et négatives pour $\geq 18$ (en particulier, $suite(18)\simeq -0.8702$). Si on continue, il semble que la suite tende vers $-\infty$, puisque $suite(100)\simeq -1.35\times 10^{142}$.
3. Soit $n\in\mathbb N$. Remarquons que, pour tout $x\in [0,1]$, on a $0\leq (1-x)\leq 1$, et donc $$0\leq (1-x)^{n+1}\leq (1-x)^n.$$ On multiplie par $e^x$ (qui est positif), puis on intègre entre $0$ et $1$ pour trouver $$0\leq I_{n+1}\leq I_n.$$ On vient donc de prouver que la suite $(I_n)$ est décroissante. De plus, elle est minorée par $0$. Elle est donc convergente. Notons $\ell$ sa limite, avec $\ell\geq 0$. On peut écrire aussi la relation $I_{n+1}=(n+1)I_n-1$ sous la forme $$\frac{I_{n+1}}{n+1}=I_n-\frac{1}{n+1}.$$ Passant à la limite dans cette égalité, on trouve que $\ell=0$. La conjecture est donc fausse!
   Pour prouver que $\ell=0$, on pouvait aussi observer que, pour tout $x\in [0,1]$, $$0\leq e^x(1-x)^n \leq e (1-x)^n$$ et donc $$0\leq I_n\leq \int_0^1 e (1-x)^n dx=\frac e{n+1}.$$ Par le théorème des gendarmes, $(I_n)$ tend vers $0$.
4. C'est immédiat! \[ J_{n+1}-I_{n+1}=(n+1)J_n-1-\big((n+1)I_n-1\big)=(n+1)\big(J_n-I_n\big). \]
5. Une récurrence rapide démontre que, pour tout $n\in\mathbb N$, $$J_n-I_n=n! (J_0-I_0)=n! (a-e+1).$$ Puisque $(I_n)$ tend vers $0$, la suite $(J_n)$
   • tend vers $0$ si $a=e-1$;
   • tend vers $+\infty$ si $a>e-1$;
   • tend vers $-\infty$ si $a<e-1$.
6. Python ne pouvait pas permettre de formuler une bonne conjecture. En effet, il ne connait pas la valeur exacte de $e$, mais seulement une valeur approchée. Et pour la formule de récurrence donnée, la seule suite qui tend vers $0$ est celle pour laquelle le premier terme vaut exactement $e$. Partant d'un mauvais premier terme (même si l'approximation est très bonne!), on a l'impression que la suite tend vers $-\infty$.

1. Par l'inégalité des pentes, on sait que, pour tout $x\leq a_1$, on a $$\frac{f(a_1)-f(x)}{a_1-x}\leq \frac{f(a_2)-f(a_1)}{a_2-a_1}=\mu\leq 0.$$ Ainsi, $f(a_1)\leq f(x)$, et la fonction atteint son minimum sur $[a_1,a_3]$.
2. Cette fois, l'inégalité des pentes nous dit que, pour tout $x\geq a_2$, on a $$0<\mu=\frac{f(a_2)-f(a_1)}{a_2-a_1}\leq\frac{f(x)-f(a_2)}{x-a_2}.$$ Ainsi, $f(x)\geq f(a_2)$, et $f$ atteint son minimum sur $[a_0,a_2]$.

3. from math import *
   
   def f(x):
       return exp(x)+x*x
   
   def minimum(eps):
       a0=-1
       a3=0
       while (a3-a0>eps):
           a1=(2*a0+a3)/3
           a2=(a0+2*a3)/3
           mu=(f(a2)-f(a1))/(a2-a1)
           if (mu>0):
               a3=a2
           else:
               a0=a1
       return [a0,a3]
   

   Remarquons que l'algorithme se termine car la taille de l'intervalle est multiplié par $2/3$ à chaque étape.

b=0
Tant que a>0 faire
   b=10b+reste(a,10)
   a=quotient(a,10)
Retourner b

1. On utilise le fait que $p$ divise $q$ si et seulement si le reste dans la division euclidienne de $q$ par $p$ est nul.

   def divise(p,q):
       if ( (q%p) == 0):
            return True
       else:
           return False
   

2. Un entier naturel est premier si ses seuls diviseurs positifs sont $1$ et lui-même, et s'il n'est pas égal à $1$. On sépare donc le traitement de $1$, et pour les autres, on regarde si un des entiers entre $2$ et $p-1$ divise $p$.

   def estpremier(p):
       if (p<2):
           return 0
       for i in range(2,p):
           if divise(i,p):
               return 0
       return 1
   

3. def phi(n):
       total=0
       for m in range(2,n+1):
           total+=estpremier(m)
       return total
   

Pour y allant de 0 à 100
  z=sqrt(1+2y*y)
  Si z=Ent(z) afficher(z,y)
Fin pour.

1. Cette question est évidemment destinée à comprendre comment proposer un algorithme pour la question suivante. L'idée est de partir d'abord du dernier chiffre. En effet, si 21 s'écrit $b_k\dots b_1$ en base 2, alors on a $$21=b_k2^k+b_{k-1}2^{k-1}+\dots+2b_2+b_1,$$ et donc $b_1$ est le reste dans la division par 2 de 17. On a donc $$21=2\times 10+1.$$ On continue avec 10 : $$10=2\times 5+0,$$ soit $$21=2^2\times 5+2^1\times 0+1.$$ On reprend avec 5 : $$5=2\times 2+1,$$ soit $$21=2^3\times 2+2^2\times 1+2^1\times 0+1,$$ soit finalement $$21=2^4\times 1+2^3\times 0+2^2\times 1+2^1\times 0+1.$$ Ainsi, 21 s'écrit en base 2 : $10101$.
2. Voici un algorithme possible. Il met les chiffres successifs dans une liste. Puis on lit la liste en sens contraire...

   Lire n
   i=0
   tant que (n>0) faire 
     l[i]=reste(n,2)
     n=(n-l[i])/2
     i=i+1
   Fin tant que
   Pour j allant de i-1 jusque 0 faire
     Afficher l[j]
   Fin tant que.
   

1. On traite le cas $n=1$ séparément, puis on utilise l'algorithme proposé par l'énoncé. On teste tous les nombres entre $2$ et $\sqrt n$ pour voir s'ils divisent $n$. Si c'est le cas pour un entier, on retourne $\textrm{False}$. Sinon, on retourne $\textrm{True}$.

   def estPremier(n):
       if (n<2):
            return False
       d=2
       while ((d*d)<=n):
           if ( (n%d)==0):
                return False
           d+=1
       return True
   

2. On parcourt tous les nombres compris entre 2 et $n$, et on les ajoute à la liste s'ils sont premiers.

   def liste_premiers(n):
       l=[]
       for d in range(2,n+1):
           if (estPremier(d)):
                l.append(d)
       return l
   

3. On initialise un entier $s$ à $0$. On augmente $s$ de $1$ à chaque fois que $p$ divise $n$, et on divise $n$ par $p$.

   def valuation_p_adique(n,p):
       s=0
       while ((n%p)==0):
           s+=1
           n=n/p
       return s
   

4. Avec la même idée :

   def val(n,p):
       if ((n%p)==0):
           return val(n/p,p)+1
       else:
           return 0
   

5. On parcourt la liste des premiers inférieurs ou égaux à $n$, et on ajoute ce premier $p$ et la valuation $p$-adique de $n$ à la liste si toutefois cette valuation est strictement positive.

   def decomposition_facteurs_premiers(n):
       l=liste_premiers(n)
       liste=[]
       for p in l:
           vp=val(n,p)
           if vp>0:
               liste.append( [p,vp] )
       return liste
   

from random import *

def simulX():
  instant=0
  k=1
  while (k!=2):
    instant=instant+1
    if (k==1):
      k=randint(1,4)
    else:
      k=k-1
  return instant

import random

def soiree(n,p):
    c=0
    for i in range(n):
        if (random.random()<p):
            c=c+1
    return c
    
def repetitions(nb):
    succes=0
    for i in range(nb):
        if (soiree(70,0.4)<=30):
            succes=succes+1
    return (succes/nb)

def horner(P,x):
    n=len(P)
    valeur=0
    for i in range(n-1,-1,-1):
        valeur=valeur*x+P[i]
    return valeur

def horner(P,x):
    n=len(P)
    valeur=P[n-1]
    for i in range(n-2,-1,-1):
        valeur=valeur*x+P[i]
    return valeur

1. Soit $i,k\in\{0,\dots,n+1\}$. On remarque que $L_i(x_k)=0$ (car un des termes du produit est nul) sauf si $k=i$. Dans ce cas, tous les termes du produit sont égaux à $1$, et $L_i(x_i)=1$. On en déduit que $$P(x_k)=\sum_{i=0}^n y_i L_i(x_k)=y_k L_k(x_k)=y_k.$$ Ainsi, $P$ est bien un polynôme interpolateur.
2. On commence par écrire une fonction intermédiaire que calcule $L_i(a)$.

   def poly_lagrange(x,i,a):
       #renvoie L_i(a) où L_i est le i-ème polynôme de Lagrange associé à la liste x
       resultat=1
       for k in range(0,len(x)):
           if (k!=i):
             resultat=resultat*(a-x[k])/(x[i]-x[k])
       return resultat
       
   def lagrange(x,y,a):
       resultat=0
       for k in range(0,len(x)):
           resultat=resultat+y[k]*poly_lagrange(x,k,a)
       return resultat
   

1. Il s'agit de la liste $[0,1,3,2]$.

2. def comp(s1,s2):
       L=[]
       for i in range(len(s1)):
           L.append(s1[s2[i]])
       return L
   

3. def inv(s):
       L=[]
       for i in range(len(s)):
           L.insert(s[i],i)
       return L
   

4. Il suffit de vérifier que $G$ est non vide, stable par passage à l'inverse et par produit.

   def groupe(G):
       if (len(G)==0):
           return False
       for i in range(len(G)):   # on teste si G est stable par inverse
           if (inv(G[i]) not in G):
               return False
       for i in range(len(G)):  # on teste si G est stable par produit
           for j in range(len(G)):
               if (comp(G[i],G[j]) not in G):
                   return False
       return True
   

5. On commence par créer une fonction qui vérifie si une permutation est égale à l'identité. Le groupe engendré par $\sigma$ est ensuite l'ensemble $\{\sigma,\sigma^2,\dots,\sigma^k\}$ de sorte que $\sigma^{k+1}$ est l'identité. On calcule donc toutes les puissances de $\sigma$ jusqu'à obtenir l'identité.

   def identite(s):
       for i in range (len(s)):
           if (s[i]!=i):
               return False
       return True
   
   def cyclique(s):
       G=[s]
       t=s
       while (identite(t)==False):
           t=comp(s,t)
           G.append(t)
       return G
   

1. On a $\Gamma_1=\{(1)\}$, $\Gamma_2=\{(2),(1,1)\}$, $\Gamma_3=\{(3),(2,1),(1,1,1)\}$, $\Gamma_4=\{(4), (3,1), (2,2), (2,1,1), (1,1,1,1)\}$.
2. 1. Il n'y a qu'une seule partition qui commence par un $1$ : celle qui comporte $n$ fois le chiffre $1$. Donc $y_{n,1}=1$.
   2. Lorsque $j=n$, on cherche à déterminer toutes les partitions. On les sépare en deux parties disjointes :
      • Les partitions qui commencent par un $n$ : il n'y en a qu'une, la partition $(n)$, et $y_{n-n,0}=y_{0,0}=1$.
      • Les partitions qui commencent par un nombre inférieur ou égal à $n-1$ : il y en a $y_{n,n-1}$.
      D'où $y_{n,n}=y_{n,n-1}+y_{0,0}$ qui est le résultat demandé.
   3. De la même façon, on sépare les partitions de $n$ commençant par un nombre inférieur ou égal à $j$ en deux parties disjointes :
      • les partitions commençant par $j$; il reste alors $n-j$ à partager en une partition qui commence par un nombre inférieur ou égal à $j$; il y a donc exactement $y_{n-j,j}$ telles partitions.
      • les partitions commençant par un nombre inférieur ou égal à $j-1$. Il y a exactement $y_{n,j-1}$ telles partitions.
      On a donc prouvé, pour $2\leq j\leq n-1$, la relation $y_{n,j}=y_{n,j-1}+y_{n-j,j}$. Si $j\leq n-j$, c'est exactement la relation demandée. Si $j>n-j$, alors on a $y_{n-j,j}=y_{n-j,n-j}$ (plus généralement, si $q>p$, alors $y_{p,q}=y_{p,p}$ car toute partition de $p$ qui commence par un nombre inférieur ou égal à $q$ commence en réalité par un nombre inférieur ou égal à $p$). Dans tous les cas, on a prouvé le résultat demandé.
3. En utilisant la formule démontrée à la question précédente, en utilisant un tableau, et en faisant attention aux indices et à l'initialisation (par exemple, $y_{n,0}=0$), voici une fonction possible :

   def partitions(n):
       y=[[1]]
       for i in range(1,n+1):
           y.append([0,1])
           for j in range(2,i+1):
               y[i].append(y[i][j-1]+y[i-j][min(j,i-j)])
       return y[n][n]
   

   Par exemple, un appel \verb+partitions(8)+ donne 22.

def factorielle(n):
  if (n==0) return 1
  return n*factorielle(n-1)

def binom(n,k):
    if (k>n):
         return 0
    if (k==0) or (k==n):
         return 1
    return binom(n-1,k)+binom(n-1,k-1)

1. Voici une solution :

   def suite(n):
       if n==1:
           return(1,3)
       k=n//2
       a,b=lucas4(k)
       if n%2==0:
           return (a*a+5,a*b+7)
       else:
           return (a*b+7,b*b+5)
   

   Un petit mot d'explication. Si $n$ est pair, $n$ s'écrit $n=2k$ et $a,b=u_k,u_{k+1}$. On doit retourner $u_{2k},u_{2k+1}$, ce que l'on fait avec les formules de l'énoncé. Si $n$ est impair, alors $n$ s'écrit $2k+1$ et $a,b=u_k,u_{k+1}$. On doit retourner $u_{2k+1},u_{2k+2}$ et on écrit la formule donnant $u_{2k+2}$ sous la forme $u_{2k+2}=u_{k+1}^2+5$.
2. Démontrons par récurrence sur $p\geq 1$ que si $n$ vérifie $2^p\leq n<2^{p+1}$, alors le nombre d'appels récursifs que réalise suite(n) est exactement égal à $p$.
   Initialisation : si $p=1$, soit $n=2$ ou $n=3$, alors $k=1$, et la fonction suite(n) appelle récursivement suite(1) qui ne fait plus d'appels récursifs.
   Hérédité : soit $p\geq 2$ tel que la propriété soit vraie au rang $p$. Soit $n$ tel que $2^{p+1}\leq n<2^{p+2}$. Alors le $k$ calculé dans la fonction vérifie $2^{p}\leq k<2^{p+1}$. De plus, suite(n) appelle récursivement suite(k). Par hypothèse de récurrence, cette dernière fonction fera $p$ appels récursifs. La fonction suite(n) fera donc en tout $p+1$ appels récursifs, et la propriété est vraie au rang $p+1$.
   Par le principe de récurrence, on a donc démontré que si $p$ est l'entier tel que $2^p\leq n<2^{p+1}$, alors la fonction suite(n) fera $p$ appels récursifs. On rappelle que $p$ est égal à $\lfloor\log_2 n\rfloor$.

• ou bien $n$ est pair : dans ce cas, le nombre total de multiplications effectuées par exporapide(a,n) est égal à 1 plus le nombre de multiplications effectuées par exporapide(a,n/2). Par hypothèse de récurrence, le nombre total est inférieur ou égal à $1+2+2\lfloor\log_2(n/2)\rfloor$. Mais $\log_2(n/2)=\log_2(n)-1$ et donc le nombre d'appels est majoré par $1+2+2\lfloor \log_2(n)\rfloor-2\leq 2+2\lfloor\log_2(n)\rfloor$.
• ou bien $n$ est impair : dans ce cas, exporapide(a,n) effectue deux muliplications et autant de multiplications que exporapide(a,(n-1)/2). Par hypothèse de récurrence, le nombre total de multiplications est donc majoré par $$2+2+2\lfloor\log_2((n-1)/2)\rfloor\leq 4+2\lfloor \log_2(n-1)\rfloor-2\leq 2+2\lfloor\log_2(n)\rfloor.$$

Tant que (b non nul) Faire
  r=reste de a par b
  a=b
  b=r
Fin Tant que.

x=0
Pour t allant de 1 à 50 Faire
  r=random()
  Si (r<1/3) alors x=x+1
  Si (r>=1/3) et (r<2/3) alors x=x+2
  Si (r>=2/3) alors x=x-3
Fin Pour.
Afficher x.