Тақырыбы: Евклид алгоритмі. ЕҮОБ, екое есептеу Күні
жүктеу/скачать 69,25 Kb.
|
Евкл алг-ЕШП-МК-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 Евклид алгоритмін кесте ретінде жазуға болады.
ЕҮОБ (468,252)=36
ЕҮОБ (1920;1536)=384
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.
жүктеу/скачать 69,25 Kb. Достарыңызбен бөлісу:
|