[PASCAL] Charge du stock (Délocalisation de variables)

Question

Bonjour,

Je dois indiquer, lors d'un exercice, si je peux "délocaliser" une variable "k" sans modifier l'effet de la procédure.

En réécrivant le code, j'ai trouvé si je peux ou pas. Dans mon cas, je NE PEUX PAS. Lors de la délocalisation de celle-ci, le résultat obtenu change.

MAIS, je ne sais pas expliquer pourquoi ... Comment peut-on expliquer ceci ?

voici mon bout de code :

	PROCEDURE CadreF1 (n: INTEGER): INTEGER;
PROCEDURE F1 (n: INTEGER): INTEGER;
VAR
k: INTEGER ; 	
BEGIN (*F1*)
IF n <= 1 THEN RETURN n END;
k := n - 2; 
RETURN F1(n-1) + F1(k)		
END F1;
BEGIN (*CadreF1*)
RETURN F1(n)
END CadreF1;	

Comme vous le voyez, c'est du pascal .... Mais je n'ai trouvé que "DELPHI" dans le menu ... 

merci d'avance à ceux qui peuvent m'aider ...

fbalien · Answer

Bonjour

ici tu ne peux pas délocaliser K car la fonction F1 est récursive
elle s'apelle donc donc elle même si tu délocalise K il est modifié par chaque appel de F1

A+

dj_noway · Answer

merci beaucoup pour ta réponse ... 

mais je ne comprends pas vraiment ....... peux-tu être plus précis ? éventuellement avec un exemple concret ? 

merci

f0xi · Answer

erf du pascal ...

F1 est recursive, c'est a dire, elle s'appelle elle même a chaque iteration.

deja y'a un probleme de declaration, identifiant identique n de CadreF1 et n de F1.

f0xi · Answer

d'ailleur je ne comprend pas la justification de K.

elle me semble inutile puisqu'on peu resoudre a 

retrun F1(n-1) + F1(n-2);

ni69 · Answer

Ah, ce cher Fibonacci!


Je rejoins f0xi pour souligner ici l'inutilité de la variable K, mais pas seulement !
Pourquoi donc créer une procédure CadreF1, alors que F1 se suffit à elle-même ?


procedure Fibonacci(n: integer) : integer;
begin
  Case n of
    0..1 : return n;
    else return ( Fibonacci(n-1) + Fibonacci(n-2) );
  end;
 end;


Mais attention tout de même, une méthode récursive n'est pas la meilleure façon de calculer un nombre de la suite de Fibonacci, car elle a une complexité exponentielle en terme de nombre d'opérations  

@+
Nico { www.ni69.info }

f0xi · Answer

function FibonacciF(const N: byte): Extended;
var I : integer;
    A,B: Extended;
begin
  A := 0;
  B := 1;
  result := N;
  for I := 2 to N do
  begin
    result := A + B;
    A      := B;
    B      := result;
  end;
end;

function Fibonacci(const N: byte {0..92}): UInt64;
var I : integer;
    A,B: UInt64;
begin
  A := 0;
  B := 1;
  result := N;
  for I := 2 to N do
  begin
    result := A + B;
    A      := B;
    B      := result;
  end;
end;

ni69 · Answer

OK pour le code de f0xi, qui a une complexité en O(n). On peut cependant faire encore mieux (!) avec une complexité en O( ln[n] ), ceci en raisonnant de manière matricielle.

Je passe les détails, mais cela devrait donner quelque-chose comme ça: 

type
  Int64Couple = array[0..1] of Int64;
 
 
function Fibonacci(n: integer): Int64;

  function FibonacciSteps(n: integer): Int64Couple;
  var
    fk : Int64Couple;
    fk0, fk1, fk0sq, fk1sq : Int64;
  begin
    case n of
      0 : begin
          result[0] := 1;
          result[1] := 0;
          end;
      else begin
        fk := FibonacciSteps(n div 2);
        fk0 := fk[0];      fk1 := fk[1];
        fk0sq := fk0*fk0;  fk1sq := fk1*fk1;
        case n mod 2 of
          0 : begin
              result[0] := fk1sq + fk0sq;
              result[1] := fk1*fk0*2 + fk1sq;
              end;
          1 : begin
              result[0] := fk1*fk0*2 + fk1sq;
              result[1] := (fk1+fk0)*(fk1+fk0) + fk1sq;
              end;
        end;
      end;
    end;
  end;

begin
   result := ((FibonacciSteps(n))[0]);
end;


Après, ça c'est du delphi, et il faudra faire deux/trois modifs pour que ça marche pour du Pascal 
 
@+
Nico { www.ni69.info }

[PASCAL] Charge du stock (Délocalisation de variables)

7 réponses

Votre réponse

Discussions similaires