ICC-P Corrigé 5
Exercice 1:
Exercice 2:
# on définit le type Matrix comme étant équivalent à une liste de liste de floats
Matrix = list[list[float]]
# on définit une matrice
m1: Matrix = [[1, 2, 3], [9, 8, 7]]
m2: Matrix = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
m3: Matrix = [[0, 2], [2, 0]]
m4: Matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [1, 5, 7]]
m5: Matrix = [[1, 2, 3]]
m6: Matrix = [[1], [2], [3]]
def print_matrix(mat: Matrix) -> None:
print("[")
for row in mat:
print(" ", end="")
for val in row:
print(val, end="")
print(" ", end="")
print("")
print("]")
matrices = [m1, m2, m3, m4, m5, m6]
for m in matrices:
print_matrix(m)
def dim_m(mat: Matrix) -> int:
return len(mat)
def dim_n(mat: Matrix) -> int:
m = dim_m(mat)
if m == 0:
return 0
n = len(mat[0])
for i in range(1, m):
if len(mat[i]) != n:
return 0
return n
for m in matrices:
print(f"{dim_m(m)}x{dim_n(m)}")
def identity(size: int) -> Matrix:
mat: Matrix = []
for i in range(size):
line: list[float] = []
for j in range(size):
if i == j:
line.append(1)
else:
line.append(0)
mat.append(line)
return mat
# version raccourcie avec compréhension de liste (avancé)
def identity2(size: int) -> Matrix:
return [[int(i == j) for i in range(size)] for j in range(size)]
print(f"identity check: {identity(3) == m2}")
def empty(m: int, n: int) -> Matrix:
mat: Matrix = []
for _ in range(m):
line: list[float] = []
for _ in range(n):
line.append(0)
mat.append(line)
return mat
# version raccourcie avec compréhension de liste (avancé)
def empty2(m: int, n: int) -> Matrix:
return [[0 for _ in range(n)] for _ in range(m)]
def mult(mat1: Matrix, mat2: Matrix) -> Matrix:
mat1_m, mat1_n = dim_m(mat1), dim_n(mat1)
mat2_m, mat2_n = dim_m(mat2), dim_n(mat2)
if mat1_m == 0 or mat2_m == 0 or mat1_n != mat2_m:
return []
mat3 = empty(mat1_m, mat2_n)
for i in range(mat1_m):
for j in range(mat2_n):
sum = 0.0
for k in range(mat2_m):
sum += mat1[i][k] * mat2[k][j]
mat3[i][j] = sum
return mat3
print_matrix(mult(m1, m2))
print_matrix(mult(m5, identity(dim_n(m5))))
print_matrix(mult(identity(dim_m(m4)), m4))
Matrix = list[list[float]]
# on définit une matrice
m1: Matrix = [[1, 2, 3], [9, 8, 7]]
m2: Matrix = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
m3: Matrix = [[0, 2], [2, 0]]
m4: Matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [1, 5, 7]]
m5: Matrix = [[1, 2, 3]]
m6: Matrix = [[1], [2], [3]]
def print_matrix(mat: Matrix) -> None:
print("[")
for row in mat:
print(" ", end="")
for val in row:
print(val, end="")
print(" ", end="")
print("")
print("]")
matrices = [m1, m2, m3, m4, m5, m6]
for m in matrices:
print_matrix(m)
def dim_m(mat: Matrix) -> int:
return len(mat)
def dim_n(mat: Matrix) -> int:
m = dim_m(mat)
if m == 0:
return 0
n = len(mat[0])
for i in range(1, m):
if len(mat[i]) != n:
return 0
return n
for m in matrices:
print(f"{dim_m(m)}x{dim_n(m)}")
def identity(size: int) -> Matrix:
mat: Matrix = []
for i in range(size):
line: list[float] = []
for j in range(size):
if i == j:
line.append(1)
else:
line.append(0)
mat.append(line)
return mat
# version raccourcie avec compréhension de liste (avancé)
def identity2(size: int) -> Matrix:
return [[int(i == j) for i in range(size)] for j in range(size)]
print(f"identity check: {identity(3) == m2}")
def empty(m: int, n: int) -> Matrix:
mat: Matrix = []
for _ in range(m):
line: list[float] = []
for _ in range(n):
line.append(0)
mat.append(line)
return mat
# version raccourcie avec compréhension de liste (avancé)
def empty2(m: int, n: int) -> Matrix:
return [[0 for _ in range(n)] for _ in range(m)]
def mult(mat1: Matrix, mat2: Matrix) -> Matrix:
mat1_m, mat1_n = dim_m(mat1), dim_n(mat1)
mat2_m, mat2_n = dim_m(mat2), dim_n(mat2)
if mat1_m == 0 or mat2_m == 0 or mat1_n != mat2_m:
return []
mat3 = empty(mat1_m, mat2_n)
for i in range(mat1_m):
for j in range(mat2_n):
sum = 0.0
for k in range(mat2_m):
sum += mat1[i][k] * mat2[k][j]
mat3[i][j] = sum
return mat3
print_matrix(mult(m1, m2))
print_matrix(mult(m5, identity(dim_n(m5))))
print_matrix(mult(identity(dim_m(m4)), m4))
Exercice 2:
numbers = sorted([1, 5, 6, 2, 8, 12, 5])
print(numbers)
def binary_search(values: list[int], item: int) -> int:
from_index = 0
to_index = len(values)
while True:
print(f"Searching {item} in {values[from_index:to_index]}")
if to_index - from_index <= 0:
return -1
middle_index = (from_index + to_index) // 2
if values[middle_index] == item:
return middle_index
else:
if item < values[middle_index]:
to_index = middle_index
else:
from_index = middle_index + 1
def binary_search_recursive(values: list[int], item: int, from_index: int = 0, to_index: int = -1) -> int:
if to_index == -1:
to_index = len(values)
print(f"Searching {item} in {values[from_index:to_index]}")
if to_index - from_index <= 0:
return -1
middle_index = (from_index + to_index) // 2
if values[middle_index] == item:
return middle_index
elif item < values[middle_index]:
return binary_search_recursive(values, item, from_index, middle_index)
else:
return binary_search_recursive(values, item, middle_index + 1, to_index)
for v in numbers:
print(binary_search(numbers, v))
print(binary_search(numbers, 3))
print(binary_search(numbers, 7))
print(binary_search(numbers, 42))
print(numbers)
def binary_search(values: list[int], item: int) -> int:
from_index = 0
to_index = len(values)
while True:
print(f"Searching {item} in {values[from_index:to_index]}")
if to_index - from_index <= 0:
return -1
middle_index = (from_index + to_index) // 2
if values[middle_index] == item:
return middle_index
else:
if item < values[middle_index]:
to_index = middle_index
else:
from_index = middle_index + 1
def binary_search_recursive(values: list[int], item: int, from_index: int = 0, to_index: int = -1) -> int:
if to_index == -1:
to_index = len(values)
print(f"Searching {item} in {values[from_index:to_index]}")
if to_index - from_index <= 0:
return -1
middle_index = (from_index + to_index) // 2
if values[middle_index] == item:
return middle_index
elif item < values[middle_index]:
return binary_search_recursive(values, item, from_index, middle_index)
else:
return binary_search_recursive(values, item, middle_index + 1, to_index)
for v in numbers:
print(binary_search(numbers, v))
print(binary_search(numbers, 3))
print(binary_search(numbers, 7))
print(binary_search(numbers, 42))
Last modified: Friday, 15 March 2024, 15:58