[Algo] A à la puissance B

**Darkenshin** · 21/09/2006, 14h55

Bonjour,

Voila j'ai fait un petit algo pour mettre un nombre A^B.
J'aimerai savoir si cette algo est correct ou non, il me semble que j'ai repris "tous" les cas pour les puissances d'un entier.

Voila l'algo en question (il s'agit d'une fonction)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
Fonction puissance (E: A,B : entier) : entier
 
Déclaration
I, Pows, Z : entier
 
Début
Pows = A
 
Si A ! = 0 et B = 0
	Alors Retourner 1
	Sinon 
	Si A = 0 et B > 0
		Alors 
		Retourner 0
	Sinon 
	Si (A = 0 et B = 0) ou (A = 0 et B < 0)
		Alors 
		Retourner "Je ne sais pas quoi mettre car il faut un entier or c'est une forme inderterminée"						
	Sinon 
	Si A > 0 et B > 0
		Alors
			Pour I allant de 1 à B faire
				Pows <- Pows*A
			Fin Pour
		Retourner Pows			
	Sinon
	Si A > 0 et B < 0
		Alors
			Z = B * -1
			Pour I allant de 1 à Z faire
				Pows <- Pows/A
			Fin Pour
		Retourner Pows	
	Sinon
		Si A < 0 et B < 0
			Alors
				Pour I allant de 1 à -B faire
					Pows <- Pows/A
				Fin Pour
			Retourner Pows	
	Sinon
	Si A < 0 et B > 0
		Alors
			Pour I allant de 1 à B faire
				Pows <- Pows*A
			Fin Pour
			Retourner Pows	
	Fin Si		
	Fin Si		
	Fin Si	
	Fin Si	
	Fin Si		
	Fin Si		
Fin Si	
 
Fin puissance

Les questions que je me pose sont les suivantes:
Es-ce que l'algo est correcte ?
Es-ce qu'il n'y a pas plus simple pour calculer des puissances d'entier en "intératif" ?

J'ai aussi un problème pour la forme indeterminée que ce que je peux renvoyer car c'est de l'entier or il faudrait retourner une chaîne de caractère.

Il est vrai que je me suis inspiré d'un programme en C pour faire l'algo (je suis une bille en algo

et encore plus en math

)

Merci de votre aide

.

Cordialement,
Darkenshin.

.: Edit :.
Correction au niveau de l'initisalition et de la pagination

**Scorpyosis** · 21/09/2006, 15h11

Moi je te propse ceci, qui devrait marcher et est plus simple, il y a une erreur dans ton algo, tu n'initialiser jamais pows ! donc tu auras toujours 0 comme résultat !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
I,Resultat : entier
Resultat = A 
 
Si A = 0 
	si B <= 0
		EXCEPTION //en algo je sais pas lever d'exception moi :cry: 
	Fin si
	retourner 0
Sinon
	si B = 0 
		retourner 0
	sinon
		pour I = 1 à (B - 1 )			
			Resultat = Resultat * A
		fin Pour
	fin si
Fin Si
 
si B < 0 alors
	resultat = 1 / resultat
fin si
 
retourner resultat

**Darkenshin** · 21/09/2006, 15h22

Salut,

J'avoue que je ne peux pas tester mon algo vu le pc que j'ai actuellement
Justement je me suis demander si il ne fallait pas initialiser ma var, ce que j'avais commencé à faire et puis supprimer car je l'ai refait car je me suis rendu compte que je ne gére qu'un seul cas.

Je vais regarder de plus près ton algo

Merci

Cordialement,
Darkenshin.

**borisd** · 21/09/2006, 17h02

Juste une petite correction : pour tout a non nul, a^0=1.
On devrait donc initialiser Resultat à 1 puis effectuer la boucle de 1 à B.

**thewho** · 21/09/2006, 17h12

Bonjour,

Je n'ai pas regardé ton algo, c'est juste pour faire une petite remarque:

Indenter le code, c'est bien.

MAIS, il faut rester raisonnable sur la taille l'incrément d'indentation, car, sincèrement, tu trouves que ton code est facile à lire ?

Une indentation de 2 caractères par bloc suffit normalement, sans avoir besoin ensuite d'un écran 36 pouces pour lire sans avoir à se balader de gauche à droite avec les scrollbars.

**Darkenshin** · 21/09/2006, 17h31

@borisd: j'y penserai merci

