L3 Alg effective TP4

28 nov. 2016

liste des diviseurs d’un entiers

Liste définie “par compréhention” en Python

Ex. Que font les algorithmes suivants ?

def d1(n):    n=abs(n)    if n==0:return(NN)    else:return([i for i in [1..n] if n%i==0])d1(24)

([1, 2, 3, 4, 6, 8, 12, 24], Non negative integer semiring)

def cd1(a,b):    if a==0:return(d1(b))    else:return([i for i in d1(a) if i in d1(b)])cd1(24,18)

[1, 2, 3, 6]

1 in NN

True

def cd(a,b):#d1(gcd(a,b))    if a*b==0:return(d1(a+b))    else:return(cd(b,a%b))cd(24,18)

[1, 2, 3, 6]

def d2(n):    n=abs(n)    if n==0:return(['all'])    elif n==1:return([1])    else:        i=2        while n%i>0:i=i+1        return([i]+d2(n//i))d2(24)

[2, 2, 2, 3, 1]

def d3(n,i=2):    n=abs(n)    if n==0:return(['all'])    elif n==1:return([])    else:        while n%i>0:i=i+1        return([i]+d3(n//i,i))d3(24)

[2, 2, 2, 3]

def d4(n,i=2):    n=abs(n)    if n==0:return(['all'])    elif n==1:return([1])    else:        while n%i>0:i=i+1        l=d4(n//i,i)        return(sorted(l+[i*k for k in l if i*k not in l]))d4(24)

[1, 2, 3, 4, 6, 8, 12, 24]

dd=d3(24);ddfrom itertools import combinationsS=range(len(dd))#list([2,3])l=list([list(k) for i in [0..len(S)+1] for k in list(combinations(S, i))])l[[dd[j] for j in l[i]] for i in range(len(l))]from operator import mulll=[reduce(mul,[dd[j] for j in l[i]],1) for i in range(len(l))]ll #show(ll)set(ll)

[2, 2, 2, 3] [[], [0], [1], [2], [3], [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3], [0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3]] [[], [2], [2], [2], [3], [2, 2], [2, 2], [2, 3], [2, 2], [2, 3], [2, 3], [2, 2, 2], [2, 2, 3], [2, 2, 3], [2, 2, 3], [2, 2, 2, 3]] [1, 2, 2, 2, 3, 4, 4, 6, 4, 6, 6, 8, 12, 12, 12, 24] set([1, 2, 3, 4, 6, 8, 12, 24])

[2,2,2,3,2].count(2)

def d5(n):    d=d3(n)    return([[k,d.count(k)] for k in set(d)])d5(24)

[[2, 3], [3, 1]]

[2^k*3^l for k in range(4) for l in range(2)]

[1, 3, 2, 6, 4, 12, 8, 24]

def d6(l):    if l==[]:return([1])    else:        return(sorted([l[0][0]^k*d for k in range(l[0][1]+1) for d in d6(l[1:])]))d6(d5(24))

[1, 2, 3, 4, 6, 8, 12, 24]

reduce(mul,[1..5],1)

120

gcd(0,0)