Algorithmique et programmation

Donner la valeur de chaque expression Python. Pour un flottant, écris par exemple 2,5.

1. Après b = 6 puis b = 2 * b + 1, b vaut
   Le membre de droite est calculé avec l’ancienne valeur : $2\times 6+1=13$, puis $13$ remplace $6$ dans b.
2. 23 // 4 vaut
   $23=4\times 5+3$ : // donne le quotient de la division euclidienne, $5$.
3. 23 % 4 vaut
   Avec la même division $23=4\times 5+3$, % donne le reste, $3$ (il est bien inférieur à 4).
4. 2 ** 5 vaut
   ** est la puissance : $2^5=2\times 2\times 2\times 2\times 2=32$.
5. 7 / 2 vaut
   La division / donne un flottant : 3.5, c’est-à-dire $3,5$. Le quotient entier 7 // 2 vaudrait 3.

Donner le type de chaque valeur : écris int, float, str ou bool.

1. 4.0 est de type
   Le point fait de 4.0 un flottant, même si sa valeur est entière.
2. "12" est de type
   Entre guillemets, c’est une chaîne de caractères : on ne peut pas faire de calcul avec, sauf après int("12").
3. 10 // 3 est de type
   // entre deux entiers donne un entier : 10 // 3 vaut 3.
4. 5 > 8 est de type
   Une comparaison est un booléen : 5 > 8 vaut False.
5. 9 / 3 est de type
   / donne toujours un flottant : 9 / 3 vaut 3.0, pas 3.

On considère le script suivant, dont les lignes sont numérotées de 1 à 6.

a = 5
b = 12
a = a + b
b = a - b
a = a - b
print(a, b)

1. Valeur de a après la ligne 3 :
   Ligne 3 : a = a + b calcule $5+12=17$ et le range dans a ; b vaut toujours 12.
2. Valeur de b après la ligne 4 :
   Ligne 4 : b = a - b calcule $17-12=5$ avec les valeurs du moment ($a=17$, $b=12$).
3. Valeur de a affichée par la ligne 6 :
   Ligne 5 : a = a - b calcule $17-5=12$. Le script affiche 12 5.
4. Justifier que ce script échange les valeurs de a et b, quelles que soient ces valeurs. Contrôle : avec a = 31 et b = 9 en lignes 1 et 2, la valeur finale de b est
   Rédaction attendue. On note $x$ et $y$ les valeurs de départ de a et b. Ligne 3 : a vaut $x+y$. Ligne 4 : b vaut $(x+y)-y=x$. Ligne 5 : a vaut $(x+y)-x=y$. À la fin, a contient $y$ et b contient $x$ : les valeurs sont échangées, sans troisième variable. Avec $x=31$ et $y=9$, b vaut 31 à la fin.

On considère l’algorithme écrit en langage naturel ci-dessous.

x ← 4
y ← x²
x ← y − 3x
y ← y + x

1. À la fin, y vaut
   On suit les lignes : $x=4$ ; $y=4^2=16$ ; $x=16-3\times 4=4$ ; $y=16+4=20$.
2. On remplace la première ligne par x ← 10. À la fin, x vaut
   $y=100$, puis $x=100-3\times 10=70$ (et $y$ vaut ensuite $100+70=170$).
3. Pour quelle valeur de départ de x, strictement positive, la valeur finale de x est-elle 0 ?
   La valeur finale de x est $x^2-3x=x(x-3)$. Ce produit est nul pour $x=0$ ou $x=3$ ; la valeur strictement positive est 3.
4. Démontrer que, pour une valeur de départ $x$, la valeur finale de y est $2x^2-3x$. Contrôle : avec x ← 5 au départ, y vaut à la fin
   Rédaction attendue. Ligne 2 : y vaut $x^2$. Ligne 3 : x reçoit $x^2-3x$ (calculé avec l’ancienne valeur de x). Ligne 4 : y reçoit $x^2+(x^2-3x)=2x^2-3x$. Contrôle : $2\times 25-15=35$ (on trouve bien $y=25$, puis $x=10$, puis $y=35$).

On a exécuté y = 12. Que vaut chaque condition ? Écris True ou False.

1. y % 5 == 2 vaut
   $12=5\times 2+2$ : le reste vaut 2, la condition est vraie.
