Questions classiques en Informatique (CFs et CNCs)

1. Quel est le plus grand entier non 7. Valeur max des éléments d’une liste
signé, que l’on peut coder sur n bits?
1 def Max (L):
Avec n bits, on peut coder les entier naturel de 0 à
2 m = L[0]
2n − 1 Donc le plus grand nombre entier est 2n − 1 3 for x in L :
2. Quel est le plus grand entier 4 if m < x:
positif avec bit de signe, avec bit de 5 m = x
signe que l’on peut coder sur n bits? 6 return m
Avec n bits, on peut coder les entiers relatifs de −2n−1
à 2n−1 − 1 le plus grand entier positif donc est 2n−1 − 1 8. Créer une fonction renvoyant la ma-
3. Somme des éléments d’une liste (Accès trice nulle de taille n × m
par indice)
1 def Zeros (n, m):
2 return [[0 for i in range(m)] for j
1 def Somme (L):
,→ in range(n)]
2 S=0
3 #Ou
3 n=len(L)
4 def Zeros (n, m):
4 for i in range(n):
5 M=[]
5 S = S + L[i]
6 for i in range(n):
6 return S
7 L=[]
8 for j in range(m):
4. Somme des éléments d’une liste 9 L.append(0)
(Accès par valeur) 10 M.append(L)
11 #Ou bien avec numpy
1 def Somme (L): 12 import numpy as np
2 S=0 13 def Zeros (n, m):
3 for x in L : 14 return np.zeros((n,m))
4 S = S + x
5 return S
9. Créer une fonction renvoyant une ma-
trice de taille n × m dont les valeurs dont
5. Somme des diviseurs d’un entier n > 0 toutes égales à 1
1 def SommeDiviseurs (n): 1 def Ones (n, m):
2 S=0 2 return [[1 for i in range(m)] for j
3 for i in range(1,n+1): ,→ in range(n)]
4 if n % i == 0: 3 #Ou
5 S = S + i 4 def Ones (n, m):
6 return S 5 M=[]
6 for i in range(n):
6. Moyenne des éléments d’une liste 7 L=[]
8 for j in range(m):
1 def Moy (L): 9 L.append(1)
2 S = 0 10 M.append(L)
3 n = len(L) 11 #Ou bien avec numpy
4 for x in L : 12 import numpy as np
5 S = S + x 13 def Ones (n, m):
6 return S / n 14 return np.ones((n,m))

10. Créer une fonction renvoyant la ma-

trice identité d’ordre n
1
 1 def identite(n): 1 def Binom (p, n):
