ICC-P Corrigé 5

# 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))
 

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))