121 lines
1.9 KiB
Python
121 lines
1.9 KiB
Python
### Exercice 1 ###
|
|
|
|
def estDedans(l,e):
|
|
for el in l:
|
|
if e==l:
|
|
return True
|
|
return False
|
|
|
|
def maximum(l):
|
|
max = l[0]
|
|
for e in l:
|
|
if e>max:
|
|
max = e
|
|
return max
|
|
|
|
def count(l,e):
|
|
s = 0
|
|
for el in l:
|
|
if el==e:
|
|
s+=1
|
|
return s
|
|
|
|
def moyenne(l):
|
|
s = 0
|
|
for el in l:
|
|
s+=el
|
|
return s/len(l)
|
|
|
|
def var(l):
|
|
s = 0
|
|
m = moyenne(l)
|
|
for el in l:
|
|
s+=(el-m)**2
|
|
return sqrt(s/len(l))
|
|
|
|
def majoritaire(l):
|
|
cmax = 0
|
|
emax = l[0]
|
|
for el in l:
|
|
c = count(el,l)
|
|
if c > cmax:
|
|
emax = el
|
|
return emax
|
|
|
|
### Exercice 2 ###
|
|
|
|
# Structure: liste de 2-tuples contenant (volume,masse)
|
|
|
|
# Algorithme naif: on teste tout
|
|
def pasTropLourd_lourd(l,m):
|
|
selection = None #list
|
|
vmax=0
|
|
for i in range(2**len(l)):
|
|
test = [l[k] for k in range(len(l)) if ((i>>k)%2)==1]
|
|
mas = sum([t[1] for t in test])
|
|
vol = sum([t[0] for t in test])
|
|
if mas<=m and vol>vmax:
|
|
selection = test
|
|
vmax=vol
|
|
return selection
|
|
|
|
# Bernard ici présent est en O(2^n)
|
|
|
|
def pasTropLourd(l,m):
|
|
if(len(l)==0): return l
|
|
if(len(l)==1): return l if l[0][1]<=m else []
|
|
|
|
# Avec ou sans ?
|
|
reste = l[1:]
|
|
(vm,ms) = l[0]
|
|
if ms>m:
|
|
return pasTropLourd(reste,m)
|
|
else:
|
|
p1 = pasTropLourd(reste,m)
|
|
p2 = pasTropLourd(reste,m-ms)
|
|
v1 = sum([t[0] for t in p1])
|
|
v2 = sum([t[0] for t in p2])+vm
|
|
return p1 if v1>=v2 else p2+[(vm,ms)]
|
|
|
|
|
|
### Exercice 3 ###
|
|
import numpy as np
|
|
|
|
def bell(n):
|
|
bin = np.zeros((n+1,n+1),dtype=int)
|
|
bin[0,0] = 1
|
|
for i in range(1,n+1):
|
|
bin[i,0]=1
|
|
bin[i,1:] = bin[i-1,1:] + bin[i-1,:-1]
|
|
|
|
B = np.zeros((n+1,),dtype=int)
|
|
B[0] = 1
|
|
print(bin[5,:])
|
|
for i in range(1,n+1):
|
|
B[i] = np.dot(B,bin[i,:].T)
|
|
return B
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|