Тақырыбы: Евклид алгоритмі. ЕҮОБ, екое есептеу Күні



бет2/3
Дата06.02.2022
өлшемі69,25 Kb.
#81336
түріПрактикум
1   2   3
Байланысты:
Евкл алг-ЕШП-МК-115-25.09.20ж

Анықтама. сандарының ең кіші ортақ еселігі деп осы сандардың кез келген ортақ еселігін бөлетін ортақ еселікті айтамыз.
Ескерту. Егер m саны  бүтін сандарының ең кіші ортақ еселігі болса, онда - нен өзгеше осы сандардың басқа ең кіші ортақ еселігі болмайды. бүтін сандарының теріс емес ең кіші ортақ еселігі  түрінде белгіленеді.
Теорема  және  натурал сандары үшін келесі формула орындалады:
.
Екі санның ЕҮОБ –ін тапқанда «Евклид алгоритмі» деп аталатын ережені білген дұрыс.
Евклид алгоритмі - екі бүтін санның, екі көпмүшенің ең үлкен ортақ бөлгішін немесе екі кесіндінің ортақ өлшемін табу тәсілі. Біздің заманымыздан бұрынғы III ғасырда өмір сүрген ежелгі грек математигі Евклид  (б.з.б. 330 - 275) геометриялық тәсілмен сипаттаған. Екі санның Ең үлкен ортақ бөлгішін табу үшін Евклид алгоритмі пайдаланылады.
ЕҮОБ-ін қалай табуға болатынын қарастырайық: Қалдықпен бөлуді тізбектей орындау арқылы шектеулі қадамнан соң 0 қалдық алатынымыз түсінікті. Себебі әр қалдық өзінің алдындағы қалдықтан кем және ден кем емес болатындықтан шектеусіз жалғасуы мүмкін емес. Немесе қалдық нольге тең болады, ЕҮОБ- табуға арналған бұл тәсілді Евклид алгоритмі деп атайды.
Мысал-1. ЕҮОБ (270, 186) табыңыз. 270-ті 186-ға қалдықпен бөлейік:
270: 186=1 (қал. 84)
Енді бөлгішті қалдыққа бөлейік және т.с.с.:
186 : 84 = 2 (қал. 18)
84 : 18 = 4 (қал. 12)
18:12 =1 (қал. 6)
12:6=2 (қал. 0)
270 пен 186-ның ЕҮОБ-і –оларға Евклид алгоритмін қолданғандығы ең соңғы нөлден өзгеше қалдық, яғни 6 саны.
Мысал-2: ЕҮОБ (102,84) Евклид алгоритмі арқылы табу.
102 :84 = 1 (18 қалдық), 102=84 * 1+18, 0<18 <84
84 : 18 = 4 (12 қалдық), 84 18*4 +12, , 0<12 <18
18 :12 = 1 (6 қалдық), 18 12*1 +6, 0<6 <12
12 : 6 6 ЕҮОБ (102,84)=6
Евклид алгоритмін кесте ретінде жазуға болады.

102

84

18

12

6




1

4

1

2

ЕҮОБ (468,252)=36



468

252

216

36




1

1

6

ЕҮОБ (1920;1536)=384



1920

1536

384




1

4

3-мысал . ЕҮОБ( 1071, 462) =? Шешуі:
1071 = 2 × 462 + 147.
462 = 3 × 147 + 21.
147 = 7 × 21 + 0.
a > b > r1 > r2 > r3 > … > rn :
1071 > 462 > 147 > 21.
ЕҮОБ (1071, 462) = 21.

 k



Достарыңызбен бөлісу:
1   2   3




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет