Ús avançat de l'estructura while

En molts dels d’exemples d’introducció s’ha utilitzat el bucle while amb una condició que bàsicament serveix per comptar casos. Però el while és molt més potent i la condició pot ser qualsevol expressió booleana més o menys complexa, oferint moltes possibilitats. Només cal traduir el que necessiteu i buscar l’expressió booleana correcta.

Per començar, fareu un programa que llegeixi un nombre i digui si es tracta d’un nombre primer o no.

Es diu que un nombre és primer si els únics divisors positius són l’1 i ell mateix. Per exemple, el 5 és primer (l’1 és divisor, el 2, 3 i 4 no ho són i només torna a ser-ho el 5). En canvi, el 15 no és primer perquè té l’1, el 3, el 5 i ell mateix com a divisors.

Per a saber si un nombre és o no primer, cal buscar divisors del nombre. S’ha de començar pel 2, continuar amb el 3 i anar augmentant fins a arribar a l’anterior al mateix nombre. En aquest moment, si no s’ha trobat cap divisor, es pot assegurar que el nombre és primer. En canvi, si se’n troba algun, significa que el nombre no és primer.

Recordeu que la instrucció en Python que us diu que a és divisor de b és:

b % a == 0 

Comenceu fent uns casos a mà, per establir l’algorisme que utilitzeu. Què es fa amb el 5?

• 5 % 2 és diferent de 0. Per tant, és divisor? No
• 5 % 3 és diferent de 0. Per tant, és divisor? No
• 5 % 4 és diferent de 0. Per tant, és divisor? No

Aquests passos indiquen que el 5 és primer. Vegem que passaria amb un nombre que no és primer, com el 15?

• 15 % 2 és diferent de 0. Per tant, és divisor? No
• 15 % 3 és igual a 0. Per tant, és divisor? Si

En aquest cas, no cal continuar perquè ja heu trobat un divisor. I això indica que el 15 no és primer.

Tot i que la definició de nombre primer també es pot estendre als nombres negatius, en el programa només s’acceptaran nombres naturals majors a 1. Les especificacions d’entrada seran: Un nombre enter n > 1. El joc de proves el teniu recollit a la taula.

D’entrada, i seguint el que heu fet en els primers exemples a mà, el refinament serà:

#llegir num

#Per a cada nombre (del 2 a n - 1)
    # si és divisor
   	    # no es primer
    #passar al següent nombre
   
#mostrar

El primer nombre que heu comprovat si és o no és divisor de n és el 2. Si acabeu abans d’arribar a n, sense haver trobat divisors, el nombre és primer. En canvi, si existeix un divisor ja podeu assegurar que el nombre no és primer.

És el moment de traduir el refinament. Si es troba un divisor, el nombre deixa de ser primer. La millor manera d’expressar-ho en un llenguatge de programació és utilitzant una variable booleana que indiqui si el nombre és o no és primer. També cal modificar el seu valor en el moment en què trobeu un divisor. Aquesta variable s’anomenarà es_primer.

Es podrien comptar els divisors, però no és el mètode que s’ha utilitzat per a resoldre el problema a mà. Heu de traduir el mateix algorisme que heu fet servir. El nombre llegit es desarà en la variable n, i per cada nombre que comprovareu que sigui un divisor s’utilitzarà la variable div. Amb aquestes consideracions, el cos del bucle serà:

# si té un divisor?
	if n % div == 0:
		# no es primer
		es_primer = False
		
	#passar al seguent
	div = div + 1

La condició serà:

#Per a cada nombre (del 2 a num - 1)
while div <= n-1:

Per últim, cal inicialitzar les variables:

• div, que s’ha d’inicialitzar a dos perquè és el primer nombre que es comprova que sigui divisor.
• La variable es_primer, d’entrada ha de tenir el valor True perquè en principi el nombre és primer fins que no es demostri el contrari.

El programa quedarà així:

#llegir num
n = int(input())

div = 2
es_primer = True

#bucle per tots els nums mes petits
while div <= n - 1:
	# si té un divisor?
	if n % div == 0:
		# no es primer
		es_primer = False
		
	#passar al seguent
	div = div + 1
	
#mostrar
print(es_primer)

Funciona el programa? Si comproveu el joc de proves, obteniu els resultats desitjats.

