## TP2 -- Tests, boucles et modules



## Exercise 2.2 -- Somme des éléments d'une liste

## question 2)

def testeBis(n):
	if n%2 == 0:
		return False
	else:
		if n%5 == 0 :
			return True
		else:
			return False
			
# ou bien :
def testeBis(n):
	if n%2 == 1 and n%5 == 0:
		return True
	else:
		return False
		
# ou bien (plus abstrait et plus élégant) :
def testeBis(n):
	return (n%2 == 1 and n%5 == 0)



## Exercise 2.3

## question 2)

def testeQuatro(n):
	if n%3 == 0:
		if n%4 == 0:
			return 42
		else:
			return n%4
	else:
		return n%3

# ou bien :
def testeQuatro(n):
	if n%3 != 0:
		return n%3
	else:
		if n%4 != 0:
			return n%4
		else:
			return 42



## Exercise 2.4

## question 1)

def valeurAbsolue(x):
	if x >= 0:
		return x
	else:
		return -x

## question 2)

def distance(a, b):
	return valeurAbsolue(b-a)



## Exercise 2.5

## question 1)

def somme(a, b):
	return a+b

## question 2)

def moyenne(a, b):
	return somme(a, b)/2

## question 3)

def produit(a, b):
	return a*b

## question 4)

def sommeAucarre(a, b):
	return somme(produit(a, a), produit(b, b))



## Exercise 2.6

## question 4)

def f(a, b):
	return somme(valeurAbsolue(a), valeurAbsolue(b))



## Exercise 2.7

## question 4)

def module(z):
	return (z.real + z.imag)**0.5

def testInegalitéTriangulaire(a, b):
	return module(a+b) <= module(a) + module(b)



## Exercise 2.10

## question 2)

mt.gcd(4243, 42434445)



## Exercise 2.11

## question 3)

def g(n):
	S = 0
	for k in range(1, n+1):
		if k%2 == 1:
			S = S+k
	return S

## question 4)

def factorielle(n):
	P = 1
	for k in range(1, n+1):
		P = P*k
	return P



## Exercise 2.12 -- Approximation rationnelle d'un nombre

## question 1)

import math as mt

def findBestFraction(n):
	x = mt.log(3)/mt.log(2)
	bestFraction = (1, 1)
	bestDistance = abs(1/1 - x)
	for b in range(1, n+1):
		for a in range(b, 2*b+1):
			x_test = a/b
			if abs(x-x_test) < bestDistance:
				bestDistance = abs(x-x_test)
				bestFraction = (a, b)
	return (a, b)



## Exercise 2.13

## question 2) a)

import math as mt

def g(n):
	S = 0
	for k in range(1, n+1):
		S = S + mt.log(k)
	return S

## question 2) b)

def plusPetitEntier(M):
	n = 0
	while g(n) <= M:
		n = n+1
	return n

## question 2) e)

import math as mt

def meilleurPlusPetitEntier(M):
	S = 0
	n = 0
	while S <= M:
		S = S + mt.log(n)
		n = n+1
	return n



## Exercise 2.14 -- Partie entière

## question 2) e)

def maPartieEntiere(x):
	n = 0
	while k <= x:
		k= k+1
	return k-1



## Exercise 2.15 -- Entiers de Syracuse

## question 1) e)

def isSyracuse(n):
	if n == 1:
		return
	elif n%2 == 0:
		isSyracuse(n//2)
	else:
		isSyracuse(3n+1)

## question 2) e)

def areFirstSyracuse(n):
	for k in range(1, n+1):
		isSyracuse(k)
	return True

## question 3) e)

def lengthSyracuse(n):
	if n == 0:
		return 0
	while n > 1:
		if n%2 == 0:
			return lengthSyracuse(n//2) + 1
		elif :
			return lengthSyracuse(3*n+1)

## question 4) e)

def heightSyracuse(n):
	record = 0
	k = n
	while k > 1:
		if k%2 == 0:
			k = k//2
		else:
			k = 3*k+1
		if k > record:
			record = k
	return record



## Exercise 2.18 -- Algorithme d'Euclide

## question 1) e)

41424241//3333

## question 2) e)

def myPGCD(n, m):
	if m > n:
		return myPGCD(m, n)
	if m = 0:
		return n
	return myPGCD(m, n%m)

## question 3) e)

% Cet algorithme repose sur le calcul suivant :
% si r = n - qm et si u*m + v*r = d, alors d = v*n + (u-q)*m
def bezoutRelation(n, m):
	if m > n:
		(u, v, d) = bezoutRelation(n, m)
		return (v, u, d)
	if m = 0:
		return (1, 0, n)
	r = n%m
	q = n//m
	(u, v, d) = myPGCD(m, r)
	return (v, u-q, d)



## Exercise 2.19

## question 3) e)

def factorielle(n):
	if n == 0:
		return 1
	else:
		return n*factorielle(n-1)



## Exercise 2.20

## question 1) e)

def binom(n, k):
	if k == 0 or n == k
		return 1
	else:
		return binom(n-1, k-1) + binom(n-1, k)



## Exercise 2.22

## question 3) e)

def parties(n):
	if n == 0:
		return [ [] ]
	result = []
	for A in parties(n-1):
		result.append(A[:])
		A.append(n)
		result.append(A)
	return result
	
def S(n):
	somme = 0
	for A in parties(n):
		for a in A:
			somme = somme + 1/a
	return somme