2. y > 3 and y < 10 vaut
   and exige que les deux conditions soient vraies ; or $12<10$ est faux.
3. not (y == 12) vaut
   y == 12 est vrai, et not donne le contraire : False.
4. y <= 12 or y > 20 vaut
   or demande qu’une seule condition soit vraie : $12⩽12$ est vrai (inégalité large).

Un magasin accorde une remise de 5 % sur toute commande d’au moins 30 €, et de 10 % sur toute commande d’au moins 60 €.

def prix(m):
    if m >= 60:
        return m * 0.9
    elif m >= 30:
        return m * 0.95
    else:
        return m

1. prix(24) renvoie
   $24⩾60$ et $24⩾30$ sont faux : on arrive au else, qui renvoie 24 (pas de remise).
2. prix(45) renvoie
   Le premier test est faux, le second vrai : la fonction renvoie $45\times 0,95=42,75$.
3. prix(60) renvoie
   $60⩾60$ est vrai (inégalité large) : $60\times 0,9=54$.
4. Justifier que l’ordre des deux tests est important. Contrôle : si l’on testait m >= 30 en premier, le client paierait € pour une commande de 72 €
   Rédaction attendue. Une commande de 72 € vérifie les deux conditions. Seul le bloc du premier test vrai est exécuté : avec m >= 30 en premier, la fonction renvoie $72\times 0,95=68,4$ et s’arrête, sans voir le test m >= 60. Le client perdrait sa remise de 10 % : le bon prix est $72\times 0,9=64,8$. On teste donc la condition la plus restrictive en premier. (Python affiche 68.39999999999999 : les flottants sont codés de façon approchée.)

Un cinéma utilise la fonction suivante (âge en années, prix en euros).

def tarif(age):
    if age < 14:
        return 5
    elif age <= 25:
        return 7.5
    else:
        return 11

1. tarif(14) renvoie
   $14<14$ est faux, $14⩽25$ est vrai : la fonction renvoie 7,5.
2. tarif(26) renvoie
   $26<14$ et $26⩽25$ sont faux : on arrive au else.
3. Une famille compte deux enfants de 9 et 13 ans, une étudiante de 19 ans et un adulte de 45 ans. Prix total : €
   $5+5+7,5+11=28,5$ : les deux enfants ont moins de 14 ans, l’étudiante est dans le cas elif, l’adulte dans le else.
4. Justifier qu’échanger les deux premiers tests (age <= 25 testé avant age < 14) change les prix. Contrôle : un enfant de 9 ans paierait alors €
   Rédaction attendue. Pour 9 ans, le premier test devenu age <= 25 est vrai : la fonction renvoie 7,5 et s’arrête. Le test age < 14 n’est jamais atteint pour un enfant, qui ne paie plus jamais 5 €. Le cas « moins de 14 ans » est inclus dans « au plus 25 ans » : il doit être testé en premier.

Une année est bissextile lorsqu’elle est divisible par 4 sans l’être par 100, ou lorsqu’elle est divisible par 400.

def bissextile(a):
    c1 = a % 4 == 0 and a % 100 != 0
    c2 = a % 400 == 0
    return c1 or c2

1. bissextile(2100) renvoie
   2100 est divisible par 4 mais aussi par 100, donc c1 est faux ; $2100=400\times 5+100$, donc c2 est faux. La fonction renvoie False.
2. bissextile(2000) renvoie
   c1 est faux (2000 est divisible par 100), mais $2000=400\times 5$ : c2 est vrai, et or renvoie True.
3. Justifier que bissextile(1900) renvoie False, alors que 1900 est un multiple de 4. Contrôle : 1900 % 400 vaut
   Rédaction attendue. 1900 est divisible par 4 et par 100 ($1900=100\times 19$), donc c1 vaut False. De plus $1900=400\times 4+300$ : le reste vaut 300, il n’est pas nul, donc c2 vaut False. Les deux conditions reliées par or sont fausses : la fonction renvoie False.

Compléter.

1. Nombre de tours de for k in range(3, 17): :
   k va de 3 à 16 : $17-3=14$ tours.
2. Dernière valeur prise par k dans range(5, 40, 5) :
   k vaut 5, 10, …, 35 ; la valeur suivante, 40, est la borne exclue.
