| Nyelv : |
|
| Enciklopédia közösség |Enciklopédia válaszok |Küldje el kérdését |Szókincs |Feltöltés ismeretek |
Euklideszi |
 |
|
Euklideszi algoritmus, más néven euklideszi algoritmus (euklideszi algoritmus) az összege két pozitív egész számok legnagyobb közös osztója algoritmus. Ez a legrégebbi ismert algoritmusok, amely vezethető vissza, hogy 3000 évvel ezelőtt. Rövid bevezetés Animáció az euklideszi A matematika, euklideszi algoritmus, vagy más néven az euklideszi algoritmus, a közös nevező az algoritmus. Euklideszi először Eukleidész "Elements" (Volume VII, Proposition y Ⅰ és Ⅱ), míg Kínában vezethető vissza, hogy a keleti Han-dinasztia megjelenése "Kilenc fejezetek Aritmetikai."A legnagyobb közös osztó két egész szám osztható egyszerre a legnagyobb pozitív egész szám. Euklideszi algoritmus alapján a következő elv: a legnagyobb közös osztó két egész szám megegyezik a kisebb a két szám hányadosa, és a maradék a legnagyobb közös osztó. Például a legnagyobb közös osztója a 252 és 105. 21 (252 = 21 × 12; 105 = 21 × 5); mint 252/105 = 2 több, mint 42, 105, illetve 42, úgy, hogy a legnagyobb közös osztó 21. Ebben a folyamatban, számos keskeny, így továbbra is végezze el ugyanezt a számítást zsugorodó, amíg az egyik a két szám lesz nulla. Ebben az időben, a többi nem váltak nulla szám a legnagyobb közös osztója a két szám. Az euklideszi algoritmus is indult, a legnagyobb közös osztó két számot lehet adni egy egész számú többszöröse két szám képviseletében a 21 = 5 x 105 (-2) x 252. Ez a fontos egyenletet nevezzük Bézout egyenlet. Euklideszi geometria euklideszi először a közegben (kb. ie 300), így még mindig használatban van az algoritmus először. Ez az algoritmus eredetileg csak foglalkozni természetes számok, de a 19. században, az euklideszi algoritmus ki kell terjeszteni más típusú számok, mint például a Gauss-egészek és egy jüan polinom. Azóta modern absztrakt algebra fogalmakat, mint például a teljes euklideszi gyűrű kezdtek megjelenni. Később, az euklideszi algoritmus terjeszteni más területekre a matematika, mint a csomó elmélet és többváltozós polinomok. Euklideszi algoritmus sok alkalmazás, akkor is lehet használni, hogy létrehozni a különböző kultúrák a világ hagyományos zenei ritmus. A modern kriptográfia, amely az RSA algoritmus (egy széles körben használt elektronikus kereskedelem nyilvános kulcsú titkosítási algoritmus) egy fontos része. Azt is használják, hogy megoldja egyenletek Diophantine, kérve, hogy megfeleljen a kínai maradéktétel számát, vagy megtalálja az inverz véges mező. Euklideszi algoritmust is fel lehet használni a konstrukció még a pontszámot Sturm tételek és néhány integer faktorizációs algoritmust is alkalmazzák. Euklideszi modern számelmélet alapvető eszköze. Euklideszi algoritmus nagyon hatékony feldolgozása során nagy számban van szükség, mert a kevesebb lépést nem haladja meg a számjegyek száma (a tizedes) öt alkalommal. Gabriel Lame (Gabriel béna), 1844-ben bizonyult ebben a kérdésben, ami a számítási komplexitás elmélet. Bizonyíték Egyszerű ötletek Hagyja, hogy a két szám a, b (a> b), megtalálja a legnagyobb közös osztó a és b (a, b) az alábbi lépéseket: a b, csak egy, van egy ÷ b = q ...... r1 (0 ≤ r1). Amennyiben R1 = 0, akkor (a, b) = b, ha R1 ≠ 0, majd az adagolást, majd r1 b, már b ÷ r1 r2 = q ...... (0 ≤ r2). Ha r2 = 0, akkor (a, b) = r1, r2, ha ≠ 0, akkor továbbra is használhatja, kivéve R1 r2, ...... és így tovább, amíg megosztja eddig. Az utolsó nemnulla osztó (a, b). Alapelv Hagyja, hogy a két szám a, b (b <a), a GCD (a, b), hogy az a, b, a legnagyobb közös osztója, r = egy mod b jelentése után fennmaradó osztódó B, K egy osztva b. szolgáltatók, azaz a ÷ b = k ....... r. Euklideszi algoritmus, amely annak bizonyítása, hogy lnko (a, b) = lnko (b, r). Lépés: Legyen c = lnko (a, b), akkor legyen a = mc, b = nc 2. lépés: szerint előfeltétele mutat r = a-kb = mc-KNC = (m-kn) c A harmadik lépés: Az eredmények szerint a második lépésben azt mutatja, hogy a C faktor egy r Negyedik lépés: azt mondhatjuk, hogy m-kn relatív prím n [Ha nem, akkor létre m-kn = xd, n = m, (d> 1), akkor m = kn xd = KYD xd = (ky x) d, akkor a = mc = (ky x) dc, b = nc = YCD, a legnagyobb közös osztó a és b egy CD-t, hanem a C, ellentétben az előző következtetések] Így látható, hogy lnko (b, r) = c, akkor lnko (a, b) = lnko (b, r). QED. Algoritmus Természetes nyelvű leírás Output b Euklideszi algoritmus határozza meg a természet a használata a következő két pozitív egész szám a és b, a legnagyobb közös faktor: 1, ha r a maradék egy ÷ b, akkor lnko (a, b) = lnko (b, r) 2.. A és ennek többszörösei a legnagyobb közös osztó a. Egy másik megfogalmazás: 1. Egy ÷ b, úgy, hogy a fennmaradó R kapjuk (0 ≤ r <b) Ha r = 0, az algoritmus véget ér, b a válasz. 2 cserélhető: Állítsa be a ← b, b ← r, és visszatér az első lépés |
| Használó Felülvizsgálati |
|
Nincs még hozzászólás |
