Algorithme (PPCM)

Fil fermé
 
Partager Rechercher
Simple tu utilise la propriété PGCD(a,b)*PPCM(a,b)=a*b
Donc un bête algorithme d'Euclide :

Code:
VAR a,b,r,prod : entier
SAISIR a
SAISIR b
prod<=a*b
r<= a-INT(a/b)*b

TANT QUE r!=0
	a<=b
	b<=r
	r<=a-INT(a/b)*b
FIN TANT QUE

AFFICHER "PGCD(a,b)=" b
AFFICHER "PPCM(a,b)=" prod/r
Lien direct vers le message - Vieux 05/12/2004, 02h59
Citation :
Publié par L@ng3
Le truc c'est qu'on demande de ne pas utiliser le PGCM pour faire le PPCM, désolé de ne pas avoir précisé
Tu as le droit d'utiliser l'algorithme de décomposition des nombres en produit de facteurs premiers ?
Lien direct vers le message - Vieux 05/12/2004, 12h01
j'en ai bien un piti log à te proposer en C :

Code:
int main(void)
{


   /* Ce logiciel calcul le plus petit commun multiple entre 2 chiffres POSITIFS\n  */

    /* unsigned long pour éviter les débordements mémoire */
   unsigned long Chiffre1   = 0;
   unsigned long Chiffre2   = 0;
   unsigned long Diviseur   = 0;
   unsigned long Borne_Max  = 0;

       /* on va capter les chiffres sous forme de chaine de caractères pour éviter */
      /* les problèmes qui se posent parfois avec le scanf et la saisie de 0            */
      /* il les comprend parfois comme un return */

    char   chiffre1_txt[50] = "";
    char   chiffre1_txt[50] = "";
    char * signe_moins_ptr1 = NULL; 
    char * signe_moins_ptr2 = NULL; 

        /* saisie des chiffres à l'execution */
       printf("Quel est le premier chiffre (>=0 )? \n");
       scanf("%s",chiffre1_txt);    
       printf("Quel est le second chiffre (>=0)? \n");
       scanf("%s",chiffre2-txt);

       /* les caractères sont saisis, on vérifie que les chiffres sont bien >0 */
       /* etape 1) recherche de signe "-" */
       signe_moins_ptr1 = strstr(chiffre1_txt,"-");
       signe_moins_ptr2 = strstr(chiffre2_txt,"-");
  
       if ((signe_moins_ptr1== NULL)  && (signe_moins_ptr2 ==NULL))
       {
           /* ce sont bien des chiffres >0 */
           /* on peut les "ranger" dans les variables unsigned long prévues */
          Chiffre1= atoi( chiffre1_txt);
          Chiffre2= atoi( chiffre2_txt);
       }
       else
       {
           /* au moins un des chiffres est négatif */
           printf("Calcul impossible, au moins un des chiffres est négatif \n");
           printf("SORTIE DU PROGRAMME\n");
           return -1;
       }

      /* début des calculs */
      /* => recherche de la borne max de la boucle de calcul */
     if ( Chiffre1 > Chiffre2)
     {
         Borne_Max = Chiffre2;
     }
     else
     {
         Borne_Max = Chiffre1;
     }
    
     /* recherche du PPCM */
     /* la boucle commence à 2 car 1 est toujours un PPCM evident :p */
     for (Diviseur =2; Diviseur <= Borne_Max ; Diviseur ++)
     {
          unsigned long Reste1 ;
          unsigned long Reste2 ;

          Reste1 = Chiffre1 % Diviseur;
          Reste2 = Chiffre2 % Diviseur;
 
           If ((Reste1 ==0) && (Reste2 == 0))
           {
                /* on a trouvé le PPCM */
                printf("le PPCM est : %i \n",Diviseur);
                printf("SORTIE DU PROGRAMME\n");
                return Diviseur;
           }
    }

     printf("Il n'y a pas de PPCM pour les chiffres que vous avez saisi \n");
     printf("SORTIE DU PROGRAMME\n");
     return 0;
}

la partie vérification des signes n'est absolument pas obligatoire mais elle est instructive...
TOUJOURS SE MEFIER DE SCANF!!!

si tu veux calculer avec des chiffres positifs et negatifs tu n'utilises pas "unsigned" dans les déclarations des variables ( par contre ta plage d'étude divisée par 2 )

tu veux le même en assembleur 68020?
Lien direct vers le message - Vieux 05/12/2004, 12h41
Citation :
Publié par L@ng3
Vous avez po plus simple ?
Celui de mys est le plus simple si tu le réécris :

Entrer les nombres a et b
1->p
Tant que non(a divise p) ou non (b divise p) faire
p+1->p
Fin tant que
Afficher p
Lien direct vers le message - Vieux 05/12/2004, 17h19
tiens le même algo avec un while en C:
Code:
#define VRAI  1
#define FAUX  0