videoioc@debian-xtec:~/Documents/programacio$ python3 nombre_primer.py 
2
True
videoioc@debian-xtec:~/Documents/programacio$ python3 nombre_primer.py 
4
False
videoioc@debian-xtec:~/Documents/programacio$ python3 nombre_primer.py 
7
True
videoioc@debian-xtec:~/Documents/programacio$ python3 nombre_primer.py 
15
False
videoioc@debian-xtec:~/Documents/programacio$ python3 nombre_primer.py 
100
False

Tot i que el programa funcioni, té un problema. És molt poc eficient i ho és perquè no s’ha aplicat l’algorisme que utilitzeu quan ho feu a mà. En aquest curs no es busca l’eficiència, però l’objectiu principal és aprendre a fer programes que repeteixin l’algorisme natural que utilitzeu. Aquest programa no ho fa.

La figura mostra el codi com es mostra a l’editor.

Fixeu-vos en l’inici del seguiment del programa per a n = 100. El joc de proves el teniu recollit a la taula.

Continuarà donant voltes fins que div arribi a 99. En canvi, l’algorisme utilitzat en els casos estudiats no feia això: en veure que el nombre 2 divideix a 100, no es continua perquè ja sabeu que el 100 no és primer.

En l’última línia (46) de la taula de seguiment anterior, taula, ja s’hauria de sortir del programa. Però encara li falten 96 voltes. El problema és que l’algorisme indica que s’han de repetir les instruccions mentre div sigui menor que n i no hàgim trobat cap divisor.Caldrà construir una condició composta.

S’ha de seguir mentre div sigui ⇐ n i mentre la variable es_primer sigui True (ja que en el moment en què passa a False ja es pot acabar). Dit d’una altra manera, esteu dins el bucle mentre (el divisor sigui menor o igual que n - 1) and (el nombre sigui primer).

while div <= n - 1 and es_primer:

El codi serà:

#llegir num
n = int(input())

div = 2
es_primer = True

#bucle per tots els div més petits
while div < = n - 1 and es_primer:
	# si es un divisor?
	if n % div == 0:
		# no es primer
		es_primer = False
		
	#passar al seguent
	div = div + 1
	
#mostrar
print(es_primer)

La figura mostra el codi com es mostra a l’editor, si feu el seguiment d’aquest nou programa en el cas del 100:

El joc de proves el teniu recollit a la taula.

Ara el programa fa exactament el que feu vosaltres: troba que el dos és divisor, surt del while i mostra el valor de la variable es_primer. Fixeu-vos en l’avaluació de la condició del while (a la línia 22), les dues vegades què hi passa:

 div < = n - 1 and es_primer 

• 1a vegada: div és 2 i es_primer és True. Els dos camps son True i el resultat també.

   2 <= 99 and True 

• 2a vegada: div és 3 i es_primer és False. El primer camp és True i el segon False. O sigui que el resultat és fals i se surt del bucle.

   3 <= 99 and False 

import math

#llegir num
n = int(input())

div = 2
es_primer = True

#bucle per tots els div més petits
while div <= math.sqrt(n) and es_primer:
	# si es un divisor?
	if n % div == 0:
		# no es primer
		es_primer = False
		
	#passo al seguent
	div = div + 1
	
#mostro
print(es_primer)

De vegades, a la variable es_primer se l’anomena bandera.

Les variables booleanes són un recurs molt potent. Però l’ús indiscriminat de banderes fa que els programes es tornin farragosos i difícils de llegir. Sempre que es recorre a l’ús d’un if i una bandera, és que es pot refer la condició del while sense la necessitat de canviar el valor de la bandera.

Estudieu, executeu i compareu aquests dos exemples:

• Programa 1:

maxim = 10

bandera = True
n = 0

while bandera:
	print(n)
	n +=2
	if n >= 10:
		bandera = False

• Programa 2:

n = 0
while n < 10:
	print(n)
	n +=2

Els dos programes fan exactament el mateix: mostrar els múltiples de 2 menors que 10. És evident que el programa 1 és millor: és molt més llegible i senzill. Només cal fer una mirada per entendre quan se sortirà del bucle. El programa 2, tot i que funciona correctament, és difícil d’entendre (a part que sembla que es defineixi un bucle infinit).

Recordeu que sempre que s’utilitza una bandera es pot modificar la condició de sortida del bucle per a fer-lo més senzill i llegible.

