Algorithme de calcul de x^n

Répondre
Takiii

Algorithme de calcul de x^n

Message par Takiii » 09 févr. 2014 21:29

Bonjour,
Je souhaiterais rédiger un programme qui utilise l'écriture en binaire d'un nombre pour pouvoir calculer sa n-ième puissance.
J'ai pensé à découper son écriture binaire en chaînes de caractères (par exemple 1001 : 1, 0 ,0, 1) mais je ne sais pas comment le faire.
Je dois aussi vérifier que n est un entier naturel non nul, pour cela j'ai le module "assert" mais je ne sais pas comment exprimer cela. :cry:
Est-ce que qulqu'un pourrait m'aider SVP?
Merci beaucoup

Arky

Re: Algorithme de calcul de x^n

Message par Arky » 09 févr. 2014 23:58

Connaître le type d'une variable ? Tu es en quel langage ? Je connais assert en Caml, mais si c'est ce que tu utilises, ton programme le reconnaitra sans mal. Tu peux aussi l'imposer, pour te rassurer, en disant par exemple :
let puissance (x : float) (a : int)
Quant à ta question principale, j'ai peur de ne pas comprendre
Takiii a écrit :Je souhaiterais rédiger un programme qui utilise l'écriture en binaire d'un nombre pour pouvoir calculer sa n-ième puissance.
Si c'est l'écriture de x en binaire qu'il te faut utiliser, pourquoi vérifier que n est entier et pas faire de même avec x ? De plus, je crains que l'écriture binaire d'un nombre ne t'aide pas énormément pour le calcul de sa puissance n-ième, sauf dans des cas particuliers (les puissances de 10 en base 10, les puissances de 2 en base 2).

Par contre si c'était - par hasard - l'écriture en binaire de n qui t'intéressait, tu pourrais te demander comment utiliser ici un algorithme de type "diviser pour régner" pour calculer la puissance, dans le but de diminuer au maximum le nombre de multiplications à faire. Quand tu l'auras trouvé, l'intérêt de l'écriture binaire devrait vite se révéler à tes yeux.

EDIT : Je n'avais pas vu ta question "nombre -> chaine de caractères ?". Du coup je pense que tu ne dois pas utiliser Caml, sinon un simple coup d'oeil à la bibliothèque standard t'aurais donné ce que tu veux. Tu peux a priori simplement utiliser les fonctions string_of_int et int_of_string.

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Algorithme de calcul de x^n

Message par fakbill » 10 févr. 2014 14:38

Ou alors il a mal compris et il veut calculer x^n auquel cas on parle de l'algo expo rapide.
Takiii : quel est ton niveau en infoß
"assert" c'est le plus souvent (ca dépend du langage) un truc comme ca:
assert(x>0);
Le programme va s'arreter si jamais x n'est pas >0 lors de l'execution (techniquement parlant, ca va envoyer le signal abort au processus en question). Ca sert pour débugger.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Arky

Re: Algorithme de calcul de x^n

Message par Arky » 10 févr. 2014 15:43

Je parlais bien de l'exponentiation rapide en fin de message, en évitant le nom pour ne pas qu'il le google :p

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Algorithme de calcul de x^n

Message par fakbill » 10 févr. 2014 16:08

arf vu comme la question est posée je pense que ce n'est pas plus mal qu'il google...
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Messages : 187

Inscription : 05 mars 2011 22:24

Profil de l'utilisateur : Élève de lycée

Re: Algorithme de calcul de x^n

Message par Marc de Falco » 10 févr. 2014 18:40

Pour vérifier qu'un entier est naturel > 0 on peut le faire en deux temps :
* vérifier que c'est un entier en testant si son type est celui de 0 : type(n) == type(0)
* vérifier qu'il est > 0 : n > 0
On peut réunir ces conditions avec une condition logique.
Ensuite, j'imagine que ton professeur souhaite que tu utilises une pré-condition en début de fonction avec un assert. Tu écris donc juste assert(ma condition) et si la condition n'est pas vérifié => erreur à l'exécution.
Tant qu'à faire, profites-en pour faire une condition en entrée et en sortie de boucle et une avant de sortir de la fonction (et donc de t'assurer qu'un certain invariant est vérifié tout au long de l'algorithme).

