$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Exercices corrigés - Algorithmes - écrire et analyser des algorithmes

\'Ecrire des algorithmes
Enoncé
Écrire une fonction qui prend en entrée un entier naturel $a$ et retourne cet entier écrit à l'envers. Par exemple, si $a=1234$, la fonction devra retourner $a=4321$. On pourra utiliser les fonctions quotient(n,p) et reste(n,p) qui donnent le quotient et le reste de la division de n par p.
Corrigé
Enoncé
On note $H_n$ la somme $H_n=\sum_{k=1}^n \frac 1k$. On admet que $(H_n)$ tend vers $+\infty$. Écrire un algorithme qui détermine le plus petit entier $n$ tel que $H_n$ dépasse un réel $a$ donné.
Corrigé
Exercice 3 - Équation de Pell-Fermat [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
On considère l'équation $x^2-2y^2=1$ d'inconnues $x,y\in\mathbb N^*$. Écrire un algorithme permettant de déterminer toutes les solutions de cette équation pour lesquelles $y\leq 100$.
Corrigé
Enoncé
On pose $p=0,9$, et on admet que la fonction $x\mapsto p^x-\frac{1}x$ est croissante sur $[1,a]$ et décroissante sur $[a,+\infty[$, où $a>1$. Écrire un algorithme permettant de déterminer pour quelle valeur de l'entier $r$ le nombre $p^r-\frac 1r$ est maximal.
Corrigé
Exercice 5 - Simulation d'une rangée de spots [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Une rampe verticale de spots nommés de bas en haut $S_1,\ S_2,\ S_3,\ S_4$ change d'état de la manière suivante :
  • à l'instant $t=0$, le spot $S_1$ est allumé.
  • si, à l'instant $t=n,\ n\geq 0$, le spot $S_1$ est allumé, alors un (et un seul) des spots $S_1,\ S_2,\ S_3,\ S_4$ s'allume à l'instant $t=n+1$, et ceci de manière équiprobable.
  • si, à l'instant $t=n,\ n\geq 0$, le spot $S_k$ ($2\leq k\leq 4$) est allumé, le spot $S_{k-1}$ s'allume à l'instant $t=n+1$.
On pourra remarquer qu'à chaque instant, un et un seul spot est allumé. On note $X$ la variable aléatoire représentant le premier instant (s'il existe) où le spot $S_2$ s'allume. Écrire un algorithme simulant le fonctionnement de la variable aléatoire $X$. On supposera que l'on dispose d'une fonction ALEA(a,b) qui simule une loi uniforme discrète sur l'ensemble $\{a,a+1,\dots,b\}$.
Indication
Corrigé
Enoncé
  1. Écrire 21 en base 2.
  2. Proposer un algorithme qui prend en entrée un entier $n$ et retourne son écriture en base 2.
Indication
Corrigé
Exercice 7 - Encadrement d'intégrale [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $f:[0,1]\to\mathbb R$ une fonction croissante. Pour $n\geq 1$, on pose $$U_n=\frac 1n\sum_{k=0}^{n-1}f(k/n)\textrm{ et }V_n=\frac 1n\sum_{k=1}^{n}f(k/n).$$
  1. Démontrer que, pour tout $n\geq 1$, on a $U_n\leq \int_0^1 f(x)dx\leq V_n$.
  2. On admet que $(U_n)$ et $(V_n)$ convergent vers $\int_0^1 f(x)dx$. Écrire un algorithme donnant une valeur approchée de $\int_0^1 e^{-x^2}dx$ à $10^{-3}$ près.
Indication
Corrigé
Analyser des algorithmes
Enoncé
L'algorithme suivant propose de calculer le pgcd de deux entiers $a$ et $b$, avec $a>b$. Fonctionne-t-il? Sinon, corriger cet algorithme.


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

Corrigé
Enoncé
Une puce se déplace sur un axe gradué. Au temps $t=0$, la puce est en 0. Si la puce est en $x$, à l'instant $n+1$, elle est en $x+1$ avec probabilité $1/3$, en $x+2$ avec probabilité $1/3$, en $x-3$ avec probabilité $1/3$. On souhaite programmer un algorithme simulant la position de la puce après 50 itérations. On propose l'algorithme suivant :


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

Cet algorithme fonctionne-t-il? Sinon, le corriger (la fonction random() retourne un nombre (pseudo)-aléatoire entre 0 et 1).

Corrigé
Exercice 10 - Triplets pythagoriciens [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Voici l'énoncé posé à des étudiants : ``On rappelle qu'un triplet d'entiers naturels $(a,b,c)$ est un triplet pythagoricien si $a^2+b^2=c^2$. Écrire un algorithme donnant tous les triplets pythagoriciens de sorte que $a+b+c\leq 10000$.''
Voici les réponses de quelques étudiants. Déterminer les algorithmes qui donnent le bon résultat. Expliquer.
Étudiant 1 :


Pour k1 allant de 0 à 10000 faire
  Pour k2 allant de 0 à 10000 faire
     Pour k3 allant de 0 à 10000 faire
         Si $k1^2+k2^2=k3^2$ et k1+k2+k3<=10000 alors afficher (k1,k2,k3)
         Fin Si
     Fin pour
  Fin pour
Fin pour.

Étudiant 2 :


a=0, b=0,c=0
Pour b allant de 0 à 10000
  $a^2+b^2\to c$.
  Si a+b+sqrt(c)<10000 et sqrt(c) entier alors afficher (a,b,sqrt(c))
  c=0;
  a=a+1;
Fin Pour.

Étudiant 3 :


a=0, b=0, c=0
Tant que a+b+c<=10000 faire
  Tant que a+b+c<=10000 faire
      afficher(a,b,c)
      b=b+1
      c=sqrt(a*a+b*b)
  Fin tant que
  a=a+1
  b=0
Fin tant que.

Étudiant 4 :


Pour a allant de 0 à 10000 faire
  Pour b allant de 0 à 10000-a faire
     Pour c allant de 0 à 10000-a-b faire
         Si a*a+b*b=c*c afficher (a,b,c) Fin si
     Fin pour
   Fin pour.
Fin pour.

Étudiant 5 :


a=0, b=0
Tant que a+b+sqrt(a*a+b*b)<=10000 faire
  b=0
  Tant que a+b+sqrt(a*a+b*b)<=10000 faire
      Si Ent(sqrt(a*a+b*b))=sqrt(a*a+b*b) alors afficher (a,b,sqrt(a*a+b*b))
      Fin si
      b=b+1
  Fin tant que
  a=a+1
Fin tant que.

Étudiant 6 :


Pour a allant de 0 à 10000 faire
   Pour b allant de 0 à 10000 faire
      c=0
      Tant que a+b+c<=10000 faire
         si a*a+b*b=c*c alors afficher (a,b,c)
         sinon c=c+1
      Fin tant que
   Fin pour.
Fin pour.

Corrigé
Enoncé
Dans l'exercice donné aux étudiants, on considère la suite $(S_n)$ définie par $$S_n=\sum_{k=0}^n \frac{(-1)^k}{k+1}.$$ On a prouvé que $(S_n)$ converge vers une limite $\ell$, et que, si on pose $u_n=S_{2n}$ et $v_n=S_{2n+1}$, alors pour tout entier $n$, on a $u_n\leq \ell\leq v_n$. Il est demandé aux étudiants d'écrire un algorithme donnant un encadrement de $\ell$ d'amplitude inférieur ou égal à $0.001$. Voici leurs réponses. Analysez-les.
Étudiant 1 :


n:=2
u:=5/6
v:=7/12
Tant que u-v>0.001 faire
  u=u-1/2n+1/(2n+1)
  v=u-1/(2n+2)
Fin Tant que
Retourner u et v.

Étudiant 2 :


a=1
c=1/2
n=0
b=a
d=c
tant que (a-c>0.001) faire
  n=n+1
  b=a
  a=b+(-1})/(2n+1)+1/(2n+2)
  d=c
  c=d+1/(2n+2)-1/(2n+3)
Afficher a et b

Étudiant 3 :


Entrées :  
u=1
v=1/2
n=0
Traitement :
Tant que (v-u>0.001)  
  n=n+1
  u=u+somme{k=0 à 2n}(-1)^k/(k+1)
  v=v+somme{k=0 à 2n+1}(-1)^k/(k+1)
Sortie : u,v

Étudiant 4 :


Variables : u,v,n,k
Initialisation :
u=1
v=1/2
k=0
n=0
Traitement :
Tant que (u-v>0.001) faire
  Pour k allant de 1 à 2n faire
     u=u+(-1)^k/k+1
  Pour k allant de 1 à 2n+1 faire
     v=v+(-1)^k/{k+1}
  n=n+1
Sortie : Afficher u,v

Étudiant 5 :


Variables : a,b,n,u,v
Initialisation :
u=1
v=1/2
a=1/2
b=1
Traitement
Tant que (a>0.001)  
  n=n+1
  a=1/(2n+2)
  b=1/(2n+1)
  u=v+b
  v=u-a
Sortie : u,v

Étudiant 6 :


s=0
t=0
Pour k=0 à 1000 faire
  s=s+(-1)^k/(k+1)
Fin Pour.
t=t+(-1)^(1001)/1002
Afficher s,t

Corrigé