3. Nombre de valeurs de range(20, 0, -4) :
   Le pas est négatif : 20, 16, 12, 8, 4. La borne 0 est exclue : 5 valeurs.
4. Pour parcourir les entiers de 1 à 50 inclus, on écrit range(1, n) avec n =
   La borne de droite est exclue : pour que 50 soit atteint, il faut écrire range(1, 51).

On considère le script suivant.

S = 0
for k in range(1, 8):
    S = S + k * k
print(S)

1. Nombre de tours de boucle :
   range(1, 8) parcourt 1, 2, …, 7 : 7 tours.
2. Valeur affichée :
   $S=1+4+9+16+25+36+49$ ; de proche en proche : 1 ; 5 ; 14 ; 30 ; 55 ; 91 ; 140.
3. Pour obtenir la somme des carrés des entiers de 1 à 20, on remplace 8 par
   Il faut que k prenne la valeur 20 : la borne exclue devient 21.
4. Valeur affichée par ce nouveau script :
   Le script ajoute les carrés de 1 à 20 et affiche 2 870, résultat que l’on peut contrôler avec la formule admise ${\displaystyle \frac{n(n+1)(2n+1)}{6}}$ pour $n=20$.

Le premier mois, Léo dépose 20 € sur un compte ; chaque mois, il dépose 15 € de plus que le mois précédent.

d = 20
S = 0
for m in range(12):
    S = S + d
    d = d + 15
print(S)

1. Montant déposé le troisième mois : €
   20 € le premier mois, 35 € le deuxième, 50 € le troisième : d augmente de 15 à chaque tour.
2. Valeur de d après la boucle :
   La boucle fait 12 tours et ajoute 15 à chaque tour : $20+12\times 15=200$. (Le dernier dépôt, celui du 12e mois, vaut 185 €.)
3. Valeur affichée :
   S cumule les 12 dépôts : $12\times 20+15\times (0+1+\dots +11)=240+15\times 66=1230$.
4. Justifier ce que fait le script si l’on indente print(S) sous le for. Contrôle : nombre de valeurs affichées
   Rédaction attendue. Indenté, print(S) fait partie du bloc de la boucle : il est exécuté à chaque tour, après la mise à jour de S. Le script affiche alors les 12 totaux successifs (20, 55, 105, …, 1 230), au lieu du seul total final.

On considère le script suivant, qui contient une boucle dans une boucle.

for i in range(1, 5):
    for j in range(i, 5):
        print(i, j)

1. Nombre de lignes affichées :
   Pour i = 1, j va de 1 à 4 (4 lignes) ; pour i = 2, de 2 à 4 (3 lignes) ; puis 2 lignes et 1 ligne. Total : $4+3+2+1=10$.
2. Nombre de couples affichés dont la somme i + j est paire :
   $i+j$ est pair lorsque i et j ont la même parité : (1 ; 1), (1 ; 3), (2 ; 2), (2 ; 4), (3 ; 3), (4 ; 4). Il y en a 6.
3. On remplace les boucles par range(1, n + 1) et range(i, n + 1). Démontrer que le script affiche ${\displaystyle \frac{n(n+1)}{2}}$ lignes. Contrôle : pour n = 20, nombre de lignes
   Rédaction attendue. Pour une valeur de i, la boucle intérieure parcourt les entiers de i à n : elle fait $n-i+1$ tours. Le total est $N=n+(n-1)+\dots +2+1$. On écrit cette somme deux fois, l’une à l’envers : $2N=(n+1)+(n+1)+\dots +(n+1)$, avec $n$ termes, donc $2N=n(n+1)$ et $N={\displaystyle \frac{n(n+1)}{2}}$. Pour $n=20$ : $N={\displaystyle \frac{20\times 21}{2}}=210$.

On considère le script suivant.

n = 1
while n < 100:
    n = n * 3
print(n)

1. Valeur affichée :
   n vaut 1, 3, 9, 27, 81, puis 243. Comme $243<100$ est faux, la boucle s’arrête : le script affiche 243.
2. Nombre de tours de boucle :
   Il faut 5 multiplications par 3 pour passer de 1 à 243 : 5 tours.
3. On remplace n < 100 par n < 81. Valeur affichée :
   Quand n vaut 81, la condition $81<81$ est fausse : la boucle s’arrête tout de suite, et le script affiche 81.

