Discussion :

[Sadgunner]

Bonjour, je suis étudiant en première année de licence informatique, et j'ai un problème afin de résoudre un exercice. Voici mon problème ..

Le but est d'établir la preuve d'un programme pascal, un algorithme de calcul de la factorielle d'un naturel.

l'assertion P est :

k <= n
n et la valeur de k sont de meme parité
q = (k-1)k
f = k!

la condition C est :

k < n

Et I l'instruction :

begin
q := q + 4*k +2
f := f*q
k := k+2
end

La question est : Quelles valeurs donner aux variables k,q et f avant l'execution de la boucle pour qu'à la terminaison de celle-ci la valeur de la variable f soit n!

J'ai essayé de partir de l'état final ( f = n!, d'ou k =n .. ), mais je n'arrive pas à avancer ..

Merci d'avance de votre aide.

[Eric Sigoillot]

Bonjour,

Il va fallir exposer un peu mieux ton problème, parce que tel quel, il est incompréhensible.
Quelle est la boucle ? Où est le programme ? Il n'y a pas d'entrée, pas de sortie...

Bref, là, on ne peut rien pour toi.

@++

[Sadgunner]

Merci quand même d'avoir pris la peine de répondre, mais j'ai fini par comprendre. . Si on prend k = n mod 2, f = 1, et q = 0, ca marche. Voici un exemple si certaines personnes en trouveront l'utilité un jour :

Exemple pour n = 0:0! = 1

k = n mod 2 = 0;
f = 1;
q = 0;
la condition k < n est fausse, donc la boucle n'est pas executée.
résultat: f = 1 = 1!

exemple pour n = 3:3! = 6

k = n mod 2 = 1;
f = 1;
q = 0;
la condition k < n est vraie, donc boucle est executée:
q := q + 4*k +2 = 6;
f := f * q = 6;
k := k+2 = 3;

la condition k < n est fausse, donc boucle s'arrête.
résultat: f = 6 = 3!

Et ainsi de suite...

[Tuxico]

euh il y a beaucoup plus simple pour faire un calcul de factorielle

[Sadgunner]

Oui il y a plus simple, mais cet algorithme diminue sensiblement le nombre de multiplications entre entiers en comparaison de l'algorithme usuel .. Qui était le principe de l'exercice.

[diden138]

il y'a beacoup plus simple franchement le calcule d'un factoriel se fait en une seule ligne de code enfin presque..

Code :

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

1
2
 
n!:=n(n-1)*(n-2)****1;

pourqoi faire une boucle se compliquer la vie
ecrire l'algorithme d'un programme se resume aussi a gagner du temp
pour ta solution elle est juste j'ai pas bien compri le but de l'exercise
ps:j'ai rien compri a ton programme parfoi tu met des affectation parfoi des egalité
@++

[Tuxico]

n!:=n(n-1)*(n-2)****1;

déja tu n'implémentes pas ca comme ca ^^ ensuite il a répondu en donnant le but de son exercice...Il avait un énoncé précis au départ

ps: la forme "usuelle"

Code :

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

1
2
3
4
5
6
7
8
n := X;
fact := 1;
 
while(n>=1) do
begin
     fact := fact*n
     n := n -1;
end;

ps:j'ai rien compri a ton programme parfoi tu met des affectation parfoi des egalité

les égalités sont des exemples de résultat....

[Eric Sigoillot]

Ah bon, moi je l'implémente comme ça :

Code :

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

1
2
3
4
5
6
(define (fact n)
    (define (fact-rec n t)
        (if (= n 0)
            t
            (fact-rec (- n 1) (* n t))))
    (fact-rec n 1))

Comme quoi, on peut faire ça de plein de manières différentes.

Sinon, je vaius écrire en Pascal l'algorithme proposé par Sadgunner, histoire qu'il puisse reservir

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
function Fact(const n: Integer): Integer;
var
  k, q, f: Integer;
begin
  f := 1;
  q := 0;
  k := n mod 2;
 
  while k < n do
  begin
    q := q + 4*k + 2;
    f := f * q;
    k := k + 2;
  end;
 
  Fact := f;
end;

Ce serait sympa de nous donner la preuve mathématique de l'algo, elle n'est pas directe (et j'ai pas envie de la faire ).

@++

[Tuxico]

Ah bon, moi je l'implémente comme ça :
Code :

(define (fact n) (define (fact-rec n t) (if (= n 0) t (fact-rec (- n 1) (* n t)))) (fact-rec n 1))

ah oui je n'avais pas vu ca comme ca

si j'ai le temps demain je ferai la preuve de l'algo

[Mihaela]

On prouve par induction que à chaque pas k :
q = (k+1)*(k+2) (#)

k varie par pas de 2 et et chaque étape on multiplie f par q, donc à chaque pas k f contient (k+2)!
Avant la boucle on établit clairement la parité de n et on choisi correctement le k de départ (0 ou 1).

Calcul pour (#) : supposons (#) vrai pour k,
à l'étape d'après, en début de la boucle while
q := q+ 4(k+2) + 2 = (K+1)*(k+2) + 4k + 8 + 2 = k^2+ 7k + 12 = (K+3)*(k+4)
(k étant l'ancienne valeur !)