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

cc-by-nc | code (python)

<<< "I know the pieces fit" (2009-05-14) | Project Euler : solution au problème 23, en Python (2009-04-06) >>>