Un capital de 2 400 € est placé à intérêts composés au taux annuel de 3,5 % : chaque année, il est multiplié par 1,035.

def annees():
    c = 2400
    n = 0
    while c <= 3000:
        c = c * 1.035
        n = n + 1
    return n

1. Capital au bout d’un an : €
   $2400\times 1,035=2484$.
2. annees() renvoie
   Le capital est multiplié par 1,035 chaque année : 2 484,00 ; 2 570,94 ; 2 660,92 ; 2 754,06 ; 2 850,45 au bout de 5 ans. Il reste inférieur ou égal à 3 000 € au bout de 6 ans et le dépasse pour la première fois au bout de 7 ans : la condition c <= 3000 devient alors fausse, et la fonction renvoie 7.
3. Capital atteint à ce moment, arrondi au centime : €
   $2400\times 1,{035}^7\approx 3053,47$ €.
4. Justifier qu’une boucle for ne convient pas ici. Contrôle : capital au bout de 6 ans, arrondi à l’euro : €
   Rédaction attendue. Une boucle for exige de connaître le nombre de tours avant de commencer. Or ce nombre d’années est justement ce que l’on cherche : il dépend du seuil de 3 000 €. Seule une boucle while, qui s’arrête quand sa condition devient fausse, permet de le trouver. Au bout de 6 ans, $2400\times 1,{035}^6\approx 2950$ €, encore inférieur à 3 000 € : la boucle continue.

On considère le script suivant.

n = 1000
c = 0
while n % 2 == 0:
    n = n // 2
    c = c + 1
print(n, c)

1. Valeur finale de c :
   1 000 est pair, puis 500, puis 250 ; 125 est impair : la boucle s’arrête après 3 divisions par 2.
2. Valeur finale de n :
   $1000÷2÷2÷2=125$, qui est impair.
3. Avec n = 96 au départ, c vaut à la fin
   96, 48, 24, 12, 6 sont pairs ; on obtient 3, impair, après 5 divisions : $96=2^5\times 3$.
4. Justifier que la boucle s’arrête pour tout entier de départ n ≥ 1. Contrôle : avec n = 1984, c vaut à la fin
   Rédaction attendue. Tant que la boucle tourne, n est un entier pair non nul, et n // 2 est un entier positif strictement plus petit que n. Une suite d’entiers positifs strictement décroissante ne peut pas continuer indéfiniment : n finit par être impair (au pire, il atteint 1), et la condition devient fausse. Pour 1 984 : 992, 496, 248, 124, 62, 31 ; 31 est impair, donc c vaut 6 ($1984=2^6\times 31$).

Un élève voulait afficher la première valeur de n supérieure ou égale à 10.

n = 0
while n != 10:
    n = n + 3
print(n)

1. Justifier que ce script ne s’arrête jamais, puis le corriger. Contrôle : avec while n < 10:, le script affiche
   Rédaction attendue. n prend les valeurs 0, 3, 6, 9, 12, 15… : ce sont des multiples de 3, et 10 n’en est pas un. n saute par-dessus 10, la condition n != 10 reste toujours vraie : boucle infinie. Avec l’inégalité n < 10, la boucle s’arrête à la première valeur qui n’est pas inférieure à 10, soit 12.
2. On garde while n != 10: mais on remplace n = n + 3 par n = n + 2. Nombre de tours effectués :
   n vaut 0, 2, 4, 6, 8, 10 : 10 est atteint après 5 tours, et la boucle s’arrête.
3. On garde n = n + 3 et while n != 10:, mais on part de n = 1. Nombre de tours effectués :
   n vaut 1, 4, 7, 10 : la boucle s’arrête après 3 tours. Le même test peut s’arrêter ou non selon la valeur de départ : on préfère une inégalité.

On définit la fonction suivante.

def k(x):
    return 5 - x ** 2

1. k(3) renvoie
   $5-3^2=5-9=-4$.
2. k(-1) renvoie
   Le paramètre x vaut $-1$, donc x ** 2 vaut $(-1{)}^2=1$ : $5-1=4$.
3. k(0.5) renvoie
   $5-0,5^2=5-0,25=4,75$.
