Discussion :

[aurelie0192]

Bonjour à tous, merci de prêter attention à mon message.

Je me trouve en difficulté avec cet exercice. C'est un exercice donné à titre indicatif par mon professeur pour s'entraîner au concours. Cet exercice concerne la fonction puissance en TURBO PASCAL.

• 1. On appelle la fonction puissance appliqué à un réel x quelconque et un entier n que l'on suppose impair et strictement supérieur à 1. Combien d'opérations élémentaires sont faites ?
• 2. Meme question avec n=1
• 3. Même question avec n=0
• 4. On s'intéresse désormais au nombre N d'appels de la fonction puissance lorsqu'on appelle puissance (x,n) (l'appel initial de puissance (x,n) ne compte pas)
  • a) Lors de l'appel de puissance(x,4) montrer que la fonction puissance est appelée 2 fois. On pourra détailler les opérations faites avec un arbre.
  • b) Même question avec puissance (x,7)
  • c) A partir de maintenant, n est un entier naturel quelconque. On note alors (ak) la suite des puissances que l'on utilise lors de l'appel de puissance (x,n). Par exemple, si n=9, alors a0 = 9, a1=(9-1)/2 =4, a2=4/2=2, a3=2:2=1 et on s'arrete ici : pour calculer puissance (x,1) aucun appel de puissance n'est effectué ( si on continuait on aurait a4=0, a5=0/2=0 , ... ) . Ainsi puissance(x,9) nécessite 3 appels de la fonction puissance.
    De façon formelle, on définit la suite (ak) par a0=n et
    pour tout k appartenant à N , ak+1 = ak/2 si ak est pair et (ak-1)/2 sinon .
    A) Montrer que pour tout k appartenant à N, ak est un entier naturel .

Alors je sais que la fonction puissance correspond à cela :

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
function puissance(x:real ; n:integer) : real ;
var u : real ;
begin
if n>1 then
begin
if ( n MOD 2 ) = 0 then
begin
u:=puissance ( x, n DIV 2 ) ;
puissance := u*u ;
end
else
begin
u := puissance (x, (n-1) DIV 2);
puissance := u*u*x
end ;
end
else
begin
If n=0 then puissance :=1 else puissance := x ;
end;
end;

je sais aussi que n MOD 2 = 0 seulement si n est pair et n MOD 2 = 1 seulement si n est impair.
Opérations élementaires : addition , multiplication, soustraction, division, affectation, appel à une fonction ou à une procédure (dont utilisation de MOD et DOV), comparaison.

Si il y a quelques as de Pascal qui peuvent élucider mon problème je serais fort ravie. Bien cordialement. Aurélie. Bonne journée à vous.

[Roland Chastain]

Bonsoir !

Il faut mettre des balises autour de ton code.

Il faut aussi l'indenter, pour en faciliter la lecture.

Autrement, tu as toutes les connaissances dont tu as besoin pour faire l'exercice. Il ne te reste plus qu'à te mettre au travail.

J'ai cherché la réponse à la première question. J'imagine que n est égal à 3, et je regarde ce qui se passe. Ensuite j'essaie avec 5. Ça me suffit à savoir ce qui se passerait pour 7, 9...

Un indice : tu remarqueras qu'il y a une partie du code qui est exécuté une seule fois dans tous les cas.

[aurelie0192]

Ce n'est vraiment pas de mauvaise volonté, j'ai cherché toute l'après midi cette exercice, mais en vain. Je ne vois même pas pour la question 1.
Merci de votre aide.
Bien cordialement.

[Roland Chastain]

Voyons ce qui se passe si n est égal à 3.

Est-il plus grand que 1 ?

Code :

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

if n > 1 then

Oui, donc c'est le code suivant qui sera exécuté :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
  begin
    if (n mod 2) = 0 then
    begin
      u := puissance(x, n div 2);
      puissance := u * u;
    end
    else
    begin
      u := puissance(x, (n - 1) div 2) ;
      puissance := u * u * x
    end ;
  end

n est-il pair ?

Code :

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

if (n mod 2) = 0 then

Non. Pour le savoir on a effectué une opération élémentaire (utilisation de mod).

Puisque n est impair, c'est donc le code suivant qui s'exécutera :

Code :

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

1
2
3
4
    begin
      u := puissance(x, (n - 1) div 2) ; // 4 opérations élémentaires
      puissance := u * u * x // 3 opérations élémentaires
    end ;

Nombre d'opérations jusqu'ici : 8.

Mais ce n'est pas fini, puisque la fonction puissance a été appelée une nouvelle fois, avec la valeur 3 - 1 div 2 c'est-à-dire 1.

Que se passe-t-il quand la fonction est appelée avec la valeur n = 1 ?

Code :

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

1
2
3
begin
If n=0 then puissance :=1 else puissance := x ; // 1 opération
end;

Nombre d'opérations : 8 + 1 = 9.

Maintenant, si n = 5, combien d'opérations y aura-t-il en plus ?

[droggo]

Qua,

On est typiquement dans un cas où la récursivité est une aberration.

[Roland Chastain]

On est typiquement dans un cas où la récursivité est une aberration.

Oui, c'est la conclusion à laquelle on arrive en étudiant le code proposé. Il faudrait peut-être ajouter un avertissement dans l'énoncé. "Ne faites pas ça chez vous !"

Si on a besoin d'une fonction puissance en Pascal, inutile d'aller chercher midi à quatorze heures.

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
function puissance(x: real; n: integer): real;
{ n entier naturel }
var
  u:  real;
  i: integer;