2 M=[] 2 if not(0<= p <= n):
3 for i in range(n): 3 return 0
4 L=[] 4 return Fact(n)//(Fact(p)*Fact(n-p))
5 for j in range(n):
6 if i==j: 15. Savoir si un entier n est un nombre
7 L.append(1)
premier ou non
8 else:
9 L.append(0) 1 def estPremier (n):
10 M.append(L) 2 for i in range (2,n//2+1):
11 return M 3 if n%i==0:
12 #Ou bien avec numpy 4 return False
13 import numpy as np 5 return True
14 def identite (n):
15 return np.eye((n,n))
16. Représentation binaire d’un entier
naturel n sous forme d’une chaine
11. Factorielle d’un entier n >= 0 (ver-
sion itérative) 1 def Binaire (n):
2 C=""
3 while n!=0:
1 def Factorielle (n): 4 C = str(n%2) + C
2 P=1 5 n = n//2
3 for i in range(2,n+1) : 6 return C
4 P = P * i
5 return P
17. Représentation binaire d’un entier
naturel n sous forme d’une liste
12. Le produit de deux matrices
1 def Binaire (n):
2 C=[]
1 def produit(A,B): 3 while n!=0:
2 if len(A[0]) != len(B): 4 C.append(n%2)
3 print("Multiplication impossible") 5 n = n//2
4 return #arr^eter la fonction 6 return C
5 # Initialisation de la matrice
,→ résultat
6 C = [[0 for i in range(len(B[0]))] 18. Différence de deux vecteurs
,→ for j in range(len(A))] représentés par deux listes de même taille
7 # Calcul du produit matriciel
8 for i in range(len(A)): 1 def Difference (L1, L2):
9 for j in range(len(B[0])): 2 L=[]
10 for k in range(len(B)): 3 n=len(L1) # ou n = len(L2)
11 C[i][j] += A[i][k] * B[k][j] 4 for i in range(n):
12 return C 5 L.append(L1[i]-L2[i])
6 return L

13. Factorielle d’un entier n >= 0 (ver- 19. Produit scalaire de deux vecteurs
sion récursive) représentés par deux listes de même taille

1 def Fact (n): 1 def ProduitScalaire (L1, L2):

2 if n==1 or n==0: 2 S=0
3 return 1 3 n=len(L1) # ou n = len(L2)
4 return (n)*Fact(n-1) 4 for i in range(n):
5 S = S + L1[i] * L2[i]
6 return S
n!
14. Coefficient binomial Cnp = p!(n−p)!
2
 20. PGCD de deux entiers n > 0 et p > 0
1 def recherche_dicho( x, L):
avec l’algorithme d’Euclide itératif
2 a, b = 0, len(L)-1
3 m = (a+b)//2
1 def euclid1 (n, p): 4 while a < b :
2 while n%p!=0: 5 if L[m] == x : return m
3 n, p = p, n%p 6 elif L[m] > x :
4 return p 7 b = m-1
8 else :
21. PGCD de deux entiers n > 0 et p > 0 9 a = m+1
avec l’algorithme d’Euclide récursif 10 m = (a+b)//2
11 return False
1 def euclid2 (n, p):
2 if n%p==0 : 27. Recherche dichotomique d’un
3 return p élément dans une liste triée (version
4 return euclid2(p, n%p) récursive)

1 def rechDicho(x, L):

22. Recherche naı̈ve d’un élément dans
2 if len(L) < 1 :
une liste
3 return False
4 m = len(L)//2
1 def rechercher (x, L):
5 if L[m] == x :
2 return x in L
6 return True
3 #in est un opérateur booléen
7 elif L[m] > x :
8 return rechDicho(x,L[:m])
23. Recherche naı̈ve d’un élément dans 9 else :
une liste (version itérative) 10 return rechDicho(x,L[m:])

1 def rechercher (x, L): 28. Résoudre le problème de Cauchy

2 n=len(L) défini par :
3 for y in L:  ′
4 if y==x: y = F (t, y(t))
5 return True y(t0 ) = y0
6 return False
29. Avec la méthode d’Euler explicite

24. Recherche d’un mot dans une chaine 1 def Euler(F,t0,tf,y0,n) :

de caractères 2 h, T, Y = (tf - t0)/n, [t0], [y0]
3 for i in range(n-1) :
1 def rechercheMot(text, mot): 4 T.append(T[i]+h)
2 n = len(mot) 5 Y.append(Y[i]+h*F(T[i],Y[i])
3 for i in range(len(text) - n + 1) : 6 return T, Y
4 if text[i:i+taille_mot] == mot :
5 return True 30. Le schéma d’Euler implicite est
6 return False défini par : yn+1 = yn + h ∗ f (tn+1 , yn+1 )

25. Échanger deux éléments d’un 1 from scipy.optimize import fsolve

vecteur ou deux lignes d’une matrice 2 def eulerImplicite(f,a,b,n,y0,t0):
3 h,Y,T = (b-a)/n,[y0],[t0]
1 def echanger(L, i, j): 4 for i in range(n-1):
2 L[i], L[j] = L[j], L[i] 5 T.append(T[i]+h)
6 y=fsolve(lambda
,→ x:-x+Y[i]+h*f(T[i+1],x),Y[i])
26. Recherche dichotomique d’un element 7 Y.append(y)
dans une liste triee (version iterative) 8 return T, Y

3
 31. Méthode de Newton (f(x)=0)
1 #Si la fonction min est autorisée
2 def Selection(L):
1 def newton(f, df, x0, epsilon): 3 n=len(L)
2 u = x0 4 for i in range(n-1):
3 v = u - f(u)/df(u) 5 m = min(L[i:]) # le min de la
4 while abs(v - u) > epsilon : ,→ position i a la fin de L
5 u, v = v, v - f(v)/df(v) 6 j=L.index(m)
6 return u 7 L[i], L[j] = L[j], L[i]
8 return L #supprimer cette ligne si
32. Calcul d’une intégrale : Méthode ,→ la fonction trie ne doit rien
des rectangles ,→ renvoyer

36. Tri par insertion

1 def Rectangles(f,a,b,N):
2 h = (b-a)/N # pas de discrétisation 1 def tri(L):
3 I = 0 2 n = len(L)
4 for i in range(N): 3 for i in range(1, n):
5 I+= f(a+i*h) 4 j = i
6 return I*h 5 x = L[i]
6 while 0 < j and x < L[j-1]:
7 L[j] = L[j-1]
33. Calcul d’une intégrale : Méthode des 8 j = j-1
trapèzes 9 L[j] = x
10 return L # si besoin
1 def Trapezes(f,a,b,N):
2 h = (b - a)/N 37. Tri à bulles
3 I = h * 0.5 * (f(a) + f(b)) #
,→ initialisation de l'intégrale 1 def Bulle(L):
4 for i in range(1, N): 2 n = len(L)
5 I += f(a + i*h) 3 Permuter=True
6 return I*h 4 Passe=0
5 while Permuter :
6 Permuter=False
34. Tester si une matrice est inversible
7 Passe+=1
8 for i in range(n-Passe):
1 import numpy.linalg as lg
9 if L[i]>L[j]:
2 def estInversible(M):
10 L[j],L[i]=L[i],L[j]
3 return lg.det(M)!=0
11 Permuter=True
12 return L # si besoin
35. Tri par sélection simplifié