Tresavis

Benvinguts al blog de tresavis de noves tecnologies i més.

Correu : tresavis3@gmail.com

☰ Pràctiques ☰ Articles

Matemàtiques.

En aquesta practica es plantejant dos problemes matemàtics. El primer el quadre màgic 3x3 i el segon el problema que nomem divisibilitat.

Fem servir el llenguatge de programació PYTHON i utilitzem el editor de codi SPYDER.

Quadre màgic 3x3.

Emplenar la resta de caselles del quadre tal que les sumes de les files sigui igual a les sumes de les columnes i també a les sumes de les diagonals. En cada casella el nombre te que ser diferent.

Aquest problema es va donar per deures a 4º de ESO.

Després de intentar fer manualment els càlculs sense arribar a cap resultat, s'ha implementat un petit programa informàtic, desenvolupat en llenguatge PYTHON.

Algorisme.

Les caselles del quadre màgic s'han nomenat c de casella i la fila i la columna corresponent.

El programa el que fa es iterar els valors de la casella c13 des de 0 fins a 100.

A cada nou valor de c13, suma la primera fila, suma=c11+c12+c13.

Calcula c33, c33=suma-c13-c23.

Calcula c22, c22=suma-c11-c33.

Igual fins obtenir totes les caselles.

Sumem la ultima diagonal i si es igual a la suma de la primera fila, tenim un resultat.

Pot haver mes d'un resultat o cap.

Codi.

quadreMagic.py

          
# -*- coding: utf-8 -*-    
'''
casseles per fila columna
'''    
c11=10
c12=18 
c13=0 
c21=0 
c22=0
c23=2
c31=0
c32=0
c33=0  
'''
sumas de les files, de les columnes i de les diagonals
a partir de sumaFila1, obenim per ordre les altres caselles
per finalitzar comprovem si sumaF1 es igual a sumaDiagonal1
si es veritat imprimim
''' 
sumF1=0
sumD2=0
'''
bucle de 0 a 100
'''
for i in range(100):
    c13=i
    sumF1=c11+c12+c13
    #sumaF1 igual per totes les sumas
    c33=sumF1-c13-c23
    c22=sumF1-c11-c33
    c21=sumF1-c22-c23
    c32=sumF1-c12-c22
    c31=sumF1-c11-c21
    
    sumD2=c13+c22+c31
    if sumD2==sumF1:
        print(str(c11)+" | "+str(c12)+" | "+str(c13)+ "\n"+
              str(c21)+" | "+str(c22)+" | "+str(c23)+ "\n"+
              str(c31)+" | "+str(c32)+" | "+str(c33)+ "\n\n")

Resultat.

El resultat es:

Que no compleix amb les especificacions de quadre màgic, perquè es repeteixen els nombres en les caselles. Podem afirmar que el problema amb les dades donades, no te solució.

Si les dades del enunciat les canviem, com es mostra en el següent quadre, si que te solució.

Nou enunciat del problema, canviant els paràmetres d’entrada:

Tornem a executar el nostre programa, canviant el paràmetres inicials. El resultat que don es el següent:

Solució manual.

Com podem arribar a la mateixa solució manualment:

Tenim la següent sèrie de 9 nombres: 2,4,6,8,10,12,14,16,18, es una sèrie aritmètica de distancia 2, que contè els paràmetres del enunciat del problema (en color).

Els col·loquem de seguen manera, ampliem el quadre en 2 files i 2 columnes mes.

El primer numero de la sèrie, el 2, el posem a dalt i al mig i seguim posant els números de la sèrie en diagonal, 2,4,6, després 8,10,12 i per últim 14,16,18, tal com es mostra la següent taula.

Els nombres de fora del quadre vermell els posem a dins del quadre, en les caselles mes oposades en direcció vertical o horitzontal.

I ja tenim el resultat.

Problema de la divisibilitat.

Tenim el rang de números del 1 al 9 : 1 2 3 4 5 6 7 8 9.

Trobar una combinació dels 9 números, que compleixi amb les següents restriccions:

1.- El numero format per els 2 primers, començant per l’esquerra ha de ser múltiple de 2.

2.- Els 3 primers per l’esquerra ha de ser múltiple de 3.

3.- Els 4 primers per l’esquerra ha de ser múltiple de 4.

4.- Els 5 primers per l’esquerra ha de ser múltiple de 5.

5.- Els 6 primers per l’esquerra ha de ser múltiple de 6.