@thewho: vu les conditions de travail que j'ai je ne peux pas faire non plus autrement que d'incrémenter de cette façon.
J'avais prévu d'éditer mon code une fois chez moi

**PRomu@ld** · 21/09/2006, 19h29

Pour un algorithme d'exponentiation entière , c'est pas très efficace en itératif. Le mieux est d'utiliser une forme récursive :

Algo : Exponentiation entière rapide.

Entrée:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
x : nombre entier ou réel.
n : nombre entier positif.

Sortie

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

x à la puissance n : x^n

Pseudo-Code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
EXPONENTIATION( x , n )
DEBUT
SI n = 0 ALORS
    RENVOYER 1
SINON 
    SI n = 1 ALORS
        RENVOYER x
    SINON
        SI n est pair ALORS
            RENVOYER EXPONENTIATION( x, n/2 ) * EXPONENTIATION( x , n/2 )
        SINON
            RENVOYER x * EXPONENTIATION( x , n/2 ) * EXPONENTIATION( x , n/2 )
        FIN SI
    FIN SI
FIN SI
FIN

Complexité :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
O( ln n )

**j.p.mignot** · 21/09/2006, 21h23

pour rappel A^B = exp ( B*ln(A)) A > 0
plus rapide que récursif si A, B sont entiers >=0

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
function A_puiss_B( A, B : word) : word;  
var i : word;
   begin
   i:=1;
   while B > 0 do
      begin
      i := i*A;  // ici il faut tout de même s'assurer que i*A reste codable sur le type choisi
      dec (B);
      end;
   A_puiss_B := i;  // ici 0^0 donne 1 comme lim(x^x  lorsque x-> 0 )
   end;

**Hephaistos007** · 21/09/2006, 22h45

Et pourquoi pas tout simplement (pour x,n >=0) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
EXP( x , n )
DEBUT
SI n = 0 ALORS
    RENVOYER 1
SINON 
    RENVOYER (x * EXP(x, n-1))
FIN SI
FIN

**Darkenshin** · 21/09/2006, 23h17

@PRomu@ld, il est vrai que ça serait plus simple en récursif seulement je ne suis pas encore tout a fait au point à ce niveau là.

Comme dit ce que tu me montre là est très bien le seul problème c'est que je suis une grosse bille en maths

, pour moi ton "EXPONENTIATION( x , n/2 )" ne me parle en rien :s désolé.

@j.p.mignot, ton algo me parle encore moins que celui de PRomu@ld de plus j'avoue ne pas connaitre cette structure d'algorithme.

@Hephaistos007, merci cette algo me parle un peu plus.

Je penses que vous avez remarqué qu'il s'agit d'un exercice de cours basique et j'ai des contraintes comme le fait que les 2 nombres peuvent être positif, négatif, voir null, j'ai fait cette algo depuis un programme en C ce qui explique le fait qu'il ne soit pas forcement le mieux, le plus simple, le plus rapide, le plus optimisé ceci dit en thèorie il fonctionne après quant à savoir si est le bon je ne sais pas trop ^^

J'aimerai quand même rester sur l'algo que j'ai fait, je vous remercie des réponses que vous m'avez donné.

Serait-il possible de corriger celui-ci au lieux de partir sur d'autre algo ?
Merci par avance

Cordialement,
Darkenshin.

**millie** · 22/09/2006, 09h58

L'algorithme de Scorpyosis fait les mêmes choses que le tiens, mais avec une notation beaucoup plus propre. Il reste juste les exceptions à gérer (par exemple 0^0 qui n'est pas définie). Je te conseille donc de prendre celui là si tu ne veux pas faire de récursif.

Sinon, pour d'autres personnes qui souhaiteraient faire cela, c'est vrai que l'algo de @PRomu@ld est le mieux de ceux proposé car beaucoup plus rapide.

La fonction de calcul de A^B de @PRomu@ld s'appelle EXPONENTIATION, c'est donc cette fonction qu'il appelle dans son algorithme (donc programmation récursive) mais qui est de bien meilleure complexité comme il l'a fait remarqué.

**Darkenshin** · 22/09/2006, 10h28

@millie, Tu parles de "l'algorithme de Scorpyosis" or je ne l'ai pas vu

Je peux aussi simplifié mon algo

au départ j'avais fait ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Fonction puissance (E: A,B : entier) : entier

Déclaration

I, Pow : entier

Début

            Pows <- A

            Pour I allant de 1 à B faire

                        Pows <- Pows*A

            Fin Pour

            Retourner Pows

Fin puissance

Qui est quand même un poil simpliste surtout quand il faut gérer positif, négatif, nulle

**lyxthe** · 22/09/2006, 10h40

juste pour dire, si j'ai bien compris l'algo de Promu@ld , il manque quelque chose de ce genre là je crois :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
        SINON
            n=n-1
            RENVOYER x * EXPONENTIATION( x , n/2 ) * EXPONENTIATION( x , n/2 )
        FIN SI

enfin je pense que je suis pas le seul à l'avoir remarqué mais c'est quand même interessant de le rajouter...
Ou alors j'ai strictement pas compris l'algo.

**PRomu@ld** · 22/09/2006, 10h56

Envoyé par lyxthe

juste pour dire, si j'ai bien compris l'algo de Promu@ld , il manque quelque chose de ce genre là je crois :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
        SINON
            n=n-1
            RENVOYER x * EXPONENTIATION( x , n/2 ) * EXPONENTIATION( x , n/2 )
        FIN SI

enfin je pense que je suis pas le seul à l'avoir remarqué mais c'est quand même interessant de le rajouter...
Ou alors j'ai strictement pas compris l'algo.

En fait, tu as compris l'algo, je pense, mais ce que tu n'as pas compris, c'est l'opérateur /, il s'agit de la division euclidiène. Ainsi, 5 / 2 vaut 2.

**lyxthe** · 22/09/2006, 11h01

au temps pour moi. Mais je suis quand même content d'avoir saisi le truc :p

**millie** · 22/09/2006, 12h42

Tu parles de "l'algorithme de Scorpyosis" or je ne l'ai pas vu

Je cite, scorpyosis a écrit à son premier post cet algorithme là.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
I,Resultat : entier
Resultat = A 
 
Si A = 0 
	si B <= 0
		EXCEPTION //en algo je sais pas lever d'exception moi :cry: 
	Fin si
	retourner 0
Sinon
	si B = 0 
		retourner 0
	sinon
		pour I = 1 à (B - 1 )			
			Resultat = Resultat * A
		fin Pour
	fin si
Fin Si
 
si B < 0 alors
	resultat = 1 / resultat
fin si
 
retourner resultat

Et qui gère tous les cas.

**Darkenshin** · 22/09/2006, 16h13

Oups merci autant pour moi millie

Merci à tous c'est réglé

**Jean-Marc.Bourguet** · 22/09/2006, 16h23

Envoyé par PRomu@ld

Complexité :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
O( ln n )

Ah bon? Je serais d'accord si on évitait le double appel récursif, mais comme il est présent deux fois...

L'algo que tu voulais, mais avec la recursivité enlevée:

Pour n entier positif ou nul:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
resultat = 1.0;
facteur = a;
while n != 1 loop
   if n mod 2 = 1 then 
      resultat = resultat*facteur;
   end if;
   facteur = facteur*facteur;
   n = n / 2;
end loop;

**j.p.mignot** · 22/09/2006, 19h04

Tout à fait d'accord que l'algorithme ci-dessus est en O(ln(n)) et celui que j'ai
donné est en O(n).
Toutefois pour une puissance de 10 on va gagner environ un facteur 3 sur les itérations mais avec un test 'if' et un 'modulo'. Est ont- vraiment encore gagnant ?
Pour des puissances élevées, de toute façon le problème sera un problème de codage.
Même avec n=a = 10, a^n = 1001010100000010111110010000000000 => 34 bits
ce qui dépasse déjà le LongWord...
Donc TRES rapidement il faudra passer en float (=> incertitudes sur résultat ) ou utiliser des manipulations du codage de très grands entiers ( il existe des débats à ce sujet sur ce forum ) ce qui n'est pas forcement si aisé ni sans conséquence sur a vitesse. De plus de tels entiers peuvent vraiment être problématiques sur certains processeurs.

**PRomu@ld** · 22/09/2006, 19h39

Envoyé par Jean-Marc.Bourguet

Ah bon? Je serais d'accord si on évitait le double appel récursif, mais comme il est présent deux fois...

Oui, je n'ai fait qu'appliquer une formule mathématique pour produire un algo. Le double appel récursif dépend, il me semble, du langage et/ou du système utilisé. (mapple il me semble mémorise les appels récursifs).

Mais en toute rigueur, tu as raison, ayant personnellement effectué certaines hypothèses

[Algo] A à la puissance B

Algorithmes et structures de données

Discussions similaires

Partager

Partager