Sujet NSI — Terminale — Polynésie — Bac 2022

EXERCICE 1 (4 points) Cet exercice traite du thème «programmation», et principalement de la récursivité. On rappelle qu'une chaîne de caractères peut être représentée en Python par un texte entre guillemets "" et que : • la fonction len renvoie la longueur de la chaîne de caractères passée en paramètre ; • si une variable ch désigne une chaîne de caractères, alors ch[0] renvoie son premier caractère, ch[1] le deuxième, etc. ; • l'opérateur + permet de concaténer deux chaînes de caractères. Exemples : >>> texte = "bricot" >>> len(texte) 6 >>> texte[0] "b" >>> texte[1] "r" >>> "a" + texte "abricot" On s'intéresse dans cet exercice à la construction de chaînes de caractères suivant certaines règles de construction. Règle A : une chaîne est construite suivant la règle A dans les deux cas suivants: • soit elle est égale à "a" ; • soit elle est de la forme "a"+chaine+"a", où chaine est une chaîne de caractères construite suivant la règle A. Règle B : une chaîne est construite suivant la règle B dans les deux cas suivants : • soit elle est de la forme "b"+chaine+"b", où chaine est une chaîne de caractères construite suivant la règle A ; • soit elle est de la forme "b"+chaine+"b", où chaine est une chaîne de caractères construite suivant la règle B. On a reproduit ci-dessous l'aide de la fonction choice du module random. >>>from random import choice >>>help(choice) Help on method choice in module random: choice(seq) method of random.Random instance Choose a random element from a non-empty sequence. La fonction A() ci-dessous renvoie une chaîne de caractères construite suivant la règle A, en choisissant aléatoirement entre les deux cas de figure de cette règle. 22-NSIJ1PO1 2/16 def A(): if choice([True, False]): return "a" else: return "a" + A() + "a" 1. a. Cette fonction est-elle récursive ? Justifier. b. La fonction choice([True, False]) peut renvoyer False un très grand nombre de fois consécutives. Expliquer pourquoi ce cas de figure amènerait à une erreur d'exécution. Dans la suite, on considère une deuxième version de la fonction A. À présent, la fonction prend en paramètre un entier n tel que, si la valeur de n est négative ou nulle, la fonction renvoie "a". Si la valeur de n est strictement positive, elle renvoie une chaîne de caractères construite suivant la règle A avec un n décrémenté de 1, en choisissant aléatoirement entre