# Solutions aux exercices proposes par Michel Couprie a l'adresse:
# http://www.esiee.fr/~coupriem/Exos/exos/exos.html
#
# Il peut y avoir d'autres approches, evidemment, je ne fournis celles-ci qu'a
# titre d'exemples.
# 2009/04/08, 2009-04-09 - Jean Karim Bockstael - jkb@jkbockstael.be
#------------------------------------------------------------------------------
# DIFFICULTE 1
#------------------------------------------------------------------------------
#------------------------------------------------------------------------------
# 01 - Factorielle
# http://www.esiee.fr/~coupriem/Exos/Enonces/fact
def factorielle_iterative(n):
res = 1
while (n > 1):
res *= n
n -= 1
return res
def factorielle_recursive(n):
if n < 2:
return 1
else:
return n * factorielle_recursive(n - 1)
#------------------------------------------------------------------------------
# 02 - Inversion d'un tableau
# http://www.esiee.fr/~coupriem/Exos/Enonces/inverse
def inversion_tableau_iterative(tab):
tmp = []
if len(tab) < 2:
return tab
for i in (len(tab), 0, -1):
tmp.append(tab[i - 1])
return tmp
def inversion_tableau_recursive(tab):
if len(tab) < 2:
return tab
else:
return inversion_tableau_recursive(tab[1:]) + [tab[0]]
def inversion_tableau_pythonienne(tab):
return tab[-1::-1]
#------------------------------------------------------------------------------
# 03 - Minimum et maximum sur un tableau en une seule passe
# http://www.esiee.fr/~coupriem/Exos/Enonces/minmax
def min_et_max(tab):
if len(tab) < 1:
return {}
res = {'min' : tab[0], 'max' : tab[0]}
for i in range(1, len(tab)):
if (tab[i] < res['min']):
res['min'] = tab[i]
if (tab[i] > res['max']):
res['max'] = tab[i]
return res
#------------------------------------------------------------------------------
# 04 - Palindrome ou non, en ignorant les espaces
# http://www.esiee.fr/~coupriem/Exos/Enonces/palindrome
def est_palindrome(texte):
if len(texte) < 2:
return True
tmp = texte.replace(' ', '')
return (tmp == tmp[-1::-1])
#------------------------------------------------------------------------------
# 05 - Solution d'un polynome par Horner
# http://www.esiee.fr/~coupriem/Exos/Enonces/polynome
def solution_horner(poly, value):
# avec poly de la forme [coeff, ...] sans vide, poids fort au debut
# donc on note explicitement les coefficiens nuls
result = poly[0]
for i in range(1, len(poly)):
result *= value
result += poly[i]
return result
#------------------------------------------------------------------------------
# 06 - Estimation de Pi
# http://www.esiee.fr/~coupriem/Exos/Enonces/calculpi
from random import random
from math import sqrt
def estimation_pi(nb_points):
def radius(x_coord, y_coord):
return sqrt(x_coord ** 2 + y_coord ** 2)
cnt = 0.0
for i in range(0, nb_points):
if radius(random(), random()) < 1:
cnt += 1
return cnt / nb_points * 4
#------------------------------------------------------------------------------
# 07 - Suite "cube de chiffres du terme precedent"
# http://www.esiee.fr/~coupriem/Exos/Enonces/cubes
def suite_cube_chiffres(depart):
def somme_cubes_chiffres(nombre):
tmp = str(nombre)
res = 0
for i in range(0, len(tmp)):
res += int(tmp[i]) ** 3
return res
if (depart % 3 != 0) or (depart < 0):
return "Le premier element doit etre un multiple positif de 3."
res = [depart]
while res[-1] != somme_cubes_chiffres(res[-1]):
res.append(somme_cubes_chiffres(res[-1]))
return res[-1]
#------------------------------------------------------------------------------
# 08 - Crible d'Eratosthene
# http://www.esiee.fr/~coupriem/Exos/Enonces/eratos
def crible_eratosthene(limite):
res_bool = [False, False]
for i in range(2, limite + 1):
res_bool.append(True)
for i in range(2, limite + 1):
for j in range(2, i / 2 + 1):
if (i % j == 0) and (i / j != 1):
res_bool[i] = False
res_num = []
for i in range(2, limite + 1):
if res_bool[i]:
res_num.append(i)
return res_num
#------------------------------------------------------------------------------
# 09 - Test de la primalite d'un entier
# http://www.esiee.fr/~coupriem/Exos/Enonces/premier
def est_premier(nombre):
if (nombre < 2):
return False
premiers = crible_erathosthene(nombre / 2 + 1)
for i in premiers:
if (nombre % i == 0):
return False
return True
#------------------------------------------------------------------------------
# 10 - Produit scalaire de deux vecteurs
# http://www.esiee.fr/~coupriem/Exos/Enonces/prodscal
def produit_scalaire(vec1, vec2):
if (len(vec1) != len(vec2)) or \
(len(vec1) < 1) or \
(len(vec2) < 1):
return "Arguments incorrects"
tmp = 0
for i in range(0, len(vec1)):
tmp += vec1[i] * vec2[i]
return tmp
#------------------------------------------------------------------------------
# 11 - Puissance N d'un nombre, en effectuant moins de N-1 multiplications
# http://www.esiee.fr/~coupriem/Exos/Enonces/puissance
def puissance(base, expo):
if (expo < 0):
return "L'exposant doit etre positif ou nul"
tmp = 1
while (expo > 1):
tmp *= (base * base)
expo -= 2
if (expo == 1):
tmp *= base
return tmp
#------------------------------------------------------------------------------
# 12 - Calcul de la racine carree
# http://www.esiee.fr/~coupriem/Exos/Enonces/raccar
def racine_carree(nbr, precision):
# Estimation a la louche
rac = 0
while (nbr > rac ** 2):
rac += 1
if (nbr == rac ** 2):
return rac
# Affinement
for i in range(0, precision):
rac = (rac + nbr / rac) / 2.0
return rac
#------------------------------------------------------------------------------
# 13 - Calcul de la racine cubique
# http://www.esiee.fr/~coupriem/Exos/Enonces/raccube
def racine_cubique(nbr, precision):
# Estimation a la louche
rac = 0
while (nbr > rac ** 3):
rac += 1
if (nbr == rac ** 3):
return rac
# Affinement
for i in range(0, precision):
rac = (2 * rac + nbr / (rac ** 2)) / 3.0
return rac
#------------------------------------------------------------------------------
# 14 - Recherche sequentielle sur un tableau
# http://www.esiee.fr/~coupriem/Exos/Enonces/rechseq
# Meme chose que l'exercice 03
#------------------------------------------------------------------------------
# 15 - Fonction sin(x)
# http://www.esiee.fr/~coupriem/Exos/Enonces/sinus
def sinus(x, precision):
def factorielle(n):
return factorielle_iterative(n)
result = 0.0
for n in range(0, precision):
result += ((-1) ** n) * ((x ** (2 * n + 1)) / (factorielle(2 * n + 1)))
return result
#------------------------------------------------------------------------------
# 16 - Symetrie d'une matrice
# http://www.esiee.fr/~coupriem/Exos/Enonces/symetrique
def est_symetrique(matrice):
if (len(matrice) != len(matrice[0])):
return False # Une matrice doit etre carree pour etre symetrique
for i in range(0, len(matrice)):
for j in range(0, i):
if matrice[i][j] != matrice[j][i]:
return False
return True
#------------------------------------------------------------------------------
# 17 - Affichage du triangle de Pascal
# http://www.esiee.fr/~coupriem/Exos/Enonces/trpascal
def triangle_de_pascal(rangees):
print "1"
print "1 1"
prevline = [1, 1]
for i in range(3, rangees + 1):
thisline = [1]
for j in range(1, i - 1):
thisline.append(prevline[j] + prevline[j - 1])
thisline.append(1)
for j in range(0, i - 1):
print str(thisline[j]) + " ",
print str(thisline[-1])
prevline = thisline
#------------------------------------------------------------------------------
# DIFFICULTE 2
#------------------------------------------------------------------------------
#------------------------------------------------------------------------------
# 18 - Determiner si deux chaines sont anagrammes
# http://www.esiee.fr/~coupriem/Exos/Enonces/anagrame
def sont_anagrammes(chaine1, chaine2):
chaine1 = chaine1.strip(" ,.;:?!'\"-_").lower()
chaine2 = chaine2.strip(" ,.;:?!'\"-_").lower()
return (list(chaine1).sort() == list(chaine2).sort())
#------------------------------------------------------------------------------
# 19 - Convolution
# http://www.esiee.fr/~coupriem/Exos/Enonces/convolution
def convolution(tabA, tabH):
# A de taille 100x100, H de taille 7x7
tabB = [[0] * 100] * 100
for i in range(0, 100):
for j in range(0, 100):
if ((i in range(0, 3) or i in range(97, 100)) or \
(j in range(0, 3) or j in range(97, 100))):
tabB[i][j] = tabA[i][j]
else: # i,j in (4, 97)
for m in range(0, 7):
for n in range(0, 7):
tabB[i][j] += tabA[i + m - 3][j + n - 3] * tabH[m][n]
return tabB
#------------------------------------------------------------------------------
# 20 - Fusion de deux tableaux tries
# http://www.esiee.fr/~coupriem/Exos/Enonces/fusion
def fusion_tableaux_tries(tab1, tab2):
cur1 = 0
cur2 = 0
tab3 = []
while (cur1 < len(tab1)) and (cur2 < len(tab1)):
if tab1[cur1] < tab2[cur2]:
tab3.append(tab1[cur1])
cur1 += 1
else:
tab3.append(tab2[cur2])
cur2 +=1
# Un des deux tableaux a ete entierement copie, reste a vider l'autre
while (cur1 < len(tab1)):
tab3.append(tab1[cur1])
cur1 += 1
while (cur2 < len(tab2)):
tab3.append(tab2[cur2])
cur2 += 1
return tab3
#------------------------------------------------------------------------------
# 21 - Conjecture Hongroise (note: on l'appelle aussi "probleme de Collatz")
# http://www.esiee.fr/~coupriem/Exos/Enonces/hongrois
def hongroise(depart):
if (depart == 1):
print "1 4 2 1 4 2 ..."
else:
print str(depart),
if (depart % 2 == 0):
hongroise(depart / 2)
else:
hongroise(3 * depart + 1)
#------------------------------------------------------------------------------
# 22 - Regroupement des valeurs paires et impaires
# http://www.esiee.fr/~coupriem/Exos/Enonces/pairimpair
def paires_impaires(tab):
res = []
for i in range(0, len(tab)):
if (tab[i] % 2 == 0):
res.append(tab[i])
for i in range(0, len(tab)):
if (tab[i] % 2 != 0):
res.append(tab[i])
return res
#------------------------------------------------------------------------------
# 23 - Afficher les nombres parfaits compris entre 1 et N
# http://www.esiee.fr/~coupriem/Exos/Enonces/parfaits
def nombres_parfaits(limite):
res = []
for nb in range(1, limite + 1):
sommediv = 0
for di in range(1, nb / 2 + 1):
if (nb % di == 0):
sommediv += di
if (sommediv == nb):
res.append(nb)
return res
#------------------------------------------------------------------------------
# 24 - Determiner la periode d'un signal digital
# http://www.esiee.fr/~coupriem/Exos/Enonces/periode
def periode_signal(tab):
per = 0
fini = False
while (not fini) and (per < len(tab) - 1):
per +=1
# Verification de cette hypothese
for cur in range(0, per):
fini = (tab[cur] == tab[cur + per])
if (fini):
return per
else:
return 0
#------------------------------------------------------------------------------
# 25 - Plus grand plateau dans le graphique d'une fonction monotone
# http://www.esiee.fr/~coupriem/Exos/Enonces/plateau
def plus_grand_plateau(tab):
plat_max = 1
plat_tmp = 0
for i in range(1, len(tab)):
if tab[i] == tab[i - 1]:
plat_tmp += 1
else:
plat_tmp = 1
if plat_tmp > plat_max:
plat_max = plat_tmp
return plat_max
#------------------------------------------------------------------------------
# 26 - Calcul de la racine carree entiere d'un entier
# http://www.esiee.fr/~coupriem/Exos/Enonces/racent
def racine_carree_entiere(nbr):
rac = 0
while (nbr > rac ** 2):
rac += 1
if (nbr == rac ** 2):
return rac
else:
return rac - 1
#------------------------------------------------------------------------------
# 27 - Conversion Romain-arabe
# http://www.esiee.fr/~coupriem/Exos/Enonces/romains
def romain_vers_arabe(romannumber):
romandigits = { 'I': 1, 'V': 5, 'X': 10, 'L': 50 }
number = 0
for i in range(1, len(romannumber)):
if (romandigits[romannumber[i]] > romandigits[romannumber[i - 1]]):
number -= romandigits[romannumber[i - 1]]
else:
number += romandigits[romannumber[i - 1]]
number += romandigits[romannumber[-1]]
return digit
#------------------------------------------------------------------------------
# 28 - Transcodage octal-decimal
# http://www.esiee.fr/~coupriem/Exos/Enonces/transcodage
def octal_vers_decimal(octnum):
number = 0
octalnumber = str(octnum)
for i in range(0, len(octalnumber)):
number += int(octalnumber[i]) * (8 ** (len(octalnumber) - i - 1))
return number
