LARP: Algorithme qui lève un nombre à la puissance (1/2)
Fermémamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 19 avril 2023 à 12:19
4 réponses
16 avril 2023 à 18:37
16 avril 2023 à 19:12
Bonjour,
Contradiction:
en 1: n du type entier
en 2: n=1/2 qui n'est pas un entier
Le rédacteur de l'exercice attend certainement une réaction à cette contradiction.
19 avril 2023 à 12:19
Oui, je pense aussi que le but de l'exercice est de sensibiliser les étudiants avec les types attendus par une fonction (dans le code proposé, pow ne marche qu'avec des entiers positifs) et la documentation qu'on l'ont est supposé y adjoindre, car ici la fonction retournera 1 si la puissance est dans [0, 1[.
Pour de petites valeurs de n, on peut multiplier x n fois dans une simple boucle.
Mais si n est assez grand, le temps de calcul est nettement plus long et il y a moyen de faire mieux.
Puisque ce n'est pas moi qui ai inventé la pédagogie ...
x^14 = x^8 * x^4 * x^2
x^7 = x^4 * x^2 * x^1
x^5 = x^4 * x^1 (x^2 n'est pas là)
x^6 = x^4 * x^2 (x^1 n'est pas là)
Voici un exemple:
Si on prend la représentation binaire de n et si on calcule les puissances successives de x, on peut faire le calcul plus rapidement.
La vitesse est approximativement proportionnelle au logarithme en base 2 de n.
Voici du code en C pour l'illustrer:
#include <stdio.h>
double power(double x, int n) {
double a = 1; // Accumulateur
int r = (n >= 0) ? 1 : -1; // +1 si n positif, -1 sinon
n *= r; // Valeur absolue
while(n > 0) { // Tant que n n'est pas nul
if(n&1) { // Si le bit 0 vaut 1 (unités en base 2)
a *= x; // Accumuler en multipliant
}
x *= x; // Puissance suivante de x (x^2, x^4, x^8, etc.)
n /= 2; // On divise n par 2
}
if(r > 0) // Si n était positif
return a; // On retourne l'accumulateur tel quel
else // Si n était négatif
return 1 / a; // On retourne l'inverse
// Note: je ne vérifie pas que x soit égal à 0
}
int main(void) {
// Quelques tests.
printf("%f\n", power(2, 6));
printf("%f\n", power(1.5,2));
printf("%f\n", power(3, 3));
printf("%f\n", power(3, 7));
printf("%f\n", power(-3, 4));
printf("%f\n", power(-3, 5));
printf("%f\n", power(2, -2));
printf("%f\n", power(3, -3));
return 0;
}
17 avril 2023 à 07:47
Bonjour Pierrot.
UtilisateurDeLarp a su résoudre la question 1, il a posté une image de son code.
Son problème, et il l'a clairement écrit (donc ça ton logiciel vocalisateur doit te l'avoir dit) est de calculer la puissance 1/2 (donc la racine carrée) en se servant de la fonction écrite précédemment. alors que cette fonction prend un entier comme puissance.
C'est pour cela que je l'ai orienté vers le calcul de la racine carrée à la main.
