Amaliy mashg‘ulotlarni bajarish buyicha uslubiy ko’rsatmalar. Amaliy mashg’ulot. Mavzu

GCD ni bo'lish orqali topish algoritmi

1. 
   Katta raqamni kichikroq raqamga bo'ling.
   
2. 
   Agar u qoldiqsiz bo'lingan bo'lsa, unda kichikroq raqam GCD (siz tsikldan chiqishingiz kerak).
   
3. 
   Agar qoldiq bo'lsa, katta raqam bo'linishning qolgan qismiga almashtiriladi.
   
4. 
   Biz 1-bandga o'tamiz
   

Misol:
30 va 18 uchun GCD ni toping.
30/18 = 1 (qolgan 12)
18/12 = 1 (qolgan 6)
12/6 = 2 (qolgan 0)
Oxiri: GCD 6 ning bo'luvchisidir.
GCD (30, 18) = 6
a = 50 b = 130 esa a! = 0 va b! = 0: agar a> b: a = a% b boshqa: b = b% a bosma (a + b)
Tsiklda bo'linishning qolgan qismi a yoki b o'zgaruvchiga yoziladi. O'zgaruvchilardan kamida bittasi nolga teng bo'lganda tsikl tugaydi. Bu shuni anglatadiki, ikkinchisida GCD mavjud. Biroq, qaysi biri, biz bilmaymiz. Shuning uchun, GCD uchun biz ushbu o'zgaruvchilarning yig'indisini topamiz. O'zgaruvchilardan biri nolga teng bo'lgani uchun u natijaga ta'sir qilmaydi.

GCDni ayirish orqali topish algoritmi

1. 
   Katta raqamdan kichikroqni ayiring.
   
2. 
   Agar u 0 bo'lib chiqsa, bu raqamlar bir-biriga teng va GCD (sikldan chiqish kerak) degan ma'noni anglatadi.
   
3. 
   Agar ayirish natijasi 0 bo'lmasa, katta raqam ayirish natijasi bilan almashtiriladi.
   
4. 
   Biz 1-bandga o'tamiz.
   

Misol:
30 va 18 uchun GCD ni toping.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Oxiri: GCD chegirib tashlanadi yoki ayiriladi.
GCD (30, 18) = 6


1-Amaliy mashg’ulot.
Mavzu: Tyuring mashinasi.

TYURING MASHINASINING VAZIFALARI

Algoritmlarni echishda ko'pincha funktsiyani amalga oshirish talab qilinadi. Hisoblash uchun zanjirni yozish imkoniyatiga qarab, funktsiya algoritmik hal qilinadigan yoki hal etilmaydigan deb ataladi. Tabiiy yoki ratsional sonlar to'plami sifatida, mashina uchun chekli N alifbosidagi so'zlar, biz B to'plamining ketma-ketligini ko'rib chiqamiz - B = (0,1) ikkilik kod alifbosi doirasidagi so'zlar. Shuningdek, hisoblash natijasi algoritm "osilib qolganda" yuzaga keladigan "aniqlanmagan" qiymatni hisobga oladi. Funktsiyani amalga oshirish uchun rasmiy tilning cheklangan alifboda mavjudligi va to'g'ri tavsiflarni tanib olish muammosi hal qilinishi muhimdir.