Partage

[Exercice] Puissance sans pow

26 juillet 2011 à 21:29:41

Salut,

Je suis entrain d'apprendre le Python et en faisant un tour sur le forum, il m'est venu une idée d'exercice (((mega)ulta)super) simple :-°

!

Exercice:

Créer une fonction permettant de d'élever un nombre à une certaine puissance sur un intervalle sans utiliser pow. Un exemple valant mieux qu'un long discours:

>>> puissance(5, 3, 6)
5 à la puissance 3 = 125
5 à la puissance 4 = 625
5 à la puissance 5 = 3125
5 à la puissance 6 = 15625
Fin.
>>>

Le nombre 5 a été élevé à toutes les puissance entre 3 et 6 (bornes comprises).
Vous ai-je dit que ce script était simple ?
Cet exercice permet de tester les boucles et conditions.

Solution:

Ceci n'est qu'une solution parmi tant d'autres:

def puissance(nb, min = 1, max = 5):
    i = 1
    puissance = 1
    while i <= max:
        puissance *= nb
        if i >= min:
            print(nb, "à la puissance", i, "=", puissance)
        i += 1
    print("Fin.")

quelqun_dautre

26 juillet 2011 à 22:28:02

def pair(n):
	return n%2 == 0

def exponentiation(a, b):
	if b<0:
		return float(1)/exponentiation(a, -b)
	r = 1
	while b != 0:
		if not pair(b):
			r *= a
			b -= 1
		a *= a
		b /= 2
	return r

def puissance(a, min, max):
	foo = exponentiation(a, min)
	for i in xrange(min, max+1):
		print a, " à la puissance ", i, " = ", foo
		foo *= a

yjltg.

candide

26 juillet 2011 à 22:35:42

Citation : Feanor13

Créer une fonction permettant de d'élever un nombre à une certaine puissance sur un intervalle sans utiliser pow

Je trouve que ce genre d'exercice n'a aucun intérêt en Python puisqu'on dispose nativement de l'opérateur d'exponentiation ** ou bien la fonction pow. Disons que je trouve l'exercice totalement artificiel. A ce moment-là on pourrait aussi décider de reprogrammer la multiplication des entiers en utilisant uniquement l'addition (puisque, par exemple, <math>\(5\times 3= 3+3+3+3+3\)</math>). L'exercice pourrait avoir un intérêt en C, et encore.

Par ailleurs, je ne sais pas si c'est le tuto qui t'a mal inspiré, mais ta façon de coder l'exercice est incorrecte, peu orthodoxe en tous cas, puisque nous sommes typiquement dans le cas d'utilisation conseillée d'une boucle for et non pas 'une boucle while comme tu l'as fait.

Si tu veux un exercice plus intéressant, je t'en propose un :

on te donne trois entiers strictement positifs a, b et n, par exemple a=29, b=42 et n= 10 et on te demande de donner la n-ième décimale de la division «à virgule» de a par b. Ici, dans l'exemple proposé, la réponse attendue est 4 puisque, comme sagemath par exemple te fait le calcul, on a :

>>> numerical_approx(29/42, digits=102)
0.6904761904761904761904761904761904761904761904761904761904761904761904\
76190476190476190476190476190476

</span>

Feanor13

26 juillet 2011 à 22:36:39

@quelqun_dautre: Une petite erreur à la ligne 17:

print (a, " à la puissance ", i, " = ", foo)

En tout cas, chez moi cela lève une exception.
@candide: Ok, je tiens compte de tes remarques. Garde juste à l'esprit que je suis débutant et que j'ai bien précisé dans le topic que l'exercice pouvait être mal conçu. Ce que je trouve dommage avec ton exercice, c'est que je ne vois pas d'application pratique.
Si tu as le temps et l'envie, propose une solution à mon exercice (cela devrait être rapide), je suis intéressé par ta solution.

@+

candide

26 juillet 2011 à 23:03:51

Citation : Feanor13

Ce que je trouve dommage avec ton exercice, c'est que je ne vois pas d'application pratique.

applications «pratiques» ? la question ne se pose pas, ce n'est pas le but d'un exercice, ton exercice d'ailleurs n'a rien de "pratique" et en plus mon exercice propose d'obtenir un résultat que Python ne peut pas a priori te fournir autrement qu'en le programmant.

Concernant le choix d'un exercice, la question est plus complexe qu'il n'y paraît.

Citation : Feanor13

Si tu as le temps et l'envie, propose une solution à mon exercice (cela devrait être rapide), je suis intéressé par ta solution.

Ce n'est pas une question de temps ni d'envie c'est tout simplement que je considère que les exercices ne sont pas interchangeables d'un langage à l'autre et en particulier, Python étant un langage de haut niveau, il vaut mieux prendre le pli tout de suite et ne pas faire le même genre d'exo qu'on ferait par exemple en C. Ton exercice n'est pas forcément à rejeter mais il y en a de beaucoup plus adapté au niveau du langage s'il s'agit de tester juste les conditions et la boucle for.

quelqun_dautre