6.- Els 7 primers per l’esquerra ha de ser múltiple de 7.

7.- Els 8 primers per l’esquerra ha de ser múltiple de 8.

8.- Els 9 números ha de ser múltiple de 9.

9.- Tots el números han de ser diferents, no poden ser repetits.

Estudi previ.

Creem una llista [1,2,3,4,5,6,7,8,9].

El primer numero pot ser qualsevol, excepte el 5.

El segon te que ser parell [2,4,6,8] .

El tercer te que ser tal que primer + segon + tercer sigui múltiple de 3, en un rang de 7 números, perquè ja tenim ocupats dos dels 9 dígits, en el primer i en el segon.

El quart, les dues ultimes xifres tenen que ser múltiple de 4, les possibles combinacions son : 12,16,24,28,32,36,44,48,64,68,72,76,84,88,92,96, son 16 possibilitats.

El cinquè nomes pot ser el 5.

El sisè, te que ser parell i la suma dels 6 dígits múltiple de 3, te que estar en [2,4,6,8].

El setè, la regla de divisibilitat de 7 diu: un numero es múltiple de 7 quan la suma dels productes dels dígits de la sèrie [1, 3, 2, –1, –3, –2, 1] por los dígits de las unitats, desenes, centenes,... del número a provar es 0 o múltiple de 7. Nomes queda 3 números perquè la resta ja està agafada

El vuitè, un numero es divisible per 8 si els tres últims dígits son múltiple de 8. Te que ser parell. Les combinacions son : 128,136,152,168,176,184,192,216,248,256,264,372,384,392,....

El novè, la suma dels dígits ha de ser múltiple de 9.

El segon, el quart, el sisè i el vuitè tenen que ser parells, la resta senars.

Tenim el operador mod que don la resta de una divisió, x mod y= a la resta de x/y

Si x mod y=0 => x es múltiple de y

Algorisme eficient.

Començant per l’esquerre, el primer dígit està entre la llista dels senars, el segon llista dels parells i successivament, el cinquè nomes pot ser 5.

primer = [1,3,7,9]

segon = [2,4,6,8]

tercer = [1,3,7,9], tal que la suma dels dígits te que ser múltiple de 3.

quart = [2,4,6,8], tal que les dues ultimes xifres tenen que ser múltiples de 4.

cinquè = 5

sisè = [2,4,6,8], tal que la suma dels 6 dígits múltiple de 3.

setè = [1,3,7,9], apliquem el operador mod al numero sencer.

vuitè = [2,4,6,8], tal que els tres últims dígits son múltiple de 8.

novè = [1,3,7,9] i la suma dels dígits ha de ser múltiple de 9.

Apliquem 8 bucles niats, cada bucle assigna un valor a cada lloc de la sèrie. En el tercer bucle posem un condicional, si la suma del primer, segon i tercer, el seu mòdul es 0, li assignem el valor al tercer lloc i continuem amb el pròxim bucle. En el bucle per el quart lloc, apliquem la regla de divisibilitat, assignem el numero al quart lloc i continuem. I successivament amb tots el bucles.

En el resultat final, per que no surtin els números que tenen dígits repetits, convertim la llista en un set, que te la propietat de no acceptar repetits i comprovem la longitud de la llista original i del set, si coincideixen les longituds, vol dir que la llista original no te repetits i podem imprimir-la com a resultat.

Contem les iteracions de cada bucle i les imprimim al final. També contem el temps d’execució del programa, per fer comparacions dels dos codis, el eficient i el de força bruta.

Codi eficient.

