San Vu Ngoc - IRMAR ___
12%3
12%0
0%12
Attention, pour tous les langages informatiques, on ne peut pas calculer 0%0, pourtant 0 est divisible par 0, car 0=1×0
0%0
def divise (i,j): # retourne True si i divise j
return (i,j) == (0,0) or j == 0 or (i !=0 and (j % i == 0))
divise (3,12), divise (12,3)
divise (0,0), divise (12,0), divise (0,12)
(and why we care)
i =ligne, j = colonne
%matplotlib inline
# inline can be replaced by notebook to get interactive plots
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as img
import matplotlib.cm as cm
import matplotlib.colors as colors
font = {'family': 'serif',
'color': 'darkred',
'weight': 'normal',
'size': 20,
}
n=100
T = np.zeros((n,n))
for i in range(0, n):
for j in range(0, n):
if divise (i,j):
T[i,j] = 0
else:
T[i,j] = 1
T
plt.rcParams['figure.figsize'] = (15.0, 10.0) # set figures display bigger
plt.imshow(T+0.15, interpolation='none', clim=(0.0, 1.), cmap=cm.hot)
plt.xlabel('i',fontdict=font)
plt.ylabel('j',fontdict=font)
# choix de la colormap: https://matplotlib.org/users/colormaps.html
# choix de l'interpolation: https://matplotlib.org/examples/images_contours_and_fields/interpolation_methods.html
Top = T[1:20,::]
plt.imshow(Top+0.15, interpolation='none', clim=(0.0, 1.), cmap=cm.hot)
plt.xlabel('time (s)')
def division (a,b):
q = 0
m = 0
while (m <= a):
m = m + b
q = q + 1
return (q - 1, a - m + b)
division (2023,123)
123*16 + 55
Attention avec les nombres négatifs ça ne marche pas du tout:
division (-2022,123)
Exercice: adapter la fonction pour admettre a négatif.
Les invariants sont très utiles pour éviter les erreurs de programmation.
def division2 (a,b):
q,r = 0,a
while r >= b:
r = r - b
q = q + 1
return (q,r)
division2 (2023,123)
def divisionR (a,b):
if a < b:
return (0, a)
else:
q,r = divisionR (a-b, b)
return (q+1, r)
divisionR (2023,123)
Dans ces 3 algorithmes, la complexité (ici, le nombre d'itérations) est a/b+1, donc au pire linéaire en a (pire cas: pour b=1). On peut faire mieux (pour les grands nombres) avec un méthode de type Newton, cf: https://en.wikipedia.org/wiki/Division_algorithm#Newton%E2%80%93Raphson_division
2023/123
2023//123
2023%123
divmod(2023,123)
Le résultat est correct pour les nombres a négatifs. Donc attention: -(a%b) n'est pas égal à (-a)%b !
(-2023)%123
-(2023%123)
divmod(-2023,123)