evklid algoritmi

DOC 195,0 КБ Бесплатная загрузка

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1576161224.doc b a m n n c c m 1 - n n c c m 2 - n n c c m 3 - n c c m 2 n c c m 1 x c m 3 x c m 4 x c n m d b a × d b a h × = d a b h × = v d b u d a × = × d a d b d b t d b u × = t d ab t d b a au x × = × × = = d ab 2772 42 252 462 ) 252 , 462 ( = × = ekuk s k s k k p p p m × × × = ... 2 1 2 1 s l s l l p p p n × × × = ... 2 1 2 1 …

nlar, eng kichik umumiy bo`linuvchi va boshqa xossalarni keltirib chiqargan. yevklid algoritmi ikkita kesmaning eng katta umumiy o`lchovini topish usuli sifatida (ba`zan u navbatma-navbat ayirish ham deb ataladi) pifagorchilarga ham ma`lum edi. xvi asr o`rtalarida yevklid algoritmi bir o`zgaruvchili ko`phadlarga ham tatbiq etildi. keyinchalik yevklid algoritmini ba`zi bir boshqa algebraik ob`ektlar uchun ham aniqlashga muvaffaq bo`lindi. yevklid algoritmi ko`p tatbiqlarga ega. uni aniqlovchi tengliklar a va b sonlarning eng katta umumiy bo`luvchisi bo`lgan d sonini d=ax+by ko`rinishida ifodalash imkonini beradi (x; y — butun sonlar), bu formula esa ikki noma`lumli birinchi darajali diofant tenglamalari yechimlarini topishga asos bo`ladi. yevklid algoritmi ratsional sonni uzluksiz kasr sifatida tasvirlash vositasi hamdir. u ko`pincha elektron hisoblash mashinalari dasturlarida qo`llaniladi, sonlar nazariyasida ham ahamiyati kattadir. 2. eng katta umumiy bo`luvchi (ekub) ta`rif: a1,a2,a3,…,an(z sonlarning umumiy bo`luvchisi deb, berilgan sonlarning har biri bo`linadigan d(z songa aytiladi. berilgan sonlarning umumiy bo`luvchi shu sonlarning barcha umumiy bo`luvchilariga bo`linsa, …

ma-ketlikni quyidagi tuzamiz: c1=a, c2=b deb olamiz. agar bo`lsa, ekub(a,b)=b bo`ladi. aks holda c1 ni c2 ga bo`lishda hosil bo`lgan qoldiqni c3 deb olamiz, c2 ni c3 ga bo`lishdagi qoldiqni c4 deb olamiz va hokazo. bunday qoldiqli bo`lishlar ketma-ketligini qulaylik uchun tengliklar zanjiri ko`rinishida bunday yozamiz: c1=c2q2+c3 c2=c3q3+c4 c3=c4q4+c5 ………… cn-2=cn-1qn-1+cn cn-1=cnqn qoldiqli bo`lish natijasida qoldiqlar uchun c2>c3>c4… munosabat o`rinli bo`ladi, bundan tashqari qoldiqlar nomanfiy sonlardir. shu sababli bu qoldiqlar orasida nolga teng bo`ladigani albatta uchraydi. cn uchun noldan farqli oxirgi qoldiqni olamiz. bu holda cn-1 soni cn ga bo`linishi ravshan. hosil qilingan c1, c2, c3, …, cn-1, cn ketma-ketlik a va b sonlari uchun evklid ketma-ketligi deyiladi. ketma-ket qoldiqli bo`lish yordamida bunday ketma-ketlikni hosil qilish usuli evklid algoritmi deb ataladi. misol. 78 va 24 sonlari uchun evklid ketma-ketligini tuzing. yechilishi. 78=24(4+18 24=18(1+6 18=6(3+0 bundan, izlangan ketma-ketlik hosil bo`ladi: 78, 24, 18, 6. теорема. a va b (a≠0,b≠0) sonlar uchun …

ta`tifga ko`ra, cn=ekub(a,b). misol. ekub(42598, 2014) ni toping. yechilishi. berilgan sonlar uchun evklid ketma-ketligini tuzamiz. qoldiqli bo`lishlar ketma-ketligini quyidagi sxema bo`yicha bajarish qulay: _42598 ( 2014 4028 21 _ 2318 2014 _ 2014 ( 304 1824 6 _ 304 ( 190 190 1 _ 190(114 114 1 _ 114 ( 76 76 1 _ 76 ( 38 76 2 0 javob: ekub(42598, 2014) = 38. mashqlar. evklid algoritmi yordamia quyidagi sonlarning ekub ini toping: 1) 645 va 381; 2) 846 va 246; 3) 15283 va 10013; 4) 6188 va 4709 ; 5) 4005 va 2581. javob: 1) 3; 2) 6; 3) 527; 4) 17; 5) 89. 3. eng kichik umumiy karrali (ekuk) ta`rif: a1, a2, a3, … , an(z sonlarning har biriga bo`linadigan son bu sonlarning umumiy karralisi (bo`linuvchisi) deyiladi. berilgan sonlarning istalgan umumiy karralisining bo`luvchisi bo`lgan umumiy karralisi bu sonlarning eng kichik umumiy karralisi deyiladi. berilgan sonlarning eng kichik …

a chekli sondagi istalgan tub sonlarni bir xil tub sonlar nomanfiy butun ko`rsatkichli darajalarining ko`paytmasi shaklida tasvirlash mumkin. misol. a=25(5(133, b=32(74, c=53(172 sonlarni bir tub sonlar darajalarining o`paytmasi shaklida yozing. yechilishi. a=25(5(133=25(30(51(70(133(170, b= b=32(74=20(32(50(74(130(170, c=53(172=20(30(53(70(130(172. teorema. ikkita va natural sonlar berilgan bo`lsin, bunda p1, p2, …, ps — turli tub sonlar, ki va li — daraja ko`rsatkichlar esa nomanfiy butub sonlar. m soni n soniga bo`linidhi uchun barcha i =1, 2, … , s uchun ki ( li tengsizlik bajarilishi zarur va yetarli. isboti: ( agar m=nx, bunda x(n, bo`lsa, x ning istalgan tub bo`luvchisi p1, p2, … , ps sonlardan biriga teng bo`ladi. shuning uchun kabi yozish mumkin,bu yerda ti(0. bundan . natural sonning tub ko`paytuvchilarga yoyilmasining yagonaligidan ki=li+ti, bundan esa barcha i=1, 2, 3, … , s uchun ki(li ekani kelib chiqadi. ( agar barcha i=1, 2, 3, … , s uchun ki(li bo`lsa, u holda bo`ladi. bundan …

Хотите читать дальше?

Скачайте полный файл бесплатно через Telegram.

Скачать полный файл

О "evklid algoritmi"

1576161224.doc b a m n n c c m 1 - n n c c m 2 - n n c c m 3 - n c c m 2 n c c m 1 x c m 3 x c m 4 x c n m d b a × d b a h × = d a b h × = v d b u d a × = × d a d b d b t d b u × = t d ab t d b a au x × = × × = = d ab 2772 42 252 462 ) 252 , 462 ( = × = ekuk s k s k k p …

Формат DOC, 195,0 КБ. Чтобы скачать "evklid algoritmi", нажмите кнопку Telegram слева.

Теги: evklid algoritmi DOC Бесплатная загрузка Telegram