Euklidsk algoritme

百度土地承包期再延长30年，时间节点与第二个百年战略构想高度契合，既稳定了农民预期，又为届时进一步完善政策留下了空间。

I talteori er euklidsk algoritme ein algoritme for ? berekne st?rste felles divisor (SFD) til to element i kva for ein som helst euklidsk ring (til d?mes to heiltal). Hovudtydinga til algoritmen er at han ikkje treng faktorisering av dei to heiltala, og at han er ein av dei eldste kjende algoritmane som kan daterast tilbake til Hellas i antikken.

Bakgrunn

Euklidsk algoritme er ein av dei eldste kjende algoritmane, sidan han st?r skildra i Elementa av Euklid fr? rundt 300 fvt. (7. bok, proposition 2). Euklid formulerte opphavleg problemet geometrisk, som problemet med ? finne det st?rste ?m?let? for to linjelengder (ei linje som kunne brukast til ? m?le begge linjer utan nokon rest), og algoritmen hans skreid fram ved gjentekne substraksjonar av det kortaste fr? det lengste linjestykket. Algoritmen vart end? truleg oppdaga av Euklid og dermed kjent opp til 200 ?r tidlegare.

Han var nesten sikkert kjent av Eudoksos fr? Knidos (omkring 375 fvt.), og Aristoteles (omkring 330 fvt.) indikert han i hans Topics, 158b, 29–35.

Skildring av algoritmen

Gjeve to heiltal, a og b, finn st?rste heiltala d slik at d deler a og b. Viss b = 0, returner a. Elles blir prosessen gjenteke med tala b og a modulo b. Det er òg mogleg ? bruke gjenteke subtraksjon, der det minste talet trekkjast fr? det st?rste, heilt til éit av tala er 0. Dette er den opphavlege algoritmen, men han er mindre effektiv.

Implementering

Nytte av rekursjon

Ved bruk av rekursjon, kan algoritmen uttrykkjast som:

 funksjon SFD(a, b)
     viss b = 0 returner a
     ellers returner SFD(b, a mod b)

I blant anna C++ og Java ser algoritmen slik ut:

 int SFD(int a,int b){
   if ( b == 0 )
     return a;
   return SFD(b,a%b);
 }

Bruk av iterasjon

Ein effektiv iterativ metode for kompilatorar som ikkje optimiserar halerekursjon:

 funksjon SFD(a, b)
     s? lenge b ≠ 0
         t := b
         b := a mod b
         a := t
     returner a

D?me

Finn st?rste felles faktor til 42 og 24.

a = 42, b = 24

a = 24, b = (42 mod 24) = 18

a = 18, b = (24 mod 18) = 6

a = 6, b = (18 mod 6) = 0

b = 0, s? svaret er a = 6

Kjelder

Denne artikkelen bygger p? ?Euklids algoritme? fr? Wikipedia p? bokm?l, den 16. september 2011.

征候是什么意思	属鸡的守护神是什么菩萨	现在是什么年代	胆固醇高会引起什么病	兔和什么属相最配
后装治疗是什么意思	前列腺炎忌口什么食物	做梦梦到鸡是什么意思	火碱是什么东西	梦到火是什么意思
快乐源泉是什么意思	优雅知性是什么意思	为什么老放屁	肛门坠胀吃什么消炎药	女性尿酸高有什么症状表现
嘴唇上火起泡是什么原因	频繁流鼻血是什么原因	熬夜后吃什么恢复元气	不可或缺是什么意思	吃三七有什么功效

考试前吃什么能让大脑发挥最佳hcv8jop3ns5r.cn	命中注定是什么意思hcv8jop8ns7r.cn	功名利禄是什么意思hcv7jop5ns6r.cn	多吃山竹有什么好处hcv9jop1ns5r.cn	左眼皮跳是什么预兆女hcv9jop7ns4r.cn
守株待兔是什么生肖hcv8jop1ns3r.cn	食指有痣代表什么意思zhongyiyatai.com	什么球不能踢hcv9jop0ns5r.cn	春宵一刻值千金是什么意思hcv7jop6ns2r.cn	太阳穴疼什么原因beikeqingting.com
小弟一阵阵的疼什么原因hcv8jop0ns7r.cn	肺癌靶向治疗是什么意思clwhiglsz.com	什么叫寓言故事hcv9jop1ns5r.cn	湾仔码头水饺为什么贵0297y7.com	流金是什么字hcv9jop2ns2r.cn
十二指肠球炎是什么意思shenchushe.com	鼻窦炎吃什么药好hcv8jop8ns9r.cn	柴胡有什么功效hcv8jop2ns7r.cn	长裙配什么鞋子好看hcv9jop7ns2r.cn	怀孕上火吃什么能降火yanzhenzixun.com