int main(void)
{
   short Continuer;

   ....

   Diviseur   = 2;
   Continuer = VRAI;
   While (Continuer == VRAI)
   {
          unsigned long Reste1 ;
          unsigned long Reste2 ;

           Reste1 = Chiffre1 % Diviseur;
           Reste2 = Chiffre2 % Diviseur;
 
          If ((Reste1 ==0) && (Reste2 == 0))
          {
                /* on a trouvé le PPCM */
                printf("le PPCM est : %i \n",Diviseur);
                Continuer = FAUX;
           }
           else
           {
                 Diviseur ++;
                 if (Diviseur == Borne_Max)
                 {
                     printf("Il n'y a pas de PPCM pour les chiffres que vous avez saisi \n");
                     Continuer = FAUX;
                 }
           }
    }
    printf("SORTIE DU PROGRAMME\n");
    return 0;
}
ca te va ou tu veux autre chose ?
Lien direct vers le message - Vieux 05/12/2004, 20h04
Est ce que ça c'est bon ?

Variable:
int nombre1, nombre2, produit, reste, ppcm => Entier

ecrire ("Calcule du PPCM de deux nombres.");
ecrire ("Entrer votre premier nombre:");
lire ("%d", &nombre1);
ecrire ("Entrer votre deuxieme nombre:");
lire ("%d", &nombre2);
produit=nombre1*nombre2;
reste=a%b;

While (reste!=0) {
a=b;
b=reste;
reste=a%b;
}
ppcm=produit/b;
ecrire ("ppcm=%d", ppcm);


Voilà, est ce que c'est bon , et si oui pouvez mexpliquer brièvement les qqs lignes à partir de produit=nombre1*nombre2 ?

Merci
Lien direct vers le message - Vieux 05/12/2004, 20h33
Hmm hmm c'est exactement ce que j'ai fait.
C'est un bête algorithme d'Euclide

Sinon le programme C de Mys mais en "pseudolangage" Algorithme

Code:
VAR Chiffre1,Chiffre2,Diviseur,Borne_Max : entier
    Reste1,Reste2 : entier

SI Chiffre1 > Chiffre2
   ALORS
      Borne_Max = Chiffre2;
   SINON
      Borne_Max = Chiffre1;
FSI

POUR Diviseur DE 2 A Borne_Max
   Reste1 <= Chiffre1 % Diviseur;
   Reste2 <= Chiffre2 % Diviseur;
 
   SI (Reste1=0) ET (Reste2=0) 
      ALORS 
      AFFICHER "le PPCM est : " + Diviseur
      RETOURNET Diviseur
   FSI
FPOUR

AFFICHER "Il n'y a pas de PPCM pour les chiffres que vous avez saisi"
C'est plus long que faire par le PGCD, on cherche juste a trouver le premier nombre qui divise les deux Chiffre.
Lien direct vers le message - Vieux 05/12/2004, 22h19
Citation :
Publié par L@ng3
Voilà, est ce que c'est bon , et si oui pouvez mexpliquer brièvement les qqs lignes à partir de produit=nombre1*nombre2 ?

Merci
Dans ton algorithme, tu calcules le pgcd et tu divises le produit par le pgcd pour avoir le ppcm alors que tu as dit que tu ne devais pas calculer le pgcd.
Lien direct vers le message - Vieux 05/12/2004, 22h40
sinon un truc tout bête :

Citation :
entrer a et b
x:=1

tant que la partie entière de x/a est différente de x/a ou que la partie entière de x/b est différente de x/b, faire x:=x+1
(fin de la boucle "tant que")

afficher x
(j'y connais rien ou presque en informatique, ce qui explique pourquoi je fais des phrases au lieu d'utiliser des commandes, vu que je ne les connais pas)

En gros cette méthode prends une variable x, et teste si x est un multiple commun à a et b. on part de x=1 et tant que c pas bon, on teste avec la valeur suivante


C'est sur que c'est peut-être pas ce qu'il y a de plus optimisé, mais au moins ça me semble simple (du moins plus simple que les codes cités plus haut auxquels je ne comprends rien )

Edit : ah si y a celui de Turanar tout au debut qui est simple aussi, et surtout qui est tres bien, mieux que le mien en tout cas^_^
Sinon tu dit qu'il faut pas utiliser le pgcd, ben il l'utilise pas, il l'affiche juste à la fin Si ça te derange efface juste la ligne en question (l'avant derniere), ça marche aussi
Lien direct vers le message - Vieux 05/12/2004, 23h16
Citation :
Publié par Turanar
Simple tu utilise la propriété PGCD(a,b)*PPCM(a,b)=a*b
Donc un bête algorithme d'Euclide :

Code:
VAR a,b,r,prod : entier
SAISIR a
SAISIR b
prod<=a*b
r<= a-INT(a/b)*b

TANT QUE r!=0
	a<=b
	b<=r
	r<=a-INT(a/b)*b
FIN TANT QUE

AFFICHER "PGCD(a,b)=" b
AFFICHER "PPCM(a,b)=" prod/r
Superbe division par 0 !
Lien direct vers le message - Vieux 10/06/2013, 23h10
a b
x=2
while true
si mod( a,x)=mod(b,x) =0 then
ppcm=x
stop
x=x+1
wend

super con mais ca marche sauf si c est 1
Dernière modification par cricri ; 11/06/2013 à 20h01.
Lien direct vers le message - Vieux 11/06/2013, 19h55
Fil fermé

Connectés sur ce fil

 
1 connecté (0 membre et 1 invité) Afficher la liste détaillée des connectés
Thème visuel : Fuseau horaire GMT +1. Il est actuellement 20h05.
^^ Haut de page ^^