La programació estructurada és un paradigma de programació sobre l’escriptura de codi per programes d’ordinador. Apareix en la programació a finals de la dècada de 1950 per millorar la qualitat, claredat i el temps de desenvolupament dels programes (la llegibilitat, en altres paraules).

Originalment les instruccions s’executaven seqüencialment. Per alterar l’ordre d’execució s’utilitzava la partícula goto (o “transferència de control”). Aquests programes també s’anomenen de “codi espagueti”, o de programació no estructurada.

Segons el teorema de la programació estructurada, qualsevol funció computable es pot implementar utilitzant les tres estructures de control bàsiques:

• Estructura seqüencial.
• Estructura alternativa.
• Estructura repetitiva.

És a dir, el goto, i altres que no hem vist com el break, no són en absolut necessaris.

En aquest curs la llegibilitat un dels atributs més importants que ha de tenir el vostre codi, de manera que es prescindirà d’aquestes estructures. Quan sigueu programadors experimentats segur que les utilitzareu, però heu de saber que són totalment prescindibles i que fan que el programa sigui molt menys llegible.

En l’ús avançat del while s’ha de parlar de programes on hi ha bucles a dins d’altres bucles. La capacitat humana és limitada i poca gent és capaç de gestionar directament les instruccions i les variables quan es troba una estructura repetitiva enmig d’una altra.

En aquests casos és molt important la disciplina i atacar els bucles d’un a un: s’ha de començar fent el refinament general, però moltes vegades convé programar primer el bucle intern. S’han de separar els problemes. El més important és ocupar-nos de cada cicle per separat, fer el refinament de cada bucle d’un en un.

A través d’un exemple veurem què s’ha de fer per trobar els nombres primers menors que m. Fareu cada pas fins a crear un programa que mostri els nombres primers menors que un nombre llegit.

El millor que podem fer per a entendre un enunciat, és fer un exemple d’execució. El joc de proves el teniu recollit a la taula.

El programa haurà d’anar generant els nombres naturals (primer el 2, el 3,..), i comprovarà si són primers. Acabarà quan s’hagi d’avaluar el nombre entrat.

Si l’entrada és 10, farà els següents passos:

1. El 2 és primer? Sí → el mostra
2. El 3 és primer? Sí → el mostra
3. El 4 és primer? No
4. …

Les especificacions d’entrada son un nombre enter n > 0. I el joc de proves el teniu recollit a la taula:

Aquest és el pas més important quan els programes es comencen a complicar, i en concret quan hi ha bucles dins d’altres bucles.Si escriviu els passos de l’algorisme utilitzat quedaria així:

#1. llegir el màxim

#2. per a cada nombre (del 2 fins a màxim - 1)

    # 3. Calcular si és primer

    #4 Si és primer,  es mostra
  
    #5. Passar al següent n
 

En aquest primer refinament us heu enfrontat només amb un bucle (el que genera els nombres des del 2 fins a màxim - 1). Per a cadascun d’ells us pregunteu si és primer.

És relativament fàcil fer aquest refinament, i ara us podeu encarar amb el següent problema: veure si un nombre és primer o no. Si els ataqueu per separat, no heu de pensar en més d’un bucle cada vegada i és més senzill.

En l’exemple que ens ocupa, el primer refinament s’ha escrit el pas 3.

    # 3. Calcular si és primer

És ara quan heu de refinar aquest pas i us adoneu que hi ha un altre bucle. Vosaltres ja teniu un programa que fa aquest pas, per tant, el podeu copiar. En cas de no tenir-lo, és una bona tècnica fer primer un programa independent per resoldre aquest problema.

Copiar un programa per afegir-lo a un altre no és tan fàcil com sembla: s’ha de controlar que els noms de les variables siguin coherents en el programa original i el final, i indentar (si és necessari), les instruccions. Fixeu-vos en el programa que ja heu fet sobre si un nombre és o no és primer:

#llegir num
n = int(input())

div = 2
es_primer = True

#bucle per tots els div més petits
while div < = n - 1 and es_primer:
	# si es un divisor?
	if n % div == 0:
		# no es primer
		es_primer = False
		
	#passar al seguent
	div = div + 1
	
#mostrar
print(es_primer)