divisibilitatEficient.py

          
# -*- coding: utf-8 -*-
from time import time
start_time = time()
primer= [1,3,7,9]
segon = [2,4,6,8]
tercer= [1,3,7,9] 
quart = [2,4,6,8] 
cinque= 5
sise = [2,4,6,8]
sete =[1,3,7,9]
vuite = [2,4,6,8]
nove =[1,3,7,9]
########   abcdefghi el nostre numero que tenim que trovar
#inicializem les variables
a=b=c=d=f=g=h=i=0
iteracions=0
e=5
for n in primer:
    a=n
    iteracions= iteracions+1
    for m in segon:
        b=m
        iteracions= iteracions+1           
        for o in tercer:
            c=o
            iteracions= iteracions+1
            if( (a+b+c) % 3==0):               
                for p in quart:
                    d=p
                    iteracions= iteracions+1
                    if ((int(str(c)+str(d))) % 4==0):
                        for q in sise:
                            f=q
                            iteracions= iteracions+1
                            if ((a+b+c+d+5+f) % 3==0):
                                for r in sete:
                                    g=r
                                    iteracions= iteracions+1
                                    if ((int(str(a)+str(b)+str(c)+str(d)+str(5)+str(f)+str(g))) % 7==0): 
                                        for s in vuite:
                                            h=s
                                            iteracions= iteracions+1
                                            if (int(str(f)+str(g)+str(h)) % 8==0):
                                                for t in nove:
                                                    i=t
                                                    iteracions= iteracions+1
                                                    if ((a+b+c+d+5+f+g+h+i) % 9==0):
                                                        llista=[a,b,c,d,5,f,g,h,i]
                                                        flag = 0
                                                        flag = len(set(llista)) == len(llista)
                                                        if(flag):
                                                            print(str(a)+str(b)+str(c)+str(d)+str(5)+str(f)+str(g)+str(h)+str(i))
                                                            tempsExecucio = time() - start_time
                                                            print("Temps de Execucio: %0.30f segons." % tempsExecucio)
                                                            print("Iteracions : ",iteracions)

Resultat.

Executem el programa des de Spyder i don el següent resultat.

Resultat: 381654729 i els temps de execució del programa es de 0.00099 segons, 0.99ms. El nombre de iteracions es de 456.

Algorisme força bruta.

Nomes tenim una llista de tots els dígits possibles que nomenem candidats.

candidats = [ 1,2,3,4,5,6,7,8,9 ].

No fem servir cap regla de divisibilitat, son 9 bucles niats i comprovem si el numero es múltiple, aplicant el mòdul:

Si x mod y=0 => x es múltiple de y

divisibilitatForzaBruta.py

          
# -*- coding: utf-8 -*-
from time import time
start_time = time()
candidats= [1,2,3,4,5,6,7,8,9]
######### abcdefghi el nostre numero que tenim que trovar
#inicializem les variables
a=b=c=d=e=f=g=h=i=0
iteracions=0
for n in candidats:
    a=n
    iteracions= iteracions+1
    for m in candidats:
        b=m
        iteracions= iteracions+1
        if ((int(str(a)+str(b))) % 2==0):           
            for o in candidats:
                c=o
                iteracions= iteracions+1
                if ((int(str(a)+str(b)+str(c))) % 3==0):              
                    for p in candidats:
                        d=p
                        iteracions= iteracions+1
                        if ((int(str(a)+str(b)+str(c)+str(d))) % 4==0):
                            for q in candidats:
                                e=q
                                iteracions= iteracions+1
                                if ((int(str(a)+str(b)+str(c)+str(d)+str(e))) % 5==0):
                                    for r in candidats:
                                        f=r
                                        iteracions= iteracions+1
                                        if ((int(str(a)+str(b)+str(c)+str(d)+str(e)+str(f))) % 6==0): 
                                            for s in candidats:
                                                g=s
                                                iteracions= iteracions+1
                                                if ((int(str(a)+str(b)+str(c)+str(d)+str(e)+str(f)+str(g))) % 7==0):
                                                    for t in candidats:
                                                        h=t
                                                        iteracions= iteracions+1
                                                        if ((int(str(a)+str(b)+str(c)+str(d)+str(e)+str(f)+str(g)+str(h))) % 8==0):
                                                            for u in candidats:
                                                                i=u
                                                                iteracions= iteracions+1
                                                                if ((int(str(a)+str(b)+str(c)+str(d)+str(e)+str(f)+str(g)+str(h)+str(i))) % 9==0):
                                                                    llista=[a,b,c,d,e,f,g,h,i]
                                                                    flag = 0
                                                                    flag = len(set(llista)) == len(llista)
                                                                    if(flag):
                                                                        print(str(a)+str(b)+str(c)+str(d)+str(e)+str(f)+str(g)+str(h)+str(i))
                                                                        tempsExecucio = time() - start_time
                                                                        print("Temps de Execucio: %0.30f segons." % tempsExecucio)
                                                                        print("Iteracions : ",iteracions)

Resultat.

Que don el resultat: 381654729 i els temps de execució del programa es de 18.95 ms. Ha tardat 19 vegades mes que el codi eficient. El programa ha realitzat 4914 iteracions, deu vegades mes que el programa mes eficient.