un peu d'affichage!!

Ecrire un programme en Pascal qui parmet d'afficher à l'ecran ce figure: exemple pour n=5 on obtien la forme suivante
https://servimg.com/view/11696810/1



a+

wico a écrit:Ecrire un programme en Pascal qui parmet d'afficher à l'ecran ce figure: exemple pour n=5 on obtien la forme suivante
https://servimg.com/view/11696810/1

a+

Très bon exercice qui fait comprendre le fonctionnement des boucles FOR
(les structures itératives). Je te donnerai une indication demain matin.
N'oublie pas de dire Bonjour, Salut tout le monde, Bonsoir, ...

Salut wico:
Une 1ère version de la solution, que je considère naïve et non très optimisée est la suivante:

Code:

uses wincrt;
var
  i,j,N: integer;

begin

  write('N = ');
  readln(N);

  for i:=1 to N-1 do
  begin
      for j:=1 to N+i do
          if (j>N) then write(' * ') else write('  ');
      writeln;
  end;

  for i:=1 to 2*N do
      write(' * ');
  writeln;

  for i:=1 to N-1 do
  begin
      for j:=1 to 2*N do
          if ((j>i) and (j<=N))  then write(' * ') else write('  ');
      writeln;
  end;

end.

Des commentaires?

Normalement, on peut résoudre tout le problème en deux boucles FOR. Elle devrait être un peu compliquée. Si je trouve le temps, je m'amuserai de te trouver une solution avec uniquement 2 boucles FOR.

Une version plus optimisée (au niveau code source) est prête. Commente d'abord ce que je t'ai proposé.

Bon programme Nabil.

Merci manianis, wico a posé le problème et nous a quitté

voilà une deuxième version plus optimisée:

Code:


uses wincrt;
var
  i,j,N: integer;
  condition: boolean;

begin

  write('N = ');
  readln(N);

  for i:=1 to 2*N-1 do
  begin
        write(i,' : ');
        for j:=1 to 2*N do
        begin
          condition := (i<=N) and (j>N) and (j<=N+i) OR
                        (i>=N) and (j> (i mod N)) and (j<=N);
              if (condition) then
                write(' * ')
              else
                write('  ');
        end;
        writeln;
  end;

end.

Any comments?

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.

Il fonctionne bien ton programme.
Si t'a du temps libre, on peut discuter lequel des programmes est le moins complexe entre terme de Comparaison.

OK?

Comme tu veux. Je suis d'accord.

Je commence par le 2ème code source...

Le nombre de comparaison qu'il fait c'est exactement

J'ai fait une petite rectification ci-dessus pour minimiser le nombre d'itérations

manianis a écrit:J'ai fait une petite rectification ci-dessus pour minimiser le nombre d'itérations

J'ai remarqué...

Lorsque tu trouves du temps, évalue le nombre de comparaisons de ton code source manianis.

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

Votre programme en fait :
pour n=5 : 90
pour n=6 : 132
pour n=7 : 182
...
pour n=100 : 39800
pour n=1000 : it = 3998000 (en 14 secondes)

pour n=10000 : it = 399980000

formule : it = (4n-2)*n

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.
@+