26 juillet 2011 à 23:27:18

Citation : Feanor13

@quelqun_dautre: Une petite erreur à la ligne 17:
print (a, " à la puissance ", i, " = ", foo)
En tout cas, chez moi cela lève une exception.

Ca dépend de ta version de Python. Tu es en 3.x, je suis en 2.x

yjltg.

Feanor13

26 juillet 2011 à 23:32:32

Ok, je ne connaissais pas cette particularité. Une raison particulière pour laquelle tu code en 2.X ? Ou bien tu as juste décidé d'en rester à cette version.

@+

Anonyme

26 juillet 2011 à 23:40:22

Citation

on te donne trois entiers strictement positifs a, b et n, par exemple a=29, b=42 et n= 10 et on te demande de donner la n-ième décimale de la division «à virgule» de a par b.

Je sens que Candide ne va pas aimer... :-°

int(str(a/b).split('.')[1][n-1])

[edit] À propos de l'erreur que tu as relevé, Feanor13, il suffit de remplacer xrange, dans le code de quelqun_dautre par range.

Anonyme

27 juillet 2011 à 0:43:11

Je propose une fonction récursive pour la puissance

def power(a, b):
    if b == 0:
        return 1
    elif b == 1:
        return a
    elif b > 1:
        return a * power(a, b-1)

Pour le reste pas d'intérêt.

Il me semble Candide, je suis loin d'être poussé en Maths, qu'il existe plusieurs algorithmes pour la fonction puissance, ça serait intéressant de savoir quel algorithme a choisi Guido pour implémenter pow() ou **.

Je trouve que cet exo peut être un bon exercice pour les débutants en algorithme, ce n'est que mon avis, hein

Sinon je trouve inutile de rajouter un paramètre (une boucle). Le plus dur est le codage de la fonction power().

L'exercice en lui même est intéressant juste pour appliquer différents algorithme, mais totalement inutile en pratique comme dit précédemment, car la fonction pow() existe déjà en python, inutile donc de réinventer la roue.

Edit : Ma fonction itérative

def power(a, b):
    if b == 0:
        return 1
    elif b == 1:
        return a
    elif b > 1:
        result = 1
        for i in range(b):
            result *= a
        return result

Pour l'exercice de Candide

class Dec(object):
    def __init__(self, nombre, n_decimal):
        assert n_decimal > 0
        self.n = n_decimal
        self.nombre = nombre
        if isinstance(self.nombre, float):
            self.entier, self.decimal = str(self.nombre).split('.')
        else:
            raise TypeError("Votre nombre doit être de type float")
    def nieme_dec(self):
        if isinstance(self.n, int):
            return self.decimal[self.n-1]
        raise TypeError("n_decimal doit être de type int")
    def __str__(self):
        return "la valeur du {0}ème décimal est : {1}".format(self.n, self.nieme_dec())

print(Dec(29/42, 10))

la valeur du 10ème décimal est : 4

accaudran

27 juillet 2011 à 2:41:47

Bonsoir, voici ma solution:

def puissance(nb=1, deb=1, fin=1):

    for n in range(deb, fin+1):
        res = 1
        for _ in range(n-1):
            res *= nb
        print('{} à la puissance {} = {}'.format(nb,n,res))

puissance(5,3,6)

Pour l'exercice de Candide j'ai une solution, mais hyper sale

def excandide(a=29,b=42,n=10):

    r = int((a/b)*10**n)
    s = str(r)[-1]

    print(int(s))

excandide()

Je serais ravi de voir une meilleure solution.

EDIT:

Je me suis creusé la tête pour éviter de convertir en str() voici ma deuxième solution qui semble fonctionner:

def excandide(a=29,b=42,n=10):

    r = int((a/b)*10**n)
    res = r/10 - int(r/10)
    print(int((res+0.01)*10))

excandide()

candide

27 juillet 2011 à 8:41:53

Citation : fred1599

Il me semble Candide, je suis loin d'être poussé en Maths, qu'il existe plusieurs algorithmes pour la fonction puissance,

Je pense que Python délègue le calcul des puissances en général au runtime C ou Java. Pour les puissances strictement entières, c'est la méthode classique square and multiply (ce qu'a proposé quelqun_dautre ci-dessus mais en plus raffiné) mâtinée de Karatsuba, cf. le fichier source longobject.c .

Anonyme

27 juillet 2011 à 9:36:55

Citation : Asimoov

res = r/10 - int(r/10)

ça fait pas 0?

Citation : Asimoov

def excandide(a=29,b=42,n=10):

    r = int((a/b)*10**n)
    s = str(r)[-1]

    print(int(s))

excandide()

t'es sûr que c'est correct, on doit trouver 4, non?

Citation : Asimoov

def excandide(a=29,b=42,n=10):

    r = int((a/b)*10**n)
    res = r/10 - int(r/10)
    print(int((res+0.01)*10))

excandide()

Tu trouves 4? il y a des int en trop non?

quelqun_dautre

27 juillet 2011 à 10:26:21

Citation : Feanor13

