## TP4 -- Listes



## Exercise 4.4

## question 7) b)

def modifie(l):
    if l == []:
        return
    else:
        l[0] = l[0] - 1
        l[-1] = l[-1] + 1

# Pour tester cette fonction, on exécute successivement dans la console :
l = [1, -3, 44, 12, -3, 3]
modifie(l)
l



## Exercise 4.6

## question 2) b)

def somme(l):
    n = len(l)
    S = 0
    for i in range(n):
        S = S + l[i]
    return S

# ou bien (plus abstrait, plus élégant) :
def somme(l):
    S = 0
    for x in l:
        S = S + x
    return S



## Exercise 4.8 -- Liste des entiers pairs entre $1$ et $n$

## question 1) b)

# C'est une question subtile car il faut parcourir la liste à l'envers
n = 123456
L = []
for i in range(n):
	L.append(i+1)
for i in range(1, n+1):
	if L[i]%2 !=0:
		L.pop(i)

## question 2) b)

resultat = []
for i in range(1, n+1):
	if i%2 == 0:
		resultat.append(i)



## Exercise 4.11

## question 4) b)

def premierIndice(L, a):
	n = len(L)
	for i in range(n):
		if L[i] == a:
			return i
	return -1



## Exercise 4.12

## question 4) b)

def premierIndiceParDichotomie(L, a):
	n = len(L)
	début = 0
	fin = n-1
	while début <= fin:
		milieu = (début + fin)//2
		x = L[milieu]
		if a == x:
			return milieu
		elif a < x:
			fin = milieu - 1
		else:
			début = milieu + 1
	return -1



## Exercise 4.13

## question 1)

def generalFindFirstByDichotomy(L, a, f):
	n = len(L)
	début = 0
	fin = n-1
	while début <= fin:
		milieu = (début + fin)//2
		x = L[milieu]
		if a == x:
			return milieu
		elif f(a, x):
			fin = milieu - 1
		else:
			début = milieu + 1
	return -1



## Exercise 4.14

## question 2)

def coefficientBinomial(n, k):
	M = []
	M.append([1])
	for i in range(1, n+1):
		L = [1]
		for j in range(1, i):
			L.append(M[-1][j] + M[-1][j-1])
		L.append(1)
		M.append(L)
	return M[n][k]