Quant au problème initial. Tu sembles très loin d'avoir saisi le procédé car tu te focalises sur l'écriture en binaire qui est juste ce qu'on a du t'expliquer après avoir exposé la méthode. Nul besoin de calculer explicitement cette écriture.
Il suffit de remarquer la chose suivante : si n=2p alors x^n = (x*x)^p et si n=2p+1 alors x^n = (x*x)^p * x.

Je te recommande alors de passer par trois variables (e,k,r) telles que à tout moment x^n = e^k * r (c'est notre invariant).
Au départ on prend (x,n,1) et à la fin on espère arriver à quelque chose de la forme (y,1,r) pour avoir x^n = y * r ce qui est juste une multiplication.
Considère n pair ou impair et regarde comment ce triplet évolue.

Ensuite, il faut coder tout cela, mais le plus dur sera fait.

Ce serait bien aussi de réfléchir sur le nombre d'étapes.
Professeur d'informatique
MPI/MPI* (à partir de 2023) du Centre International de Valbonne
http://prepa.civfrance.com/

Takiii

Re: Algorithme de calcul de x^n

Message par Takiii » 12 févr. 2014 19:25

Merci beaucoup tout le monde! Merci surtout à Marc de Falco pour sa réponse très pertinente!
En effet, l'idée c'est d'élever au carré et multiplier x à chaque 1, élever au carré à chaque 0 de la décomposition de la puissance en binaire.
J'"utilise" python, mais je suis (encore) très débutante.
A vrai dire, je n'arrive pas à composer. J'ai pensé à utiliser dec2bin, puis transformer le nombre obtenu en liste de chaînes de une caractère, puis seuelement élever les x à chaque 1... Je ne crois même pas que ça soit faisable, vu que _ça doit se faire dans l'ordre et pas tout à la fois, c'est le but de la boucle for mais justement je ne saisis pas exactement le concept.

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Algorithme de calcul de x^n

Message par fakbill » 12 févr. 2014 22:31

Marc de Falco : oui bon les invariants de boucles et la complexité...on verra ça un peu après vu que l'a on est un problème classique de débutant.

Quand on débute, il faut d'abord avoir une idée très très précise de l'algo AVANT de coder quoique ce soit.
Qu'est ce que tu as en entrée? Qu'est ce que tu dois calculer?
Quelles sont les étapes de calcul?
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Messages : 187

Inscription : 05 mars 2011 22:24

Profil de l'utilisateur : Élève de lycée

Re: Algorithme de calcul de x^n

Message par Marc de Falco » 12 févr. 2014 22:57

fakbill : tu fais ce que tu veux avec tes élèves (cf signature ;-) ), mais il y a quand même un programme ! L'idée est de faire passer un peu d'invariant et de complexité dès le départ.
Maintenant, je reste fermement convaincu que pour certains exemples particuliers, il est plus facile de partir de l'invariant pour écrire le programme.
L'exponentiation rapide en récursif, c'est très naturel, mais en itératif beaucoup moins. Dans la même série, pour faire l'algorithme d'Euclide étendu, en remontant c'est facile mais en descendant, on voit très bien ce qu'il faut faire, mais c'est plus simple de partir de l'invariant pour dégager l'algorithme.
De plus, parler de complexité sur l'exponentiation rapide dans un second temps c'est assez bête, dans la mesure où ce problème n'a strictement aucun intérêt si on ne dit pas que le but est de calculer plus vite.
Maintenant, je pense tout de même qu'il est plus important qu'un élève comprenne comme on fait une recherche dichotomique (qui est explicitement au programme)...
Professeur d'informatique
MPI/MPI* (à partir de 2023) du Centre International de Valbonne
http://prepa.civfrance.com/

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Algorithme de calcul de x^n

Message par fakbill » 12 févr. 2014 23:36

Je n'ai pas d'élève et n'en aurait probablement jamais :)
Il y a un programme certes mais là on est face à qlqn qui mélange l'algo avec son implémentation....je pense donc que, dans CE cas précis, il y a d'autres choses à lui dire AVANT d'aller lui parler d'invariant.

"dans un second temps" : quel second temps??? Qu'il comprenne déjà la méthode et comprenne la différence entre l'algo et le code (ce qui n'est pas trivial qu'en on débute). Une fois que ce sera fait, on lui fera compter les opérations.

Si on est dans le cadre de l'info pour tous, il me semble aussi nécessaire de bien leur dire qu'en pratique ils n'auront JAMAIS à coder ça. Si on ne le dit pas, on va retrouver en stage des gens qui pense par exemple que recoder x^n avec cet algo "fera aller matlab plus vite"...
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Répondre