D’entrada, en aquest programa al nombre que estudieu li dieu n. En el que esteu construint haureu de mantenir el nom de la variable. Al copiar-lo haureu d’indentar tot el programa, ja que això ho feu dins d’un bucle i el nivell d’indentació no és a la primera columna, sinó a la següent.

El fragment que us interessa és des de la inicialització de la variable div fins al final del bucle. Cal recordar que en la variable es_primer és on hi ha la informació. Si incorporeu el nou programa al refinament obtindreu el següent codi:

#1. llegir el màxim

#2. per a cada nombre (del 2 fins a màxim - 1)

  # 3. Calcular si és primer
	div = 2
	es_primer = True
	
	# 3.1 bucle per tots els div més petits
	while div < = n - 1 and es_primer:
		# 3.2 si es un divisor?
		if n % div == 0:
			# 3.3 no es primer
			es_primer = False
			
		# 3.4 passar al següent
		div = div + 1
		
  #4 Si és primer,  es mostra
  
  #5. Passar al següent n	

Ara ja només falta acabar d’omplir. El programa que acabeu d’enganxar us obliga a dir-li n a la variable que va augmentant en el bucle extern. La condició i la inicialització depenen de la n i són relativament senzilles, com també ho és el punt 5 (“#5. Passar al següent n ”).

if es_primer == True:
  print(n)

Respecte al punt 4 (si és primer, es mostra), recordeu que la informació està en la variable es_primer. El codi serà tan senzill com:

	#4 Si és primer,  mostro
	if es_primer:
		print(n)

Fixeu-vos que print(n) ha d’estar indentat, ja que està dins del bucle. La versió més eficient, en la que per veure si un nombre és primer s’arriba només fins a l’arrel quadrada del nombre, és la següent:

import math

#1. llegir num
maxim = int(input())

#2. per a cada nombre del 2 
n = 2
while n < maxim :
	
	# 3. Calcular si és primer
	div = 2
	es_primer = True
	
	#3.1 bucle per tots els nums mes petits
	while div <= math.sqrt(n) and es_primer:
		#3.2 si es un divisor:
		if n % div == 0:
			#3.3 no es primer
			es_primer = False
			
		#3.4 passar al seguent
		div = div + 1
		
	#4 Si és primer,  mostrar
	if es_primer:
		print(n)
	
	#5. Passar al següent
	n = n + 1

Per acabar, cal comprovar que el programa acompleix el joc de proves.

videoioc@debian-xtec:~/Documents/programacio$ python3 primers_menors_n.py 
10
2
3
5
7

Cal fer el mateix amb els altres exemples d’execució.

Els aspectes que s’han treballat en aquesta lliçó són algunes de les eines bàsiques que fareu servir a l’hora de crear els programes per la gestió del sistema. És important que els domineu i els feu servir adequadament. Els aspectes fonamentals d’aquestes estructures els teniu a continuació.

El bucle while és l’estructura repetitiva adequada quan la sortida del bucle depèn de diverses condicions. Només cal trobar l’expressió booleana composta que tradueixi exactament les condicions que s’han de donar per seguir el cicle (o trobar la que es necessita per sortir i escriure-la amb un not davant).

Les variables booleanes se solen utilitzar per emmagatzemar informació relativa a l’estat d’altres variables. S’aconsella anomenar-les es_alguna_cosa, perquè el llenguatge no deixi ambigüitats per entendre què significa quan és True o False. Per exemple, la variable es_primer té informació relativa al nombre n que s’està estudiant.

Recordeu, també, que la instrucció variable_booleana == True és de novell i que s’ha de substituir només per variable_booleana.

Tradicionalment, s’ha anomenat bandera a una variable booleana que ajuda a sortir d’un bucle while. Es poden utilitzar tot i que no és recomanable l’abús. Sempre que s’utilitza una bandera es pot modificar la condició del while per incorporar-la, incrementant notablement la llegibilitat dels programes.

L’objectiu d’aquest curs és aprendre a programar traduint els algorismes que feu de manera natural i fer programes llegibles. Es considera que l’estructura break no manté l’ordre del codi i no és apta per la programació estructurada.

Quan tingueu temptacions d’utilitzar el break, cal que reviseu la condició del while per afegir-hi (amb una condició composta) la causa que us feia utilitzar el break.

Heu d’intentar enfrontar-vos a un sol bucle a la vegada. L’eina per anar desglossant el programa en petits bocins i separa els bucles és el refinament.