4. k(2) + k(1) vaut
   Chaque appel vaut la valeur renvoyée : $k(2)=1$ et $k(1)=4$, donc la somme vaut 5.

On considère la fonction $f$ définie sur $ℝ$ par $f(x)=x^2-5x+3$, programmée ainsi :

def f(x):
    return x ** 2 - 5 * x + 3

for x in range(-1, 5):
    if f(x) < 0:
        print(x)

1. f(-1) renvoie
   $(-1{)}^2=1$ et $-5\times (-1)=5$, donc l’image vaut $1+5+3=9$.
2. f(2) renvoie
   $2^2=4$ et $5\times 2=10$, donc l’image vaut $4-10+3=-3$.
3. Nombre d’entiers affichés par le script :
   x va de $-1$ à 4. Les images sont 9 ; 3 ; −1 ; −3 ; −3 ; −1 : elles sont strictement négatives pour x = 1, 2, 3 et 4. Le script affiche 4 entiers.
4. Plus petit entier affiché :
   $f(-1)=9$ et $f(0)=3$ sont positifs ; $f(1)=1-5+3=-1$ est négatif : le premier entier affiché est 1.

La vitesse moyenne (en km/h) est la distance d (en km) divisée par la durée t (en h).

def vitesse(d, t):
    return d / t

1. vitesse(150, 2) renvoie
   d vaut 150 et t vaut 2 : $150÷2=75$ km/h. Python affiche 75.0, car / donne un flottant.
2. vitesse(2, 150) renvoie, arrondi au centième,
   Les arguments sont inversés : d vaut 2 et t vaut 150, d’où $2÷150\approx 0,01$. Le calcul est faux, car l’ordre des arguments est celui des paramètres.
3. Justifier qu’avec print(d / t) à la place de return d / t, l’instruction v = vitesse(150, 2) + 10 provoque une erreur. Avec return, v vaudrait
   Rédaction attendue. Avec print, la fonction affiche 75.0 mais ne renvoie rien : l’appel vaut None, et None + 10 est impossible (erreur de type). Avec return, l’appel vaut 75.0 et v vaut $75+10=85$.

On lit les deux fonctions suivantes, qui renvoient la moyenne et l’écart type de trois nombres.

from math import sqrt

def moyenne(a, b, c):
    return (a + b + c) / 3

def ecart(a, b, c):
    m = moyenne(a, b, c)
    d1 = (a - m) ** 2
    d2 = (b - m) ** 2
    d3 = (c - m) ** 2
    v = (d1 + d2 + d3) / 3
    return sqrt(v)

1. moyenne(11, 14, 17) renvoie
   $(11+14+17)÷3=42÷3=14$.
2. Lors de l’appel ecart(11, 14, 17), la variable v vaut
   m vaut 14, et $v={\displaystyle \frac{(-3{)}^2+0^2+3^2}{3}}={\displaystyle \frac{18}{3}}=6$.
3. ecart(11, 14, 17) renvoie, arrondi au centième,
   La fonction renvoie $\sqrt{6}\approx 2,45$.
4. Justifier que ecart(a + 5, b + 5, c + 5) renvoie la même valeur que ecart(a, b, c). Contrôle : ecart(16, 19, 22) arrondi au centième vaut
   Rédaction attendue. Si l’on ajoute 5 aux trois nombres, leur moyenne augmente aussi de 5 : ${\displaystyle \frac{(a+5)+(b+5)+(c+5)}{3}}=m+5$. Les écarts $(a+5)-(m+5)=a-m$, … sont inchangés, donc v et sa racine carrée aussi. Ainsi ecart(16, 19, 22) = ecart(11, 14, 17) $\approx 2,45$.

On a écrit from random import randint, random. Compléter. Pour une probabilité, écris un nombre décimal.

1. Plus grande valeur que peut renvoyer randint(3, 8) :
   randint inclut ses deux bornes : il renvoie un entier de 3 à 8.
2. Nombre d’entiers que peut renvoyer randint(5, 15) :
   Les entiers de 5 à 15, bornes comprises : il y en a $15-5+1=11$.
3. Probabilité que randint(1, 8) renvoie un nombre pair :
   Les 8 valeurs sont équiprobables ; 4 sont paires (2, 4, 6, 8) : ${\displaystyle \frac{4}{8}}=0,5$.
