While

Croissance de la factorielle.

Soit n un entier positif.
On appelle factorielle n (et on note n!) l'entier égal au produit des entiers de 1 à n.
Écrire un programme qui :

  1. demande un entier strictement positif B,
  2. détermine et affiche le plus petit entier n tel n! > B.


B = int(input('Entrez un entier B > 0 : '))
p = 1
n = 0
while p <= B :
	n += 1
	p *= n
print('Le premier entier n tel que n! > {} est {}.'.format(B,n) )

Substitution à répétition.

Question 1.

Étudier le rôle de la méthode replace (méthode qui s'applique à un string) en testant le programme suivant. 


texte=' abracadabra gloubiboulga chabada tsoin tsoin'
texte=texte.replace('ab', 'ruv')
print(texte)

Question 2

Le rôle de cette méthode étant comprise, écrire un programme qui

  1. demande à l'utilisateur une chaîne de caractères ch1,
  2. demande à l'utilisateur une chaîne ch2,
  3. demande à l'utilisateur une chaîne ch3,
  4. remplace dans ch1 tous les ch2 par des ch3 tant qu'il y en a.

Attention, si ch1='baaac', ch2='ba' et ch3='b' alors le résultat attendu n'est pas 'baac' puisque ch2 est encore présent. L'opération de substitution doit donc être à nouveau réalisée.

Question 3

Existe-t-il des situations telles que le programme ne s'arrête jamais ?

Question 1

Lors d'une instruction texte=texte.replace(chaine1, chaine2), toutes les occurrences de chaine1 présentes dans texte sont remplacées par chaine2.

Question 2


ch1 = input('Entrez une première chaîne : ')
ch2 = input('Entrez une seconde chaîne : ')
ch3 = input('Entrez une troisième chaîne : ')

while ch2 in ch1 :
	ch1 = ch1.replace(ch2,ch3)
	
print(ch1)

Question 3

Si ch1 = 'bxdrt', ch2 = 'b' et ch3 = 'ba', alors ch1 devient 'baxdrt', puis 'baaxdrt' puis 'baaaxdrt' ... et ainsi de suite à l'infini. Il faut évidemment éviter de lancer le programme sur un tel cas, à moins d'ajouter une condition d'arrêt indépendante (par exemple en fixant un nombre maximum d'itérations.)

Suite de Conway.

Saurez-vous déterminer la logique de passage d'une ligne à l'autre dans ce qui suit :

1
11
21
1211
111221
312211
13112221
1113213211

Explication :

  1. En première ligne, on commence par la chaîne '1'.
  2. En seconde ligne, on écrit ce qu'on voit en première ligne : un '1', ce qui donne '11'.
  3. En troisième ligne, on lit ce que l'on voit dans la ligne précédente : deux '1', ce qui donne '21'.
  4. Sur la ligne suivante, on écrit de même ce que l'on voit : un '2' et un '1', ce qui donne '1211'
  5. ...et ainsi de suite.

Écrire un programme qui :

  1. demande un entier n > 0 à l'utilisateur,
  2. affiche n lignes du triangle ci-dessus. 


n = int(input(' Nombre de lignes  ? '))

chaine_totale = '1'  # désignera le triangle
chaine_ligne = '1'  # désignera une ligne du triangle

for j in range(n) :
	
	aux = chaine_ligne 
	chaine_ligne = ''    #réinitialisation à la chaîne vide pour calcul de la prochaine ligne
	while aux != '' :    # tant que la chaîne aux n'est pas vide 
		cpt = 0   # compteur pour le nombre de répétitions 
		        # du premier symbole au début de la chaîne aux
		premiere_lettre = aux[0] # premier symbole de la chaîne aux
		while (aux != '' and aux[0] == premiere_lettre) : # tant que le premier symbole
		                                              # de la chaîne reste le même
			aux = aux[1:]  # on supprime le premier symbole de la chaîne  aux 
			cpt += 1       
		chaine_ligne += str(cpt) + premiere_lettre  # on complète la ligne actuelle
		
	chaine_totale += '\n' + chaine_ligne # on ajoute la ligne qui vient d'être calculée au triangle
	
print(chaine_totale)

Quelques remarques :

  1. Ce programme est un peu plus difficile que les précédents : prenez le temps de le décortiquer et de le comprendre ( notamment si vous n'avez pas su en écrire une version !)
  2. aux désignant une chaîne de caractères, l'instruction aux[1:] a la même signification que aux[1:len(aux)] et désigne la sous-chaîne de aux constituée de toutes les lettres de aux, sauf la première.
  3. Lorsqu'un programme présente, comme celui-ci, un empilement de petites procédures techniques (compter le nombre de caractères identiques en début de mot, en déduire une nouvelle chaîne, concaténer cette chaîne avec une autre...etc), on le rend plus compréhensible en le découpant en fonctions. Nous verrons cela dans le chapitre sur les fonctions.

blog.

Soit x ≥ 1 un nombre réel. On appellera blog(x) le plus petit entier n tel que x ≤ 2n.

Écrire une fonction python prenant en entrée un float x ≥ 1 et donnant en sortie blog(x). 


def blog(x) :
	n = 0
	while x > 1 :
		x /= 2
		n += 1
	return n
	
 


for x in (1, 1.6, 2,3, 4, 7, 8, 14, 15, 16, 17) : 
	print('blog({}) = {}.'.format(x, blog(x)) )

Consulter la page sur le logarithme.

PGCD.

Pour déterminer le pgcd de deux entiers naturels a et b, on utilise les propriétés suivantes :

  1. pgcd(a,0) = 0
  2. pgcd(a,b) = pgcd(b,r) où r est le reste de la division euclidienne de a par b.

Lorsqu'on remplace pgcd(a,b) par pgcd(b,r), on remplace l'élément b par un élément strictement plus petit (et ≥ 0). En réitérant le procédé, on finit par arriver à une valeur de r égale à 0. La dernière valeur de r non nulle (qui peut éventuellement être b lui-même dans certains cas) est alors le pgcd de a et b.

En d'autres termes, le calcul du pgcd revient à remplacer le couple (a, b) par le couple (b,r) successivement jusqu'à ce que r soit nul puis à appliquer la règle 1 citée ci-dessus.

Écrire un programme qui demande deux entiers naturels a et b et détermine ensuite leur pgcd suivant le principe précédent.

Premier programme.


a = int(input('Entrez un entier naturel a : '))
b = int(input('Entrez un entier naturel b : '))


while b != 0 :
	aux = a
	a = b
	b = aux%b
	
print(a)

Second programme.

On peut en python se passer de la variable intermédiaire aux utilisée dans le programme précédent à l'aide d'affectations parallèles.

Par exemple, si l'on veut échanger les valeurs des variables a et b, il suffit d'écrire a,b=b,a en langage python (dans la plupart des autres langages, une variable auxiliaire serait nécessaire).

Cette particularité permet d'écrire un programme plus proche de notre descriptif :


a = int(input('Entrez un entier naturel a : '))
b = int(input('Entrez un entier naturel b : '))

while b != 0 :
	a,b = b, a%b
	 
print(a)