begin
  if n = 0 then
    puissance := 1
  else
    begin
      u := 1;
      for i := 1 to n do u := u * x;
      puissance := u;
    end;
end;

[l_autodidacte]

Et pour un mathématicien, une fonction puissance serait plus simple en se débarrassant des conditions multiples excepté celle concernant la positivité du réel dont on calcule la puissance d'ordre n :

Code :

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

1
2
3
4
Function Puissance(x:Real;n:Integer) : Real;
   Begin
     Puissance:=Exp(Ln(x)*n);
   End;

[droggo]

Hia,

Oui, mais bonjour le crash si x <= 0.

Et en plus, passer par un log diminue la précision du calcul*, et augmente sérieusement le temps de calcul*.

* et * : bien que le fait d'utiliser des real ne favorise pas ces points, c'est le moins qu'on puisse dire.

[aurelie0192]

Merci beaucoup pour votre aide, vraiment !
Donc si j'ai bien compris pour la question 2. avec n=1 , il y a 3 opérations élementaires et pour la question3. avec n=0 il y a 2 opérations élementaires ?
Merci d'avance . et si vous avez des pistes pour la question 4 , serais ravie de votre aide. Cordialement.

[Roland Chastain]

Tu as compris le principe.

Pour la question 1, je m'aperçois que j'ai oublié de compter les comparaisons (<, >, =) donc ma réponse est à corriger.

Pour les questions 2 et 3, il me semble qu'avec n = 0 ou n = 1 le nombre d'opérations est le même (3, deux comparaisons et une attribution).

Pour la dernière question je vais regarder ça dans l'après-midi.

Bon courage !

[aurelie0192]

pour la question 1, il y a donc 11 opérations élementaires ?
Merci beaucoup !

[Roland Chastain]

Donc je rectifie la réponse que j'avais donnée, pour n = 3.

Pour n = 3, si je compte bien il y a 13 opérations élémentaires. Pour n = 5, il y en a 23, etc. Bref, pour tout n impair, le nombre d'opérations est égal à 5 * (n - 1) + 3. Pour tout n pair, c'est 5 * n + 3.

Si je me sers du signe div, comme on fait en Pascal, pour symboliser la division euclidienne (division qui donne un résultat entier et un reste), je dirai que pour tout n, pair ou impair, le nombre d'opérations est 10 * (n div 2) + 3.

Pour la quatrième question : dire qu'on divisera un nombre par deux s'il est pair, ou qu'on lui retirera un puis qu'on le divisera par deux s'il est impair, cela revient à dire que dans tous les cas on le divisera par deux en utilisant une division euclidienne. Donc il est évident que tous les termes de la suite sont des nombres entiers.

J'espère t'avoir aidé à comprendre l'exercice. Vérifie les résultats que je t'ai donnés : je me suis peut-être trompé quelque part.

[aurelie0192]

oui merci beaucoup pour votre aide, très benefique .

Pour la question 1, on a bien 11 opérations ?

et pour n=0 , on suppose donc que 0 est impaire ?
puisqu'on trouve que n=0 et n=1 ont tout deux trois opérations élementaires ?

Merci beaucoup.

[Roland Chastain]

Pour la question 1, on a bien 11 opérations ?

La question 1 porte sur

un entier n que l'on suppose impair et strictement supérieur à 1.

J'ai cherché la réponse pour n = 3, pour n = 5 et j'en ai déduit la réponse pour tout n impair et strictement supérieur à 1. Pour le détail relire mon message précédent.

on suppose donc que 0 est impair ?

n mod 2 veut dire : le reste d'une division euclidienne de n par 2.

Zéro divisé par deux égale zéro, reste zéro. Oui, zéro est un nombre pair.

[aurelie0192]

Merci beaucoup.. tous mes camarades disent trouver 10 pour la première question.. je ne comprends pas comment :/

[Roland Chastain]

tous mes camarades disent trouver 10 pour la première question..

Ils trouvent 10 pour n = 3, n'est-ce pas ?

Mais c'est sans compter que la fonction s'appelle elle-même à cet endroit :

Code :

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

u := puissance(x, (n - 1) div 2) ;

La valeur passée en paramètre est 1, ce qui fait trois opérations supplémentaires, sauf erreur de ma part.

Donc je maintiens ma réponse.

[aurelie0192]

ils ne sont pas passer par n=3 mais ont directement compter de manière ''brut'' sur le programme et trouvent tous 10.
Selon vous , c'est donc 13 ?
Merci vraiment . Cordialement.

[Roland Chastain]

ils ne sont pas passer par n=3 mais ont directement compter de manière ''brut'' sur le programme et trouvent tous 10.
Selon vous , c'est donc 13 ?

Pour n = 3, c'est 13.
Pour n = 5, c'est 23.
Pour n = 7, c'est 33...

Si n est plus grand, il doit y avoir plus d'opérations pour arriver au résultat, non ?

[ZOUARI4U]

Oui, c'est la conclusion à laquelle on arrive en étudiant le code proposé. Il faudrait peut-être ajouter un avertissement dans l'énoncé. "Ne faites pas ça chez vous !"

Si on a besoin d'une fonction puissance en Pascal, inutile d'aller chercher midi à quatorze heures.

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
function puissance(x: real; n: integer): real;
{ n entier naturel }
var
  u:  real;
  i: integer;
begin
  if n = 0 then
    puissance := 1
  else
    begin
      u := 1;
      for i := 1 to n do u := u * x;
      puissance := u;
    end;
end;

tu peut supprimer la condition
tout simplement

Code :

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

1
2
3
u := 1;
      for i := 1 to n do u := u * x;
      puissance := u;