I-Algorithm ka-Euclid: Umlando, Ukusetshenziswa kanye Nezicelo

Informatec Digital » Ama-algorithms » I-Algorithm ka-Euclid: Umlando, Ukusetshenziswa kanye Nezicelo

I-algorithm ka-Euclid, eyadalwa eminyakeni engaphezu kuka-2000 eyedlule yisazi sezibalo saseGrisi u-Euclid, iyindlela ethakazelisayo newusizo kakhulu esivumela ukuthi sithole i- greatest common divisor (GCD) yama-integer amabili ngempumelelo nangokunengqondo. Naphezu kobudala bayo, isalokhu iyithuluzi elibalulekile ezindaweni ezifana nethiyori yezinombolo, uhlelo , kanye ne-cryptography yesimanje. Isisekelo sayo sezibalo siqinile kangangokuthi sibhekwa njengensika eyisisekelo ekufundweni kwama-algorithms kanye nezibalo.

Kuyo yonke le ndatshana, sizochaza ngokuningiliziwe ukuthi le algorithm isebenza kanjani, izinhlelo zayo ezisebenzayo, nokuthi ungayisebenzisa kanjani kalula ezimweni ezahlukahlukene. Kusukela ekwenzeni kube lula izingxenyana kuya ekusetshenzisweni kwayo ekuphepheni kwedijithali, uzofunda konke okudingeka ukwazi ngale ndlela yezibalo edumile.

Iyini i-algorithm ka-Euclid?

I-algorithm ka-Euclid iyinqubo yezibalo enhloso yayo eyinhloko ukuthola i- greatest common divisor (GCD) yama-integers amabili. Lesi sihlukanisi siyinombolo enkulu kunazo zonke engahlukanisa zombili izinombolo ngaphandle kokushiya okusele. Le ndlela isekelwe esimisweni se-geometric esiqukethe ukususa noma ukuhlukanisa izinombolo kuze kube yilapho kufinyelelwa umphumela ohlangabezana nezimo ze-GCD.

Ngokwesimanje, le algorithm isebenzisa imisebenzi elula njengokususa nokubala okusele ( kusetshenziswa umsebenzi we-modulo) ukuthola imiphumela ngokushesha nangendlela ephumelelayo. Le nqubo ibonakale isebenza kahle kakhulu ngisho nalapho isebenza ngezinombolo ezinkulu kakhulu , iqinisa ukufaneleka kwayo ezibalweni zamanje kanye nesayensi yekhompyutha.

Ukusebenza okuyisisekelo

I-algorithm ka-Euclid iqala ngezinombolo ezimbili, ngokuvamile ezibizwa ngokuthi u-a no- b , lapho u-a ≥ b . Umqondo oyinhloko ukusebenzisa isici sokuthi i-greatest common divisor (GCD) yezinombolo ezimbili ayishintshi uma sishintsha inombolo enkulu ngengxenye esele yokuhlukaniswa kwe-enkulu nge-encane. Inqubo ingafingqwa ngezinyathelo ezilandelayo:

• Hlukanisa a phakathi b futhi ubale okusele r.
• Faka okunye esikhundleni a por b y b por r.
• Phinda inqubo kuze kube yilapho insalela ikhona 0.

Okwamanje okusele kuba yi-zero, inani lokugcina lika- b yi-GCD.

Izibonelo ezisebenzayo ze-algorithm

Ukuze uqonde kangcono le-algorithm, ake sibheke isibonelo esisebenzayo:

Bala i-GCD ka-56 no-12:

1. Sihlukanisa 56 ngo-12: 56 = 12 × 4 + 8.
2. Sifaka esikhundleni: manje a = 12 kanye no-b = 8. Sihlukanisa u-12 ngo-8: 12 = 8 × 1 + 4.
3. Sishintsha futhi: a = 8 futhi b = 4. Sihlukanisa u-8 ngo-4: 8 = 4 × 2 + 0.

Okusele manje kungu-zero, ngakho-ke i-GCD ka-56 no-12 ingu- 4.

Izicelo ze-Euclid's Algorithm

I-algorithm ka-Euclid inenqwaba yezinhlelo zokusebenza ezisukela kwizibalo eziyisisekelo kuye ku-cryptography ethuthukisiwe. Ezinye zezindlela engasetshenziswa ngazo zihlanganisa:

• Ukwenza lula izingxenyana: Thola i-GCD yenani kanye nedinomineyitha yengxenye ukuze ulehlise libe ngendlela yalo elula.
• Ukukhiqiza ukhiye ku-cryptography: Kuma-algorithms afana ne-RSA, i-GCD ibalulekile ekutholeni izinombolo ze-coprime ezidingekayo ukudala okhiye abavikelekile futhi ihlobene ne- Izinombolo eziyinhloko.
• Ukuxazulula izibalo ze-Diophantine: Xazulula izibalo zomugqa ezinezixazululo eziphelele.
• Idizayini yesiyingi yedijithali: Kuyasiza ukuvumelanisa amaza kubunjiniyela be-elekthronikhi.

Ukuqaliswa Kuhlelo

I-algorithm ilula kangangokuthi ingasetshenziswa cishe kunoma yiluphi ulimi lokuhlela ngekhodi encane kakhulu. Nasi isibonelo kuPython:

Inguqulo ephindaphindayo:

def mcd(a, b):
    if b == 0:
        return a
    else:
        return mcd(b, a % b)

Inguqulo ephindaphindayo:

def mcd_iterativo(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Zombili izinguqulo zisebenza kahle kakhulu futhi zikhiqiza umphumela ofanayo.

Ukusebenza kwe-algorithm

I-algorithm ka-Euclid isebenza kahle kakhulu kangangokuthi inobunzima besikhathi buka- O(log(min(a, b))) . Lokhu kusho ukuthi ngisho nasezinombolweni ezinkulu kakhulu, ukubala kungenziwa ngokushesha.

Lokhu kusebenza kahle kuyenza ibaluleke kakhulu emikhakheni lapho isivinini nokunemba kubalulekile khona, njenge-cryptography kanye nokuxazulula izinkinga zezibalo ezithuthukisiwe.

Ukubaluleka Emlandweni Wezibalo

U-Euclid, owaziwa ngokuthi "uyise we-geometry," wafaka le algorithm emsebenzini wakhe i-Elements , enye yezinkomba zezibalo ezibaluleke kakhulu zakudala. Nakuba yaqala njengendlela ye-geometry, ukuvela kwayo kuye kwavumela ukuthi isetshenziswe namuhla ezindaweni zesimanje njengokuthuthukiswa kwe-algorithms yekhompyutha.

Le-algorithm iwubufakazi bokuthi imiqondo yezibalo elula kakhulu ingaba nezinhlelo zokusebenza ezingokoqobo futhi iguqule kanjani yonke imikhakha phakathi namakhulu eminyaka.

I-algorithm ka-Euclid ayilona nje ithuluzi lokubala i-greatest common divisor (GCD); iyisibonelo sobuhle nobuhle bezibalo ezisetshenzisiwe. Kusukela ezinkingeni eziyisisekelo njengokunciphisa izingxenyana kuya ekusetshenzisweni kwayo kwezobuchwepheshe besimanje, le ndlela isalokhu iyingxenye ebalulekile ekufundweni kwama-algorithms kanye nethiyori yezinombolo. Ukuguqula ubulula bube ukusebenza kahle ngokungangabazeki kungenye yezihluthulelo zempumelelo yayo kanye nokufaneleka kwayo okuhlala njalo.