Keresse meg a legnagyobb közös osztó két egész szám, a probléma a pascal, programozás

Megfogalmazás. Mivel két pozitív egész szám. Ahhoz, hogy megtalálja a legnagyobb közös osztó.

Megjegyzés: A legnagyobb közös osztója (GCD write rövidítve) két természetes számot m és n a legnagyobb közös osztó őket. Rendeltetése: GCD (m n.).

2. megjegyzés: közös osztó két egész szám az úgynevezett természetes szám, amellyel a természetes szám, amely osztója mindkét számra.

Például, azt találjuk, hogy GCD (12, 8):

Írjuk le az összes osztója 12: 1, 2, 3, 4, 6, 12;

Írjuk le az összes osztója 8: 1, 2, 4, 8;

Írjunk minden közös osztók 12 és 8: 1, 2, 4. Ezek közül a legnagyobb számban - 4. Ez a legnagyobb közös osztója a 12-es és a 8.

Határozat. Természetesen a döntés nem fogunk írni osztók, és válasszon egyet. Elvileg lehetne megoldani, mint a feladat 15. A ciklust kezdve a legkisebb a két szám (ahogy azt is lehet GCD például, a GCD (12, 4) = 4). De mi használjuk az úgynevezett euklideszi algoritmus megtalálása GCD, amely származik matematikai módszerekkel. A legegyszerűbb esetben, a megadott számok m és n úgy néz ki, mint ez:

1) Eslimneravnon, ugorjon a 2. lépésre, egyébként vyvestimi kivitelben algoritmus;

3) lépés az 1. lépéshez

Amint az a 2. lépésben, a nagyobb a két szám helyettesíti a jelenlegi különbség a nagyobb és a kisebb.

Itt egy példa a számok 12 és 8:

a. Mivel 12> 8, cseréje 1 2 12 - 8 = 4;

b. Mivel 8> 4, cserélni a augusztus 08-04 = 4;

Ne végezzen semmilyen vitát egy olyan algoritmus, és bizonyítani annak helyességét, lefordítani leírását egy intimebb formája Pascal:

Az algoritmus a természetes nyelvben:

2) a Start ciklus m előfeltétele <>n. A ciklus:

1. Ha m> n. majd rendelni a változó m m -n. egyébként rendelni n változó n -m;