Algorithme de calcul de x^n
Algorithme de calcul de x^n
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.
Est-ce que qulqu'un pourrait m'aider SVP?
Merci beaucoup
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.
Est-ce que qulqu'un pourrait m'aider SVP?
Merci beaucoup
Re: Algorithme de calcul de x^n
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 :
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.
Quant à ta question principale, j'ai peur de ne pas comprendrelet puissance (x : float) (a : int)
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).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.
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.
Re: Algorithme de calcul de x^n
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.
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é.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Algorithme de calcul de x^n
Je parlais bien de l'exponentiation rapide en fin de message, en évitant le nom pour ne pas qu'il le google :p
Re: Algorithme de calcul de x^n
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é.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Algorithme de calcul de x^n
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.
* 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/
MPI/MPI* (à partir de 2023) du Centre International de Valbonne
http://prepa.civfrance.com/
Re: Algorithme de calcul de x^n
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.
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.
Re: Algorithme de calcul de x^n
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?
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é.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Algorithme de calcul de x^n
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)...
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/
MPI/MPI* (à partir de 2023) du Centre International de Valbonne
http://prepa.civfrance.com/
Re: Algorithme de calcul de x^n
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"...
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é.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.