un peu d'affichage!!

manianis.
Est-ce que tu peux en déduire une formule mathématique qui calcule le nombre de comparaison en fonction de n? C'est pour le plaisir d'inventer des formules

Oui je l'ai dèja fait jette un coup d'oeil ci-dessus. Page précédente

manianis a écrit:pour n = 5 :it = 69
pour n=6 : it = 100
pour n=7 : it = 137
pour n=100 : it= 29804
pour n=1000 : it= 2998004 (9 secondes sur P4 3GHz)

pour n=10000 : it = 299980004

formule : it = (3*N-2)*N+4

Je vais vérifier la formule. Surtout, donner expliquer comment tu l'as trouvée.
C'était prévisible qu'il soit trop peu optimisé le mien, je l'ai dit depuis le début.
Parcequ'en fait, le losange est inscrit dans un tableau de taille 2N(2N-1). C'est la complexité maximale du problème.

Mnt je vais essayer dévaluer la complexité du 1er programme (ma 1ère version) ... je crois qu'elle est plus optimisée. parce qu'elle construit chaque partie à part.

manianis a écrit:pour n = 5 :it = 69
pour n=6 : it = 100
pour n=7 : it = 137
pour n=100 : it= 29804
pour n=1000 : it= 2998004 (9 secondes sur P4 3GHz)

pour n=10000 : it = 299980004

formule : it = (3*N-2)*N+4

Tu peux m'expliquer comment tu as raisonné pour trouver la formule:



J'ai pas trouvé cette formule quand j'ai refait les calculs, sachant que je ne compte que les instructions IF (condition) THEN... et j'ignore le contenu de (condition) ....

Lorsque N=1, ta formule donne it = (3*1-2)*1 + 4 = 5 comparaisons, alors, que l'algorithme ne fait que 3 comparaisons:

(1): pour j de 1 à 1 (une seule instruction)
(2): pour i de 1 à 2 (deux instructions)

Total = 3 instructions.

La formule que j'ai trouvée est:

salut;
desolé j'ai pas assez de temps mais ya3tikom essa7a c'est bien traiter le sujet.
rdv pour d'autres exo.


amicalement
a+

La formule je l'ai trouvée à partir du tableau de valeurs que j'ai construit :

n = 5 ==> it = 69

n = 6 ==> it = 100
n = ... ==> it = ...

elle est vraie pour n > 1.


je crois que j'ai fait une erreur ou bien c'est toi qui a fait une erreur dans ce qui suit.

Admin a écrit:
(1): pour j de 1 à 1 (une seule instruction)
(2): pour i de 1 à 2 (deux instructions)
Total = 3 instructions.

car à mon avis :
Pour i de 1 à m faire
Pour j de 1 à n faire
// ce code est exécuté n * m fois
// avec m = 1 et n = 2 il est exécuté 2 fois et non 3 fois
Fin Pour
Fin Pour

Code:

for j:=1 to 2*n-1 do
begin
        if (a > n) then a := 0 else a := a  1;
        for i:=1 to n + a do
        begin
            if
                (j < n) and (i > n) or
                (j = n) or
                (j > n) and (i > j mod n)
                then Write('*') else Write(' ');
        end;
end;


Pour n=1. 2n-1=1.
Donc la comparaison ci-dessous est exécutée une seule fois:
if (a > n) then a := 0 else a := a + 1;

La valeur de a est 1. Donc n+a=2.

La boucle (for i:=1 to n + a do) exécute la comparaison ci-dessou 2 fois.
if
(j < n) and (i > n) or
(j = n) or
(j > n) and (i > j mod n)
then Write('*') else Write(' ');

Ce qui fait un total de 3 comparaisons obtenues après 2 itérations.
Je crois que tu as compté les comparaisons comme les itérations.

Vérifie et mets-moi au courant... à propos comment tu as obtenu la formule? un raisonnement mathématique ou bien c'est généré automatiquement par MAPLE?

Admin a écrit:...
Ce qui fait un total de 3 comparaisons obtenues après 2 itérations.
Je crois que tu as compté les comparaisons comme les itérations.

Oui, c'est exact le programme fait 3 comparaisons et 2 itérations.
Non, Je n'ai pas compté les comparaisons j'ai compté les itérations car elles sont plus importantes que les comparaisons et c'est elles qui pénalisent le temps d'exécution des programmes.

Admin a écrit:
Vérifie et mets-moi au courant... à propos comment tu as obtenu la formule? un raisonnement mathématique ou bien c'est généré automatiquement par MAPLE?

Je n'ai que quelques notions vagues à propos de Maple. J'ai utilisé une calculatrice pour trouver la formule.

Pour les comparaisons mon progrmme fait :
comp = 3 ; n = 1
comp = 15 ; n = 2
comp = 30 ; n = 3
comp = 51 ; n = 4
comp = 78 ; n = 5
comp = 111 ; n = 6
comp = 150 ; n = 7
comp = 195 ; n = 8
comp = 246 ; n = 9
comp = 303 ; n = 10
comp = 30003 ; n = 100
comp = 3000003 ; n = 1000
comp = 300000003 ; n = 10000

pour n > 1 : comp = 3*N*N+3 = 3*(N² + 1)

manianis: dans la théorie de complexité, on s'intéresse aux opérations atomiques: arithmétiques + comparaisons... Les comparaisons sont importantes. Les boucles sont aussi basées sur des comparaisons. Pour vérifier, essaie d'écrire une boucle en Assembleur (JE:Jump If Equal, JNE: Jump If Not Equal,...). Donc, si tu veux qu'on soit trop minitieux, il faut compter tout ça. Mais, on s'est simplifié la vie en supposant qu'on va calculer juste le nombre de fois où l'instruction IF...THEN a été invoquée.

Je ne suis pas encore d'accord sur la formule et les résultats données par ton programme de calcul de complexité... Je vais essayer de te convaincre plutard.

A mon avis, il ne faut pas généraliser des formules mathématiques en partant uniquement de quelques exemples. Même si ça coincide dans 10000 exemples, on ne peut pas affirmer à tout le monde que la formule est correcte.

La formule que je t'ai proposée: C(n)=(5n²+3n-2)/2 pourrait être fausse, mais, je l'ai faite après un raisonnement mathématique (des calculs de suites...).

Si tu veux, je poste la démo de la formule.
@+

Oui je veux savoir comment tu as trouvé cette formule.

C'est promis. Dès que je trouve un peu de temps, je te poste la réponse. Je dois la copier du papier vers le forum.

je suis curieux de voir la démo?!

manianis a écrit:Je ferais comme même un petit essai :

Code:


program losange;
var i, j, a, n : integer;
begin
    Writeln('Entrer n : '); Readln(n);
    a := 0;
    for j:=1 to 2*n-1 do begin
        if (a > n) then a := 0 else a := a + 1;
        for i:=1 to n + a do begin
            if
                (j < n) and (i > n) or
                (j = n) or
                (j > n) and (i > j mod n)
                then Write('*') else Write(' ');
        end;
        Writeln;
    end;
    Readln;
end.

C(n) = le nombre de comparaisons effectuées par cet algorithme.

On a:

C(n) = (2n-1) + Somme(k x P(k), k=1..2n-1)

où P(k): nombre de comparaisons dans la boucle "for i:=1 to n + a do begin", en fait c'est évident que "a" dépend de k.

P(k) = n + a(k) , avec a(k) défini par: a(k)=k, si k=1..n et a(k)=0 si k>n.
Soit,
P(k) = n+k, pour k=1..n
P(k) = n, pour k=n+1..2n-1
Donc:

C(n) = (2n-1) + Somme(k x P(k), k=1..2n-1)
= (2n-1) + [P(1)+P(2)+...+P(n)] + [P(0)+...+P(0)]
= (2n-1) + [(n+1)+(n+2)+...+(n+n)] + [(n + n + ... n)]

Somme d'une suite arithmétique
(n+1)+(n+2)+...+(n+n) = n² + n(n+1)/2 = (3n²+n)/2.

(n + n + ... n) répété (2n-1)-(n+1) + 1 fois, çàd, n-1 fois.
(n + n + ... n) = n(n-1)


Récapitulons:
C(n) = (2n-1) + (3n²+n)/2 + n(n-1)

Si le calcul est bon, on aura:
C(n) = (5n²+3n-2)/2