4. Probabilité que la condition random() < 0.3 soit vraie :
   random() tombe au hasard dans $[0;1[$ : la condition est vraie avec la probabilité 0,3. C’est ainsi que l’on simule un événement de probabilité 0,3.

Une urne contient 25 boules numérotées de 1 à 25, indiscernables au toucher : celles numérotées de 1 à 9 sont rouges, les autres sont bleues. On tire une boule au hasard.

from random import randint

def rouge():
    return randint(1, 25) <= 9

def frequence(n):
    c = 0
    for i in range(n):
        if rouge():
            c = c + 1
    return c / n

1. Probabilité de tirer une boule rouge :
   Le tirage est équiprobable : 9 boules rouges sur 25, soit ${\displaystyle \frac{9}{25}}=0,36$.
2. Pour simuler une boule bleue, on écrit randint(1, 25) > m avec m =
   Les boules bleues portent les numéros 10 à 25, c’est-à-dire les numéros strictement supérieurs à 9.
3. Lors d’un appel frequence(1000), c vaut 362 à la fin de la boucle. La fonction renvoie
   Elle renvoie ${\displaystyle \frac{362}{1000}}=0,362$, une fréquence proche de la probabilité 0,36, sans lui être égale.

On tire un entier au hasard entre 1 et 100 et l’on s’intéresse à l’événement « il dépasse 80 ».

from random import randint

def estimation(n):
    c = 0
    for i in range(n):
        if randint(1, 100) > 80:
            c = c + 1
    return c / n

1. Nombre d’entiers favorables entre 1 et 100 :
   Les entiers 81, 82, …, 100 : il y en a $100-80=20$.
2. Probabilité de l’événement :
   Équiprobabilité : ${\displaystyle \frac{20}{100}}=0,2$. Pour $n$ grand, estimation(n) renvoie une valeur proche de 0,2.
3. Pour estimer la probabilité de tirer un multiple de 10, on remplace la condition par randint(1, 100) % 10 == r avec r =
   Un entier est multiple de 10 lorsque son reste dans la division par 10 est nul.
4. Deux appels de estimation(10000) renvoient 0,1974 puis 0,2038. Justifier que ces résultats ne contredisent pas le calcul. Contrôle : écart entre 0,2038 et la probabilité :
   Rédaction attendue. Une simulation tire les nombres au hasard : la fréquence obtenue fluctue d’un appel à l’autre autour de la probabilité. Les écarts, $0,2-0,1974=0,0026$ et $0,2038-0,2=0,0038$, sont petits devant 0,2 : ils sont compatibles avec le hasard. Une fréquence n’est jamais « la » probabilité, seulement une valeur approchée.

Un élève répond au hasard à un QCM de 4 questions ; chaque question a 4 choix, dont un seul est juste. La fonction suivante simule son nombre de bonnes réponses (le choix juste est noté 1).

from random import randint

def score():
    s = 0
    for q in range(4):
        if randint(1, 4) == 1:
            s = s + 1
    return s

1. Plus grande valeur que peut renvoyer score() :
   La boucle fait 4 tours et s augmente au plus de 1 par tour : au maximum 4 bonnes réponses.
2. Probabilité que score() renvoie 4, en fraction :
   Chaque réponse est juste avec la probabilité ${\displaystyle \frac{1}{4}}$, indépendamment des autres. Sur l’arbre, le chemin « juste, juste, juste, juste » a pour probabilité ${\left({\displaystyle \frac{1}{4}}\right)}^4={\displaystyle \frac{1}{256}}$. (règle du chemin d’un arbre pondéré, chapitre Probabilités)
3. Pour obtenir la moyenne des scores sur n QCM simulés, on écrit s = s + score() dans une boucle de n tours, puis return s / .... On divise par
   s est la somme des n scores ; leur moyenne est cette somme divisée par le nombre de valeurs, n.
4. Un élève tape randint(1, 4) < 1 au lieu de randint(1, 4) == 1. Justifier que score() renvoie alors toujours la même valeur :
   Rédaction attendue. randint(1, 4) renvoie un entier de 1 à 4, jamais un entier strictement inférieur à 1. La condition est donc toujours fausse, s n’augmente jamais, et la fonction renvoie toujours 0.