Ecrire un Algorithme qui Déterminer Le ppcm de deux nombres entiers naturels (non nuls) a et b revient tout simplement à déterminer leur plus petit multiple commun non nul.
Nb : En mathématiques, et plus précisément en arithmétique, le plus petit commun multiple – en abrégé PPCM – (peut s'appeler aussi PPMC, soit « plus petit multiple commun ») de deux entiers non nuls a et b est le plus petit entier strictement positif qui soit multiple de ces deux nombres.
Exemple : PPCM(27,63)=3×3×3×7=189
Proofs
1. Par résolution :
Nouvelle base de connaissance :
\[ \neg(\exists x, R(x) \land \lnot S(x)) \]
Nous devons négativement universellement quantifier et distribuer :
\[ \forall x, \neg(R(x) \land \lnot S(x)) \]
Appliquons les règles de résolution :
\[ \forall x, \neg P(x) \lor \exists y, Q(x, y) \]
\[ \neg P(x) \lor Q(x, y) \lor R(y) \]
\[ \neg R(y) \lor \neg S(y) \lor \neg P(x) \lor \neg Q(y, x) \]
\[ \neg S(x) \lor R(x) \]
\[ P(x) \]
En résolvant ces clauses, on obtient la clause vide (\(\bot\)), ce qui signifie que la négation de la conclusion est insatisfaisante, et donc la conclusion \(\exists x, R(x) \land \lnot S(x)\) est prouvée.
2. Par chaînage avant :
On commence par instancier les quantificateurs existentiels dans la base de connaissance et utiliser les clauses pour déduire de nouvelles clauses jusqu'à atteindre la conclusion.
- À partir de la clause 5 : \( P(c) \) (où \(c\) est une constante)
- À partir de la clause 1 (avec \(c\)) : \( \exists y, Q(c, y) \)
- À partir de la clause 2 (avec \(c\) et une nouvelle constante \(d\)) : \( R(d) \)
- À partir de la clause 4 (avec \(c\)) : \( R(c) \)
À ce stade, nous avons \(R(d)\) et \(R(c)\), nous pouvons donc conclure \(R(c) \land \lnot S(c)\), et par conséquent, la conclusion est prouvée.
3. Par chaînage arrière :
On commence par instancier la conclusion et essayer de remonter la chaîne pour satisfaire les prémisses.
- \( \exists x, R(x) \land \lnot S(x) \)
- \( R(a) \land \lnot S(a) \) (où \(a\) est une nouvelle constante)
On remonte ensuite la chaîne :
- À partir de la clause 4 : \( \lnot S(a) \lor R(a) \)
- À partir de la clause 3 (avec \(a\) et une nouvelle constante \(b\)) : \( \lnot R(b) \lor \lnot S(b) \lor \lnot P(a) \lor Q(b, a) \)
- À partir de la clause 2 (avec \(a\) et \(b\)) : \( \lnot P(a) \lor Q(b, a) \lor R(b) \)
- À partir de la clause 1 (avec \(a\) et une nouvelle constante \(c\)) : \( \lnot P(a) \lor Q(c, a) \)
On peut maintenant utiliser la clause \( \lnot P(a) \lor Q(c, a) \) avec la clause \( P(a) \) pour obtenir \( Q(c, a) \), et utiliser cela avec \( \lnot S(b) \lor \lnot P(a) \lor Q(b, a) \) pour obtenir \( \lnot S(b) \). Enfin, cela peut être utilisé avec \( \lnot S(a) \lor R(a) \) pour obtenir \( \bot \), prouvant ainsi la conclusion.
Voir le corrigéMasquer le corrigé
Correction:
Algorithme PPCM ;
var a , b ,c ,d : entier ;
Debut
Ecrire (" entrez vos deux nombres ");
repeter
lire ( a,b ) ;
jusqu'a ( a > 0 et b > 0 ) ;
c<- a ;
d <- b ;
tant que a < > b faire
si a > b alors
b <- b+d
sinon
a <- a+c ;
fsi
fin tant que
Ecrire (" le PPCM est de " , c , " et " , d , "est : " , a ) ;
Fin.
Questions / Réponses
Aucune question. Soyez le premier à poser une question.
★★★★★
9 votes. Moyenne 4.4 sur 5.
Commentaires
1
scott
Le 07/11/2023
Ça c est quoi ça c est trop compliqué bros
2
Ly
Le 27/01/2023
Et je viens de remarquer qu’il ya des valeurs avec lesquels ton programme génère une boucle infinie
3
Ly
Le 27/01/2023
Fall ton code là ne marche pas dans tous les cas deh
4
Djiomo Arold
Le 13/12/2020
Merci beaucoup
joel_ykLe 31/12/2020
Bonjour / Bonsoir Arold et Merci Pour votre soutien !
Et je viens de remarquer qu’il ya des valeurs avec lesquels ton programme génère une boucle infinie
