2 Лаборатория иши Шахсий компьютерларда маълумотларнинг таърифланиши, кодлаш

Мисол 1. a = 24 ва b = 18 сонларини кўриб чиқамиз.Уларни оддий кўпайтма шаклида ёзиб оламиз 24 = 2³·3, 18 = 2·3². Шунингдек

НОД(24, 18) = 2^min(3,1) · 3^min(1,2) = 2¹ · 3¹ = 6,

   НОК(24, 18) = 2^max(3,1) · 3^max(1,2) = 2³ · 3² = 8 · 9 = 72

Худди шундай сонларни каноник усулда ёзилишини биз мактабда ЭУБ ва ЭУК ни топиш учун ўрганганмиз.Бироқ, бу усул алгоритмни ҳисоблашни реализациясида у даражада эффектли эмас.

Кейинги яққол фактни кўриб чиқамиз. Агар ЭУБ(a, b) = d, унда a ва b , d.га бўлинади. a – b фарқи ҳам d га бўлинади. ЭУБ ни ҳисоблашни рекуррентлиги


Мисол 2. a = 32, b = 12 бўлсин, унда

   НОД(32, 12) = НОД(32 – 12, 12) = НОД(20, 12) = НОД(20 – 12, 12) = НОД(8, 12) =

   = НОД(8, 12 – 8) = НОД(8, 4) = НОД(8 – 4, 4) = НОД(4, 4) = НОД(4 – 4, 4) = НОД(0, 4) = 4

Бу ҳисоблаш усули оптимал ҳисобланмайди.Масалан, НОД(1000000, 2)ни топиш учун 500000 ҳисоблаш операциясини бажариш керак бўлади. ЭУБ(НОД) ни ҳисоблашни тезроқ амалга ошириш учун айирма операциясини бўлинмадан қолган қолдиқни олишга алмаштирамиз:

Мисол 3. a = 78, b = 14. ,бўлсин, унда
НОД(78, 14) = НОД(78 mod 14, 14) = НОД(8, 14) = НОД(8, 14 mod 8) = НОД(8, 6) =

   = НОД(8 mod 6, 6) = НОД(2, 6) = НОД(2, 6 mod 2) = НОД(2, 0) = 2

Шартлар сонини иккига қисқартириш эвазига юқоридаги рекурентликни соддалаштирамиз:


Агар a < b, то НОД(a, b) = НОД(b, a mod b) = НОД(b, a), яъни функция аргументлари келтирилади. Кейинги функция чақирилишида ЭУБ(НОД) биринчи аргумент иккинчисидан катта бўлади. Фақат иккинчи аргумент b ноль бўлиши мумкин.

7 Жадвал

вариантнинг раками	А ва В формулалар учун	х, y
1	2	3
1	A= B=x(arctgA+e^-(x-1))	x = 3 y = -1,4
2		x=2 y=3.1
3	B=(1+tg^2	x= -2,3 y= 2,7
4		x=-5,3 y=2,5
5		x=1,6 y=-6,2
6		x=4 y=3,4
7		x=3,6 y=5,5
8
9
10