Texnalogiyalarini rivojlantirish vazirligi toshkent axborot texnalogiyalar unversiteti qarshi filiali

O’ZBEKISTON RESPUBLIKASI AXBOROT
TEXNALOGIYALARINI RIVOJLANTIRISH VAZIRLIGI
TOSHKENT AXBOROT TEXNALOGIYALAR UNVERSITETI
QARSHI FILIALI ‘’TT VA KT’’ FAKULTETI

‘’AX 11-19’’ GURUHI TALABASI Toshniyozov Og'abekning

‘’KRIPTOGRAFIYA” FANIDAN BAJARGAN

15-AMALIY ISHI

Qabul qildi: Bekkamov Fayzi
Tahrirladi: Toshniyozov O
15-Amaliy mashg‘ulot

Ishdan maqsad – Sonning eng katta bo‘luvchisini topish uchun Evklid algoritmidan foydalanishni o‘rganish, hamda ushbu algoritm dasturini tuzish.

Yevklid algoritmi qadamlari:

1. 
   Ikkita sondan kattasini kichigiga bo’lib qoldiq olamiz.
   
2. 
   Ularni o’rnini almashtiramiz
   
3. 
   1- va 2-qadamlarni sonlardan biri nol bo’lib qolguncha davom ettiramiz
   
4. 
   Qolgan son shu ikki son uchun EKUB bo’ladi.
   

Yevklid algoritmi qay tarzda ishlaydi. (Geometrik)
Bilamizki, Yevklid geometriya fani olimi bo'lgan shuning uchun u yaratgan algoritmni geometriya orqali tushuntirib berishga harakat qilamiz.
Misol: 38 va 16 sonlarining EKUBini Yevklid algoritmi yordamida toping.
K eling tomonlari 38 va 16 bo'lgan to'g'ri to'rtburchak chizib olamiz
Endi bu to'rtburchakdan tomoni 16 ga teng bo'lgan kvadratlarni ajratib olamiz.

Bu narsa bizga 38 ni 16 ga bo'lgandagi butun va qoldiq qismni vizual ko'rsatib beradi. Ya'ni:

O'ng tarafdagi bo'yalmagan qism bizdagi qoldiqni (6) ifodalaydi. Endi yuqoridagi ishni o'sha 16 ga 6 tomonli to'g'ri to'rtburchak uchun davom ettiramiz.

Huddi yuqoridagidek:

Shu tarzda qoldiq nolga tenglashguncha davom etamiz.






Shu joyda algoritm o'z ishini yakunlaydi va eng kichik kvadrat tomoni (2) bizga 38 va 16 uchun EKUBni beradi.
Bu holatda tomoni to'g'ri to'rtburchak tomonlari EKUBiga teng bo'lgan kvadrat shu to'g'ri to'rtburchakning barcha sohasini to'ldirib chiqa oladigan eng katta tomonli kvadrat.

Dasturi:
#include

using namespace std;
int EKUB(int a, int b) {
if (b == 0)
return a;
return EKUB(b, a % b);
}
int main() {
int a , b;
cout<<"a va b ning qiymatlarini kiriting "<cin>>a>>b;
cout}

Natijasi: