Second concours de programmation

[lord.osiris]

Coucou les gens! Désolé j'ai pas des masses de temps, alors je poste ici vite fait un deuxième concours.
Je vais juste ajouter quelque chose : pourriez-vous commenter votre code pour que les néophytes puissent comprendre? Le but n'est pas ici de faire des posts élitistes, mais des posts CONSTRUCTIFS pour tous. Donc un peu comme j'ai fait sur l'autre topic. En clair, lorsque vous donnez la solution, donnez un bloc "code" contenant le tout d'un coup, puis donnez les explications comme mon autre post.
Désolé si je suis pas clair, mais hier je me suis pas couché super tôt... Et ce soir il est... Ben oui, 01:01...

Donc voici le "concours" : Essayez d'écrire une procédure qui prend en entrée deux entiers naturels, et qui applique étape par étape (donc retourne chacune des lignes) l'algorithme d'Euclide. Pour ceux qui s'en rappellent pas, .... Honte à vous! Enfin, google est votre ami.

Je veux donc en entrée de procédure 2 entiers naturels (on est sympas), et en sortie les lignes de l'algorithme, de la forme : a= b*c + r.


Question subsidiaire : Donner le temps que met maple (dans le cas où l'on utilise maple) pour appliquer l'algorithme jusqu'à la dernière ligne.


Je rappelle que tout le monde peut participer, en donnant une idée genre "je pense qu'il faudra créer une variable interne afin de stocker telle information" ou autre... Personne n'est stupide, tout le monde commence. Et vous avez déjà un exemple à côté.

[!ce#M@n]

Euh, c'est quoi l'algorithme d'Euclide??

[lord.osiris]

Gasp!

Allez, hop, je te le rappelle (juste pour info, l'idée de ce concours ci vient de mon frere qui est en seconde maintenant...)

http://fr.wikipedia.org/wiki/Algorithme_d'Euclide


Et interdit de me recopier les codes de wikipedia, ça ne nous apprendrait RIEN. Donc obligation d'utiliser maple cette fois ci.

[walko]

Bon, ben moi j'aime pas Maple, alors je l'ai fait en C ...

c'est tout simple à comprendre, faut juste faire attention au fait que :

a=a+9; signifie affecte à a, la valeur a +9, du coup premier=deuxieme ne signifie pas que premier est égal à deuxieme, le = sert à affecter, sinon on met == , pour le = classique.

PS: c'est moche ce code en vert.... faudrait changer ça.
PPS: ça a été fait sous linux, du coup le gcc sert à compiler, et le a.out c'est le produit de la compilation, ~a.exe sous DOS
PPPS: tout ce qui est entre /* et */ sont des commentaires, à la fin, c'est juste des exemples d'execution, pour montrer qu'il a l'air de marcher.
PPPPS: Thibaud, t'es nul, tu sais même pas faire un lien correctement...

Code: Tout sélectionner


*--euclide.c--*
@author Walkowiak <walkowia>
Probleme: Appliquer l'algorythme d'euclide à 2 entiers, et afficher chaque étape
*/

#include <stdio>

int main(void) {

  int premier,deuxieme,temp,div;                         /* On déclare les variables que l'on va utiliser */

  printf("Veuillez entrez les deux nombres : \n \n");   /* saisie des deux nombres */
  scanf("%d %d",&premier,&deuxieme);                /* stockage des deux nombres dans les variables */


  if(premier<deuxieme){                              /* Si le premier n'est pas le plus grand */
    temp=premier;                                    /*On échange les valeurs de premier et deuxieme */
    premier=deuxieme;                                /* A l'aide de la variable temp */
    deuxieme=temp;
  }                                                  /* Sinon, on ne fait rien */


if(premier==0,deuxieme==0){                       /* Si l'un des deux est nul */

    printf("ça va pas être facile avec ces deux là... \n");
  }


  else{
                                              /* Sinon, on peut faire l'algorythme */
    temp=1;                                   /* On affecte une valeur par défaut à temp */

  while(temp!=0){                                /* tant que le reste n'est pas nul, on continue */
    temp=premier%deuxieme;                           /* On affecte à temp la valeur du reste de la division euclidienne */
    div=(premier-temp)/deuxieme;                     /* On calcule div */

    printf("%d = %d * %d + %d \n",premier,deuxieme,div,temp);  /* On a bien : premier=deuxieme*div+temp */

    premier=deuxieme;                                          /* On affecte la valeur de deuxieme dans premier */
    deuxieme=temp;                                             /* Puis celle de temp dans deuxieme */
  }                                                            /* Et on réaplique le while si temp n'est pas nul */   
  printf("\n");                                                /* ça c'est juste pour passer une ligne */
  }                                                            /* C'est plus jolie ;) */





return 0;

}

/*
Exemples d'execution:

walkowia@dual22:~/C/Tests$ gcc euclide.c
walkowia@dual22:~/C/Tests$ a.out
Veuillez entrez les deux nombres :

44
333
333 = 44 * 7 + 25
44 = 25 * 1 + 19
25 = 19 * 1 + 6
19 = 6 * 3 + 1
6 = 1 * 6 + 0

walkowia@dual22:~/C/Tests$ a.out
Veuillez entrez les deux nombres :

45
12
45 = 12 * 3 + 9
12 = 9 * 1 + 3
9 = 3 * 3 + 0

walkowia@dual22:~/C/Tests$
walkowia@dual22:~/C/Tests$ a.out
Veuillez entrez les deux nombres :

888
0
ça va pas être facile avec ces deux là...
walkowia@dual22:~/C/Tests$ a.out
Veuillez entrez les deux nombres :

0
222
ça va pas être facile avec ces deux là...
walkowia@dual22:~/C/Tests$ a.out
Veuillez entrez les deux nombres :

222
56
222 = 56 * 3 + 54
56 = 54 * 1 + 2
54 = 2 * 27 + 0



*/



[erd]

OK.

Étant donnés deux entiers [tex]0\leq v\leq u[/tex]. Fixons [tex]u.[/tex] Qui peut me dire de manière heuristique (c'est-à-dire, en se basant sur des exemples numériques) quel est l'ordre de grandeur du nombre de pas de cet algorithme en fonction de u (tester pour différents v possible et regardez la moyenne du nombre de pas, par exemple...comparez alors cette moyenne à [tex]u.[/tex]..) ?

[walko]

Buh ?????


----> A pas compris la question.....

[Xklr_65]

Bon j'ai enfin pu rédiger ma procédure en MAPLE cette procédure répond à la première question, qui était de donner le pgcd de deux nombres par l'algorithme d'Euclide en écrivant chaque ligne de calcul.
Voici le code:

Code: Tout sélectionner

pgcd:=proc(a,b)
local q,r;
if a<b then pgcd(b,a);
else q:=iquo(a,b,'r');
printf("%g = %g * %g + %g\n",a,q,b,r);
if r=0 then RETURN(q);
else pgcd(b,r);
fi;fi;end;


Penchons nous à présent sur les particularités de cette procédure. C'est une procédure qui s'auto appelle. Je m'explique:

Code: Tout sélectionner

pgcd:=proc(a,b)
local q,r;

Normal jusqu'ici...

Code: Tout sélectionner

if a<b then pgcd(b,a)

Ici on ne peut effectuer une division euclidienne de 4 par 26, donc on va réappliquer la procédure aux entiers inversés.

Code: Tout sélectionner

else q:=iquo(a,b,'r');

MAPLE affecte à q la valeur du quotient de la division euclidienne et à r le reste.

On pourrait néanmoins utiliser:

Code: Tout sélectionner

q:=iquo(a,b);
r:=irem(a,b);

Ces deux opérations étant équivalentes.

Code: Tout sélectionner

printf("%g = %g * %g + %g\n",a,q,b,r);

Voici la ligne qui permet de nous retourner la ligne de calcul.
L'assertion entre " " est ce qui va être affiché à l'écran. Les %g seront substitués par leus valeurs respectives a,q,b et r. Enfin le \n indique à MAPLE qu'il faudra changer de ligne après ceci. Sinon, tous les calculs seront sur une même ligne.

Code: Tout sélectionner

if r=0 then RETURN(q);

Si le reste est nul, alors le quotient est le pgcd recherché.

Code: Tout sélectionner

else pgcd(b,r);

Sinon on réapplique la procédure à b et r (d'après l'algorithme d'Euclide)

Code: Tout sélectionner

fi;fi;end;

Je ferme toutes mes boucles if et conclus ma procédure.

Suite de la questions sur le post suivant.

[Xklr_65]

Ici on va s'intéresser à la partie nombre d'opérations effectuées. Je reprends ma procédure et la "bidouille" un peu...

Code: Tout sélectionner

pgcd:=proc(a,b,n)
local q,r;
if a<b then pgcd(b,a,n);
else q:=iquo(a,b,'r');
if r=0 then RETURN(n);
else pgcd(b,r,n+1);
fi;fi;end;


Ici le printf a disparu, je n'ai en effet plus besoin d'afficher les calculs vu que je ne m'intéresse qu'au nombre de calculs (on considère qu'une division euclidienne constitue un calcul)
J'ai rajouté un compteur n, qui s'incrémente à chaque fois que la procédure s'auto appelle après avoir effectué une division euclidienne.
Pour effectuer un calcul je dois donc taper:

Code: Tout sélectionner

pgcd(a,b,0);

Je dois en effet initier le compteur mais pas à l'intérieur de la procédure, étant donné qu'elle s'auto appelle, si je fixais la valeur de n à 0 à l'intérieur de la procédure, le compteur de réinitialiserait à chaque fois. C'est assez embêtant...

Pour répondre à la question on peut faire une procédure de ce style:

Code: Tout sélectionner

nbmoy:=proc(n)
local A, res;
A:=[seq(pgcd(i,5000,0), i=1..5000)]
res:=((sum(A[i],i=1..nops(A))/nops(A)))
RETURN(res);
end;

Explication:

Code: Tout sélectionner

A:=[seq(pgcd(i,5000,0), i=1..5000)]

MAPLE me fait une liste des nombres d'opérations qu'ils effectue pour calculer le pgcd des nombres entre 1 et 5000.

Je fais ensuite la moyenne de ces nombres:

Code: Tout sélectionner

n:=((sum(A[i],i=1..nops(A))/nops(A)));


Je somme les n termes de A et les divise par le nombre de termes.

On obtient donc le nombre moyen d'opérations en fonctions du nombre.

[erd]

OK.

Et alors, quels exemples de résultats obtiens-tu pour [tex]N=10^k, \quad k=3..10[/tex] ?