16/04/2009
Exercices de Michel Couprie: solutions aux séries 1 et 2, en Python
Eh oui, c'est la semaine de congé, du coup j'ai un peu levé le pied en matières informatiques. Mais pour ne pas laisser les choses en désuétude, voici quelque chose que j'avais fait avant le début du congé, partagé avec quelques favorisés, et qui pourrait être utile à d'autres.
Quand on veut apprendre à programmer, ou qu'on veut se faire la main sur un langage en particulier, on apprécie d'avoir à disposition des petits problèmes d'algorithmique de difficulté et de complexité croissantes. Pour ma part, quand je m'ennuie j'aime beaucoup avoir un problème que je peux résoudre en moins d'une heure, une sorte de "one-shot" pour se changer les idées.
En fouillant un peu j'ai trouvé cette liste de problèmes, proposé par Michel Couprie. ces problèmes (34 en tout) sont classés par difficulté croissante en quatre paliers. Voici mes solutions pour les problèmes des deux premiers paliers (les deux suivants suivront si je m'ennuie ce soir).
# 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