Ok, je ne connaissais pas cette particularité. Une raison particulière pour laquelle tu code en 2.X ? Ou bien tu as juste décidé d'en rester à cette version.

Certaines bibliothèques n'existent pas encore en 3.x, alors pour des raisons de compatibilité je reste en 2.x

yjltg.

accaudran

27 juillet 2011 à 19:57:19

Bonsoir, fred non chez moi je trouves 4 et le résultat semble tomber juste même pour d'autres divisions et le résultat de res = r/10 - int(r/10) chez moi cela donne 0.3999999999....

Anonyme

27 juillet 2011 à 21:30:11

ça y est j'ai capté

oui ça me paraît logique maintenant, c'est parce-que en python version 2 ça peut pas fonctionner de cette manière.

yoch

28 juillet 2011 à 9:52:51

Citation : candide

Si tu veux un exercice plus intéressant, je t'en propose un :

on te donne trois entiers strictement positifs a, b et n, par exemple a=29, b=42 et n= 10 et on te demande de donner la n-ième décimale de la division «à virgule» de a par b.

Cet exo est tout de même orienté math, même si la solution requiert un peu d'algo. On peut aimer, comme ne pas...

Je crois avoir déjà fait pour project Euler, je ne vais donc pas le refaire car pas très intéressant.

Pour moi, on peut globalement classer les exercices comme ceci :

Niveau 1 (débutant) :
- usage d'algorithmes simples (boucles, conditions, etc.)
- maitrise de base du langage (modules, fonctions, chaines, listes, etc.)

Niveau 2 (intermédiaire) :
- algorithmes plus complexes (récursivité, combinatoire, etc.)
- maitrise plus avancée du langage (sets, dicts, lambdas, compréhensions, map, zip, etc.)

Niveau 3 (avancé) :
- réflexion algorithmique (complexité, techniques, etc.)
- maitrise poussée du langage (générateurs, décorateurs, <plein de trucs que je ne connais pas>, etc.)

Hors catégorie (niveau 2 minimum) :
- conception (POO, usage de libs tierces, GUI, etc.)

Il y a certains exos du project Euler que j'ai vraiment aimé d'un point de vue algorithmique, peut-être que je les proposerai un jour.

candide

28 juillet 2011 à 19:06:30

Citation : yoch

Cet exo est tout de même orienté math, même si la solution requiert un peu d'algo. On peut aimer, comme ne pas...

Pour ce qui est d'aimer ou pas, je suis d'accord et en fait c'est un facteur essentiel dans la capacité à résoudre un exercice. Maintenant, orienté math ? oui et non, disons que c'est maths niveau CM1 ou CM2

Parce qu'il s'agit juste de simuler avec Python une opération qu'en principe tout le monde sait faire : 29<42 donc en 290 combien de fois 42, il y va 6 qui est mon premier chiffre au quotient, 6 fois 42 ôté de 290 vaut 38 et on recommence en 380 combien de fois 42, etc

En code Python, ça donne :

n=29
d=42 # on doit avoir d < n
for i in range(100): # je veux la 100eme decimale
    n=10*n # mon nouveau reste
    q=n/d # en n combien de fois d (q : mon nouveau chiffre) ...
    n=n%d # ... et il reste
print q

Après on peut optimiser mais ce n'est pas le but. Pour moi il est essentiel d'apprendre (mais pas trop tôt) à reproduire en code des algorithmes ultra-naïfs. Beaucoup d'exos de l'école primaire (conjugaison, orthographe, arithmétique, conversions, etc) sont bons pour ça.

Citation : yoch

Je crois avoir déjà fait pour project Euler

Peut-être le Problème 26 mais qui était nettement moins facile que ce que je proposais

yoch

29 juillet 2011 à 0:12:36

Citation : candide

en fait c'est un facteur essentiel dans la capacité à résoudre un exercice.

Citation : candide

Maintenant, orienté math ? oui et non, disons que c'est maths niveau CM1 ou CM2 Parce qu'il s'agit juste de simuler avec Python une opération qu'en principe tout le monde sait faire : 29<42 donc en 290 combien de fois 42, il y va 6 qui est mon premier chiffre au quotient, 6 fois 42 ôté de 290 vaut 38 et on recommence en 380 combien de fois 42, etc

Tout à fait.

Peut-être que ma réaction est due à une overdose d'exos du project euler... Plus sérieusement, en programmation, j'aime les problèmes "concrets", même si leur résolution fait appel à des mathématiques poussées (pour moi qui ai malheureusement cessé les maths très tôt), mais j'aime nettement moins les problèmes "purement mathématiques", même si leur solution est absolument triviale. Pour "concret", il m'est difficile de cerner ma propre définition, car il y a des tas d'exercices parfaitement théoriques que je trouve "concrets" (questions de combinatoire, par exemple p. euler 114, 115, 116, 117).

Bref, il faudrait que je passe chez mon psy... :-°

Citation : candide

Peut-être le Problème 26 mais qui était nettement moins facile que ce que je proposais

Oui, il me semble.