linkedin facebook linkedin facebook nod32

Olimpiada misollarini yechish usullari I- bosqich

Muallif: Mengliyev Sh.

Qo`shilgan sana: 2015-04-08

Olimpiada misollarini yechish usullari I – bosqich

1 -misol. n butun soning raqamlari aniqlansin va ekranga chiqarilsin.
Bu masalaning matematikasini xususiy misolda ko’rib chiqaylik.
4538 soning raqamlarini topaylik. Buning uchun butun sonlarni bo’lganda qoldiqni topishga mo’ljallangan buyruq (mod) yordamida 4538 ni 10 ga bo’lgandagi qoldiqni topaylik :
4538 mod 10 = 8, sonning oxirgi raqamini hosil qilamiz (u ham bo’lsa o’ng tomondan birinchisi).
"O’ng tomondan 1 – raqam 8 ga teng " degan xabar chop etamiz.
Bu holdan so’ng 4538 ni 10 ga butun bo’lib 453 hosil qilamiz (qoldig’ini tashlab yuboramiz):  
4538 div 10 = 453.
So’ngra jarayonni qaytaramiz:
2 - marta;                   453 mod 10 = 3
O’ng tomondan 2-raqam 3 ga teng,
453 div 10 = 45,
3 - marta;                     45 mod 10 = 5,
O’ng tomondan 3-raqam 5 ga teng,
45 div 10 = 4,
4 - marta;                     4 mod 10 = 4,
O’ng tomondan 4-raqam 4 ga teng,
4 div 10 = 0.

Dasturda shuningdek, sondagi tartib bo’yicha qaysi raqam o’ng tomonda ekanligini ko’rsatib o’tish kerak. Buning uchun hisoblagich sifatida yana bir o’zgaruvchi kiritish kerak. Bu o’zgaruvchi har siklda 1 ga oshishi kerak.
Dastur

Program L1; {Sonning raqamlarini aniqlash va ekranga chiqarish}
uses Crt;
var
n, p, i : integer;
begin
write('natural n sonini kiriting,  n <= 32767 '); readln(n);
i := 1;
while n <> 0 do
begin
p := n mod 10;
writeln(‘o’ng tomondan’,  i, ' hi raqam= ', p);
n := n div 10;
i := i + 1
end
end.
Dasturning qurilishi va uning ishlashi

Ta’riflar bo’limida
n - o’zgaruvchi butun son uchun, p – sonning raqamlari uchun, i – raqamlar hisoblagichisi.
Operatorlar bo’limida
Write operatori yordamida ekranga foydalanuvchi uchun butun sonni kiritish kerakligi to’g’risida xabar chiqadi.  Readln operatori uning qiymatini xotiraga joylashtiradi va n o’zgaruvchiga beradi.
I - hisoblovchiga boshlang’ich qiymat sifatida 1 joriy etiladi.
while operatorida sikl bajariladigan shart yoziladi ( n 0 ga teng bo’lmagunicha).
Siklda bir nechta operator bo’lgani uchun,  
begin ... end.
operator qavslari ishlatiladi. Ularning ichida quyidagi operatorlar yozilgan:
p := n mod 10; - oxirgi raqam aniqlanadi ;
writeln(‘o’ng tomondan’ i, 'chi raqam=', p); - o’ng tomondagi raqamning tartib raqami va raqamning o’zi chiqariladi;
n := n div 10; - sondagi oxirgi raqam  "o’chirib tashlanadi";
i := i + 1; - hisoblagich 1 ga oshadi.
2 -misol. Kiritilgan natural sonning birinchi va oxirgi raqamlarini o’rnini amashtiruvchi dastur tuzilsin.
Bu masalaning matematikasini xususiy misolda ko’rib chiqaylik.
Foydalanuvchi tomonidan 4538 soni kiritilgan bo’lsin. Birinchi va oxirgi raqamlarining o’rnini almashtirgandan so’ng ushbu son quyidagi ko’rinishga kiradi: 8534.
Sonning oxirgi raqamini aniqlash qiyin emas. Buni bizga ma’lum usulda qilsa bo’ladi: 4538 mod 10.
Sonning birinchi raqamini topish va ajratish uchun oldingi dasturlarda sonning raqamlarini chiqarish va raqamlar yig’indisini hisoblash uchun qo’llanilgan usuldan foydalanish, ya’ni o’ng tomondan bittadan raqam ajratish kerak. Oldingi dasturlarda bu holga o’xshash jarayon n<>0 (n nolga teng bo’lmagan) bo’lguncha davom etardi, n nolga teng bo’lib qolganda esa sikl tugardi, ya’ni barcha raqamlar, jumladan birinchisi ham, ajratilgan bo’lardi, ammo hozir ushbu jarayonni bitta raqam oldinroq to’xtatish kerak, shu holda n o’zgaruvchining oxirgi qiymati sonning birinchi raqami bo’ladi.
Bizning misolimizda u 4 ga teng.
Shu hol kabi, birinchi va oxirgi raqamlar topildi. Ularning sondagi o’rnini qanday qilib almashtirish kerak?
Biz kiritgan son uchun buni quyidagicha qilish mumkin. 1000 ga ko’paytirigan birinchi raqamni sonning o’zidan ayiramiz va oxirgi raqamini  ayiramiz:     
4538 - 4x1000 - 8 = 530.
Hosil bo’lgan natijaga 1000 ga ko’paytirilgan oxirgi raqamni- 8  qo’shamiz va birinchi raqamini  qo’shamiz:  530 + 8x1000 + 4 = 8534.
Oxirgi 2 ta jarayonni bitta qatorda yozsak bo’ladi:
4538 - 4x1000 - 8 + 8x1000 + 4 = 8534.
Bitta qiyinchilik tug’iladi. Birinchi raqam (chapdan birinchi) joylashgan razryadni qanday qilib aniqlaymiz va uni ayirishdan avval nechaga ko’paytiramiz? U minglarmi, o’ng minglarmi  yoki boshqa razryadmi?
Buni aniqlash uchun, boshlang’ich qiymati 1 ga teng bo’lgan o’zgaruvchini kiritamiz, so’ngra har raqam ajratishda u 10 ga ko’paytirilaveradi.
4538 soni -misolida butun jarayonni ko’rib chiqaylik.
Boshlang’ich qiymatlar: n = 4538, i = 1.
Sikl n >= 10 bo’lguncha davom etadi, 4538 >= 10 - rost, demak sikl operatorlari birinchi marta bajariladi:  i := i*10 = 1*10 = 10;  i o’zgaruvchi birinchi qiymat qabul qiladi,
n := 4538 div 10 = 453.
453 >= 10 shartini tekshiramiz – shart bajarilmoqda, demak sikl ikkinchi marta bajariladi:  i := i*10 = 10*10 = 100; n := 453 div 10 = 45.
45 >= 10 shartini tekshiramiz – rost, demak sikl uchinchi marta bajariladi:  
i := i*10 = 100*10 = 1000, n := 45 div = 4.
4>=10 shartini tekshiramiz – yolg’on, demak, sikl operatorlari bajarilmayapti. Sikl tugaydi.
O’zgaruvchilarning oxirgi qiymatlari: n=4- sonning birinchi raqami, i=1000. Endi raqamlarning o’rnini almashtirish va natijani ekranga chiqarish jarayonini bajarish qoldi holos.

Dastur

Program L2; { Sonning birinchi va oxirgi raqamlarini o’rnini amashtirish}
uses Crt;
var
n, n1, p, a, i : integer;
begin
write('n natural sonini kiriting’ ); readln(n);
a := n;  i := 1;
p := n mod 10; {kiritilgan sonning oxirgi raqami}
while n >= 10 do
begin
i := i*10;
n := n div 10;
end;
n1 := a - n*i - p + n + p*i;
writeln(Raqamlarning o’rnini almashtigandan so’ng hosil bo’lgan son ', n1);
end.

3 -misol. Berilgan n>= butun sonnini o’zining  raqamlarini teskari tartibda yozish orqali hosil qilingan songa almashtirib beruvchi dastur tuzing.  
1-usul
Program L3_1;
uses Crt;
var
n, p, n1 : longint;
begin
write(‘Natural  n sonini kiriting '); readln(n);
n1 := 0;
while n > 0 do
begin
p := n mod 10;
n1 := n1*10 + p;
n := n div 10
end;
writeln('Raqamlarning o’rnini almashtirgandan so’ng hosil bo’lgan son ', n1 + n)
end.
2-chi usul
Program L3_2; 
uses Crt;
var
n, p, n1 : longint;
begin
write('Natural son kiriting'); readln(n);
n1 := 0;
while n > 0 do
begin
n1 := n1*10 + n mod 10;
n := n div 10
end;
writeln('Raqamlarning o’rnini almashtirgandan so’ng hosil bo’lgan son=', n1)
end.

4 -misol. n natural sonini  tub ko’paytuvchilarga ajratuvchi dastur tuzing.
Avvalambor, tub sonlarga 2 ta bo’luvchiga ( 1 va o’zi) ega bo’lgan natural sonlar kirishini esga tushiraylik.
2 tadan ortiq bo’luvchiga ega bo’lgan natural sonlar- murakkab sonlar deyiladi.
Bir faqat bitta bo’luvchiga - o’ziga ega bo’lganligi uchun u na tub, na murakkab sonlarga kiradi. Agar tub sonlarni  eng kichig i- 2 dan boshlab o’sish tartibida yozsak, quyidagi sonlardan iborat qatorni hosil qilamiz:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
Endi, kichik sinflarda biz natural sonlarni qanday qilib tub ko’paytuvchilarga ajratganimizni eslaylik. 
Buning uchun birinchi tub sonni - 2 ni olamiz va ushbu natural sonni 2 ga bo’lib ko’ramiz, agar son 2 ga bo’linsa, u holda 2 ni yozib olish kerak, sonni esa 2 ga bo’lib, hosil bo’lgan natijani  yana 2 ga bo’lib ko’ramiz, agar bo’linsa, bo’lish jarayonini davom ettiramiz, agar bo’linsa, keyingi tub songa-3 ga bo’lib ko’ramiz va h.k
Odatda bunday jarayonni biz  "ustun" qilib yozardik:                
Shunday qilib, 360 soni quyidagi tub ko’paytuvchilarga ajratish mumkin:
360 = 2x2x2x3x3x5.

Dastur tuzish uchun yozilgan eng oddiy algoritm quyidagicha bo’lishi mumkin.

Algoritm

Birinchi bo’luvchi sifatida 2 ni olib, ushbu qiymatni i ga berib qo’yamiz;
" i <= n bo’lguncha" degan sikl boshlansin;
agar berilgan n soni i ga bo’linsa, i ning qiymati ekranga chiqarilsin, berilgan sonni i ga bo’lib, yangi qiymat n o’zgaruvchiga  (n := n div i) “yozilsin”;
so’ngra sikl davom ettirilsin, lekin I ning qiymati 1 ga oshirilmasin, faqatgina n ning yangi qiymatini i ning oldingi qiymatiga bo’linish yoki bo’linmasligi tekshirilsin.
agar n i ga bo’linmasa, i ning qiymati 1 ga ortsin 1 (i := i + 1) va sikl davom ettirilsin, ya’ni siklning (i <= n) sharti tekshirilsin, so’ngra  n ni i ning yangi qiymatiga bo’linish yoki bo’linmasligi tekshirilsin.

 

Dastur

Program L4; {Sonni tub ko’paytaytuvchiga ajratish.. 1-usul}
uses Crt;
var
n, i : integer;
begin
write('Natural sonni kiriting’); readln(n);
write( n,  'sonining tub ko’paytuvchilari quyidagilar');
i := 2;
while i <= n do
if n mod i =0 then
begin
write(i, ' ');
n := n div i
end
else i := i + 1
end.

Albatta bu dastur komillikdan yiroq bo’lib, o’ziga xosligi bilan ajralib turmaydi.
U kompyuterga bo’lishni tekshirishda ko’plab ortiqcha buyruqlarni yuklab tashlaydi.
Quyida anchayin takomillashgan algoritm keltirilgan.
U quyidagi fikr - mulohazalarga asoslanadi.
Avvalambor, sonni faqat 2 ga bo’lamiz. Buning uchun 360 ni 2 ga tartib bo’yicha bo’lamiz: 

360:2=180 180:2=90 90:2=45

Shundan so’ng, olingan natijani toq sonlarga bo’lamiz. Jumladan, har bir toq sonni bir marotaba emas, bo’lish jarayoni o’z mazmunini yo’qotmagunicha bo’laveramiz.
3 ga bo’lamiz: 45:3 = 15, 15:3 = 5.
5 ga bo’lamiz: 5:5 = 1.
7 ga bo’lamiz, bo’linmaydi, keyingi toq songa bo’lib ko’ramiz.
9 ga bo’lamiz, bo’linmaydi, keyingi toq songa o’tamiz.
11 ga bo’lamiz, bo’linmaydi, va h.k
Toq sonlarga bo’lish jarayonini, ular mos bo’luvchiga bo’lish natijasida olinadigan xususiy sondan kichik yoki teng bo’lguncha davom ettiramiz.
Ushbu mulohazalar asosida dastur tuzamiz.   

Program L4a;
uses Crt;
var
i, n : integer;
begin
write('Butun sonni kiriting'); readln(n); writeln;
writeln( n, 'Butun sonning tub bo’luvchilari',);
while n mod 2 = 0 do {2 ga teng bo’lgan bo’luvchilarni chiqarish sikli}
         begin
write(2, ' ');
n := n div 2
end;
i := 3;
while i <= n do           {Toq bo’luvchilarni chiqarish sikli}
if n mod i = 0
then
begin                 
write(i, ' ');
n := n div i
end
else i := i + 2;
writeln
end.

5 -misol. Berilgan n butun sonning tarkibiga 2 raqami kirish yoki kirmasligini aniqlovchi dastur yozilsin.
Dasturni tuzish g’oyasi juda oson. Buning uchun sikl tuzilsin va  bizga ma’lum usul orqali raqamlar ajratilib, har bittasi 2 raqami bilan solishtirilsin. Agar raqam 2 ga teng bo’lsa, hisoblagichni (u ma’lum bir sonli o’zgaruvchi bo’lishi mumkin) 1 ga oshirish, aks holda, siklni davom ettirish kerak.
Sikl to’laligicha bajarilgandan so’ng, ya’ni sonning hamma raqamlari tekshirilib, har bittasi 2 raqami bilan solishtirilgandan keyin, yana bir marotaba shartli operatordan foydalanish va hisoblagich-o’zgaruvchining qiymatini 0 bilan tekshirish kerak. Agar o’zgaruvchining qiymati 0 ga teng bo’lsa, u holda 2 raqami sonning tarkibiga kirmaydi, aks holda- kiradi.   

ALGORITM

1. Boshlanish. n, p, k butun turdagi o’zgaruvchilar: n – kiritilayotgan son uchun;
p – ushbu sonning raqamlari uchun; k – sondagi 2 ga teng bo’lgan raqamlar sonini sanovchi- hisoblagich.
2. Butun sonni kiriting.
k  hisoblagichga boshlang’ich 0 qiymat beriladi.
3. n <> 0 bo’lguncha sikli. Siklda p o’zgaruvchiga sondagi  raqamning qiymati berilsin.
Agar p = 2 bo’lsa, k 1 ga oshirilsin.  
n sonidan oxirgi raqam ayirib tashlansin va 10 ga bo’linsin.
Sikl davom ettirilsin va tugatilsin.
4. Agar k = 0, bo’lsa " 2 raqami sonning tarkibiga kirmaydi ",  aks holda      "2 raqami sonning tarkibiga kiradi " degan xabar chiqarilsin.
5. Tamom
Dastur

Program L5; { 2 raqami sonning tarkibiga kiradimi? }
uses Crt;
var
       n, p, k : integer;
begin
write('Butun sonni kiriting'); readln(n);
k := 0;
while n <> 0 do
begin
p := n mod 10;
if p = 2 then k := k + 1;
n := n div 10
end;           
if k = 0  then writeln('2 raqami ushbu sonning tarkibiga kirmaydi')
else  writeln('2 raqami ushbu sonning tarkibiga kiradi')
end.

6 -misol. Raqamlar yig’indisi berilgan natural songa teng bo’lgan barcha uch xonali sonlar topilsin.
Program L6;
uses Crt;
var
n, a, p, b, s : integer;
begin
write('28 dan kichik bo’lgan natural sonni kiriting '); readln(a);
b := 100;
writeln(' Raqamlar yig’indisi a teng bo’lgan uch xonali sonlar');
write('quyidagilar:', a,);
while b < 1000 do
begin
s := 0; n := b;
while n <> 0 do
begin
p := n mod 10; 
s := s + p;
n := n div 10
end;
if s = a then write(b, ', ');
b := b + 1
end; writeln
end.
7-misol. O’zining raqamlari kublarining yig’indisiga ikki xonali sonni  qo’shganda, huddi shu raqamlardan tashkil topgan, lekin teskari tartibda yozilgan son hosil bo’lish xususiyatiga ega bo’lgan ikki xonali son topilsin. (Dasturda sikl oldindan to’xtatilsin).

Program L7;
uses Crt;
var
n, d, e : integer;
begin
n := 10;
write('Qidirilayotgan ikki xonali son');
while n <= 99 do
begin
d := n div 10;  e := n mod 10;
if n + d*d*d  +  e*e*e = e*10 + d then writeln(n);
n := n + 1
end
end.

8-misol. Raqamlarining yig’indisi kvadrati berilgan m songa teng bo’lgan, n dan kichik bo’lgan natural sonlarni chiqarish dasturi tuzilsin.
Masalaning mazmuni quyidagicha. Natural son kiritiladi (ungacha bo’lgan,   shartni qanoatlantiruvchi natural sonlar chiqariladi). Masalan foydalanuvchi 21 sonini kiritadi.
Foydalanuvchi kiritishi kerak bo’lgan 2-son- bu natural sonlardagi  raqamlar yig’indisining kvadratiga teng bo’lgan sondir.
Bu son aniq kvadrat bo’lishi kerakligi ravshan, masalan: 4, 9, 16, 25, 36 va h.k.
Foydalanuvchi 4 sonini kiritdi deb faraz qilaylik.
Raqamlar yig’indisining kvadrati 4 ga teng bo’lgan 1 dan 21 gacha bo’lgan barcha natural sonlarni topish kerak. 1, 2, 3, 4, 5, ..., 21 dan boshlab, berilgan shartni qanoatlantiruvchi sonlarni tanlay boshlaymiz.  
Bulardan birinchisi - 2, chunki 22 = 4,  ikkinchisi - 11, chunki (1 + 1)2 = 22 = 4, uchinchisi - 20, chunki  (2 + 0)2 = 22 = 4.
Boshqa shartni qanoatlantiruvchi 21-gacha bo’lgan natural sonlar yo’q.
Barcha tanlangan sonlarni ekranga chiqarish kerak, ya’ni 2, 11 va 20.

Algoritm

1. Ta’riflar bo’limi
O’zgaruvchilar: n, m, k, a, p, s. Butun turda.
n – natural sonlar qiymatlarini chegaralash uchun, m – raqamlar yig’indisi kvadrati (aniq kvadrat) solishtiriladigan son uchun, k – 1 dan n gacha bo’lgan natural sonlar uchun, a- raqamlari yig’indisi aniqlanishidan avval natural sonning o’zini xotiraga kiritish uchun, p- sonning raqamlari uchun, s- raqamlar yig’indisi  uchun.
2. Operatorlar bo’limi.  
n va m qiymatlarini kiritish. k uchun boshlang’ich qiymat belgilansin ( bu o’zgaruvchi 1 dan n gacha bo’lgan barcha natural sonlarni “ko’zdan kechiradi”,       k := 1).
k <= n bo’lguncha sikli.
Siklda: s yig’indi  uchun boshlang’ich qiymatlar belgilansin (s:=0); son a o’zgaruvchiga yozilsin (a:=k).  
Raqamlar yig’indisini hisoblash uchun sikl, k <> 0 bo’lguncha.
Siklda: ma’lum usul bilan sonning raqamlari bittama-bitta ajratilsin; Raqamlar yig’indisini hisoblagich sikl tugatilsin.
Shartning bajarilishi tekshirilsin.
Agar raqamlar yig’indisi kvadrati berilgan songa teng bo’lsa
u holda ushbu natural son ekranga chiqarilsin.
Keyingi sonni tekshirishga o’tilsin.
Sonlarni  tekshiruvchi asosiy sikl tugatilsin.
3. Dastur tugatilsin.

Ushbu algoritm bo’yicha dastur tuzamiz:

Program L8;
uses Crt;
var
n, m, k, a, p, s : integer;
begin
write('Qaysi natural songacha’);
write('qidirilayotgan sonlar chiqarilsin'); readln(n);
writeln('Raqamlari yig’indisi kvadratini qaysi son bilan’ );
write(' tekshirmoqdasiz. U aniq kvadrat bo’lishi kerak'); readln(m);
write('Qidirilayotgan sonlar: ');
k := 1;
while k <= n do
begin
s := 0; a := k;
while k <> 0 do
 begin
p := k mod 10;
s := s + p; 
k := k div 10
 end;
if sqr(s) = m then write(a, ' ');
k := a + 1
end
end.

Dasturda ikkita sikl mavjud. Birinchisi - tashqi (natural sonlar uchun), ikkinchisi - ichki (sondagi raqamlari yig’indisini hisoblash uchun).

9-misol. Raqamlari yig’indisi berilgan natural songa teng, barcha n <= 100000 natural sonlarni topish dasturini tuzing.
Program L9;
uses Crt;
var
n, a, p, b, s : integer;
 begin
write('Natural sonni kiriting '); readln(a);
b := 1;
writeln('Raqamlari yig’indisi’, a, ‘soniga  teng bo’lgan’);
write(‘natural sonlar quyidagilar: ');
while b < 32767 do
begin
s := 0; n := b;
while n <> 0 do
begin
p := n mod 10;  s := s + p;  n := n div 10
end;
if s = a then write(b, ', ');
b := b + 1
end; writeln
end.

19-misol.  2, 3, 4, 5, 6  sonlariga bo’lganda mos ravishda 1, 2, 3, 4, 5 qoldiqlarni beruvchi eng kichik natural son topilsin.

Masalani quyidagicha yechamiz: eng kichik natural son - bir olinadi va uni          2, 3, 4, 5 va 6 ga bo’lgandagi qoldiqlari topiladi; agar qoldiqlar 1, 2, 3, 4 va 5 ga teng bo’lsa, aynan bu son qidirilayotgan bo’ladi va uni ekranga chiqarib, dasturni tugatish, aks holda, keyingi natural son - 2 ni olib, uni tekshirish kerak bo’ladi va h.k
Ushbu g’oya asosida tuzilgan  dastur juda osondir:
Program L19;
uses Crt;
var
n : integer;
begin
n := 0;
repeat
n := n + 1;
until (n mod 2 = 1) and (n mod 3 = 2) and (n mod 4 = 3) and
               (n mod 5 = 4) and (n mod 6 = 5);
writeln(‘Qidirilayotgan butun son ', n)
end.

20-misol. O’ngdan chapga va chapdan o’nga bir xil o’qiladigan sonlar palindromlar deyiladi. Masalan 42324 yoki 1331 sonlari – palindrom. Berilgan oraliq ichida palindrom sonlarni topuvchi dastur tuzing.

Dasturni tuzish mantig’i quyidagicha:
Sondagi raqamlar o’rnini almashtirish va hosil bo’lgan sonni berilgan  son bilan solishtirish.
Sondagi raqamlar o’rnini almashtirishga doir dastur tuzilgan edi, u
while ... do ...
shartli sikl yordamida bajarilgan edi.
Shu yo’sinda, dasturda raqamlar o’rnini almashtirishga oid qism
repeat ... until ...
sikli yordamida qanday qurilishini ko’raylik.
a son berilgan bo’lsa, u holda yana bir b o’zgaruvchini kiritamiz, unga a o’zgaruvchining qiymati beriladi  (nima uchunligini keyinchalik bilib olamiz)    b:= a;
Yana bir o’zgaruvchi a1 ni raqamlarning o’rnilari almashtirilib bo’lingan yangi son uchun hosil qilamiz.
Ushbu o’zgaruvchining boshlang’ich qymati - nol:  a1 := 0;
Bu o’zgaruvchi nima uchun nolga tengligi dasturni ko’rib chiqqanimizdan so’ng ravshan bo’ladi. 
So’ngra, b sondagi raqamlarning o’rin almashish jarayoni kechadigan repeat siklini tashkil qilamiz:
repeat
a1 := a1*10 + b mod 10;
b  := b div 10
until b = 0;

Shunday qilib, siklda while ... do ... siklidagidek, оxirgi raqam ajratiladi:
b mod 10; (masalan, 343 mod 10 = 3); a1 o’zgaruvchiga quyidagi qiymat beriladi:
a1 := a1*10 + b mod 10; 0 * 10 + 3 =3;
Berilgan sondagi oxirgi raqam butun bo’lish operatsiyasi yordamida "tashlab yuboriladi " :
b := b div 10; 343 div 10 = 34;
b = 0, 34 = 0 shart tekshiriladi, shart bajarilmayapti, demak sikl davom etadi.
Yangi sondagi oxirgi raqam ajratiladi:
b mod 10 = 34 mod 10;
3 ga teng bo’lgan yangi a1 son, 10 ga ko’paytiriladi va natijaga keyingi raqam - 4 qo’shiladi:  
a1 := a1*10 + b mod 10;
b sondagi oxirgi raqam "tashlab yuboriladi":
b := b div 10 ; 34 div 10 = 3;
b = 0, 3 = 0 shart tekshiriladi; shart bajarilmayapti, demak sikl davom etadi.
Sonning oxirgi raqami ajratiladi:
b mod 10 ; 3 mod 10 = 3;
yangi son hosil bo’ladi:
a1 := a1*10 + b mod 10 ;  34 * 10 + 3 = 343;
sondagi oxirgi raqam "tashlab yuboriladi" va yangi son hosil bo’ladi: 
b := b div 10 ;  3 div 10 = 0;
b = 0, 0 = 0 shart tekshiriladi; shart bajarilmoqda, demak sikl tugatiladi.  
Endi, berilgan son uchun nega boshqa b o’zgaruvchi kiritilgani tushunarli, sonning sikldagi qiymati boshlang’ich qiymatdan boshlab 0 gacha o’zgaradi va a o’zgaruvchida berilgan sonni saqlash uchun “ishchi” o’zgaruvchi - b kiritiladi.  
Sondagi raqamlar o’rnini almashtirish sikli tugatilgandan so’ng, a o’zgaruvchida "saqlab qolingan" boshlang’ich son va raqamlar o’rnini almashtirgandan so’ng hosil bo’lib, a1 o’zgaruvchida "turgan" son solishtiriladi.
Agar a = a1 bo’lsa, u holda a ning qiymati ekranga chiqariladi, chunki bu son palindromdir.  
So’ngra, a ning qiymati 1 ga oshadi, ya’ni ko’rib chiqish uchun keyingi natural son olinadi va yana tashqi sikl davom etadi. Sondagi raqamlar o’rni almashtiriladi, raqamlar o’rnini almashtirgandan so’ng hosil bo’lgan yangi a1 son boshlang’ich a bilan solishtiriladi va h.k.
a ning qiymati n oraliqning o’ng chegarasiga teng bo’lib qolganida tashqi sikl tugatiladi.  

Dastur tuzamiz
Program L20;
uses Crt;
var
m, n, a, b, a1 : longint;
begin
write(' Oraliqning chap chegarasini kiriting '); readln(m);
write(' Oraliqning o’ng chegarasini kiriting '); readln(n);
a := m;
writeln('[', m, ';', n, '] oraliqdagi  palindrom sonlar');
repeat
b := a; a1 := 0;
repeat
a1 := a1*10 + b mod 10;
b  := b div 10
until b=0;
if a1 = a then write(a, ' ');
a := a + 1
until a > n;
end.

21-misol. Raqamlar soni juft bo’lgan 131 ga karrali eng kichik natural son topilsin.  Dastur tuzilsin.

Program L21;
uses Crt;
var
n, a, k : integer;
begin
n := 131;
repeat
n := n + 131;
a := n; k := 0;
repeat
k := k + 1;
a := a div 10
until a = 0;
until k mod 2 = 0;
writeln(‘ raqamlar soni juft bo’lgan ');
writeln('131 ga karrali eng kichik natural son= ', n)
end.

22-misol. Agar biz biror-bir sonning barcha raqamlarini qo’shib, so’ngra hosil bo’lgan yig’indining ham barcha raqamlarini qo’shib, bu jarayonni ko’p marotaba takrorlasak, oxir-oqibat bir xonali son (raqam) hosil qilamiz. Hosil bo’lgan raqam berilgan sonning raqamli ildizi deyiladi. Masalan, 561 soning raqamli ildizi 3 ga teng(5 + 6 + 1 = 12; 1 + 2 = 3).
Sonning raqamli ildizini topuvchi dastur tuzing.

Dasturni tuzishga oid fikr- mulohazalar

Dasturda sondagi raqamlar yig’indisini aniqlovchi sikl bo’lishi kerak. O’z navbatida, bu sikl raqamlar yig’indisining qiymati bitta songa teng bo’lib qolmagunicha, ya’ni 10 dan kichkina lekin 0 dan katta bo’lgunicha davom etishi kerak. Buning uchun yana bitta sikl tashkil etish kerak, u raqamlar yig’indisini hisoblovchi siklga nisbatan tashqi sikl hisoblanadi.
Bitta nozik xususiyat! Har doim raqamlar yig’indisini hisoblovchi ichki siklni bajargandan so’ng, ushbu yig’indi qiymatini boshlang’ich son saqlanadigan o’zgaruvchiga berish kerak, ya’ni sonni o’zining yig’indisi bilan almashtirish, shartni tekshirish (yig’indi 10 dan kichkinami yoki kichkina emasmi), agar shart bajarilmasa  siklni yangi son - yig’indi bilan davom ettirish kerak. Yig’indi saqlangan o’zgaruvchini esa, har doim nolga tenglab  turishni esdan chiqarmaslik kerak.
Shunday qilib, agar kiritilgan son n o’zgaruvchiga, uning raqamlari yig’indisi esa s o’zgaruvchiga yozilgan bo’lsa, raqamlar yig’indisini hisoblagandan so’ng,     n o’zgaruvchi s qiymat olish (n:= s), (n < 10) sharti tekshirilishi kerak, agar u hali bajarilmayotgan bo’lsa, s o’zgaruvchi nolga tenglansin (s:= 0) va raqamlar yig’indisini hisoblash sikli davom ettirilsin.
Yig’indining qiymatini tekshirish bo’yicha tashqi siklni repeat ... until             n < 10 operatorlari yordamida, raqamlar yi’g’indisini hisoblash bo’yicha ichki siklni esa while ... do operatorlari yordamida tashkil qilamiz.
Dastur

Program L22; { Sonning raqamli ildizi }
uses Crt;
var
n, a, s : integer;
begin
write('Natural sonni kiriting '); readln(n);
a := n;
repeat
s := 0;
while n <> 0 do
               begin
s := s + n mod 10; n := n div 10
    end;
n := s
until n < 10;
writeln(a,  'ning raqamli ildizi =’, n)
end.

23-misol. Shunday uch xonali son topingki, uni 11 ga bo’lganda bo’linma uning raqamlari yig’indisiga teng bo’lsin.

Program L23;
uses Crt;
var
a, n, p, s : integer;
begin
a := 100;
writeln(' 11 ga bo’lganda bo’linma uning raqamlari yig’indisiga teng ’);
write(‘bo’lgan uch xonali son ');
repeat
n := a; s := 0;
repeat
p := n mod 10;
s := s + p*p;
n := n div 10
until n = 0;
if (a mod 11 = 0) and (s = a div 11) then write(a, '; ');
a := a + 1
until a = 1000;
end.

24- misol. n soning barcha bo’luvchilarini aniqlovchi dastur tuzilsin.

Bunday masala berilganda talabalar ko’pincha quyidagi yechish usulini taklif etishadi.
1 dan to n gacha bo’lgan barcha natural sonlarni ko’rib chiqish kerak, agar ulardan birontasi n soninig bo’luvchisi bo’lsa, uni ekranga chiqarish kerak. Masalan 36 soni uchun tekshirish maqsadida 1, 2, 3, ..., 36 sonlarini olamiz va ulardan 36 ning bo’luvchilarini tanlab olamiz. Bo’luvchilar quyidagilardir: 1, 2, 3, 4, 6, 9, 12, 18 va 36.
Bunday usuldan foydalanish mumkin. Lekin, diqqat bilan 36 ning bo’luvchilariga qarab chiqsangiz, bularning barchasi 1 dan to 18 gacha,  ya’ni 36 ning yarmigacha bo’lgan oraliqda joylashganligini ko’rasiz, faqatgina oxirgi bo’luvchi - sonning o’zidir. 
Mantiqan o’ylaganda ham, shunga amin bo’lamizki, bo’luvchilar aynan: 1 dan n/2 gacha bo’lgan oraliqda joylashadi.  
Agar sonning yarmidan ham katta bo’luvchi bor degan fikr tug’ilsa, uni 2 ga ko’paytirib berilgan sondan katta son hosil qilamiz.
Shunday qilib, sonning o’zidan tashqari barcha bo’luvchilari 1 dan n/2 gacha bo’lgan oraliqda joylashishi ayon bo’ladi, demak sonning bo’luvchilarini aynan shu oraliqdan tekshirish kerak. 
Bu yerdan dasturni tuzish rejasi kelib chiqadi: 1 dan n/2 gacha bo’lgan sikl tashkil etish; agar nson ushbu oraliqdagi biror-bir songa bo’linsa, u holda ushbu bo’luvchi ekranga chiqarilsin; sikl davom ettirilsin; ekranga sonning o’zi chiqarilsin. 
Dastur

Program L24; {Sodda algoritm. 1 - usul }
uses Crt;
var
n, d : integer;
begin
write('Butun sonni kiriting '); readln(n);
d := 1;
writeln(n, 'soning bo’luvchilari ');
repeat
if n mod d = 0 then write(d, ' ');
d := d + 1
until d > n div 2;
write(n)
end.

Lekin bu masalani yechishda ham mashinaga yordam bersa va uning ishini yengillashtirsa bo’ladi. Bu yerda yordamga yana matematika keladi.
n soning bo’luvchilarini topish uchun sqrt(n) dan katta bo’lmagan bo’luvchilarni topish yetarli ekan.
Qolgan barcha bo’luvchilar n ni topilgan bo’luvchilarga bo’lganda hosil bo’ladi.
Masalan, agar n=30 bo’lsa, u holda faqatgina 1, 2, 3, 5 (30 dan chiqadigan natural kvadrat ildizdan katta bo’lmagan son 5 ga teng) bo’luvchilarni topish yetarli, qolgan bo’luvchilarni esa 30 ni hosil bo’lgan sonlarga bo’lish orqali hosil qilsa bo’ladi:
30 div 1 = 30;
30 div 2 = 15;
30 div 3 = 10;
30 div 5 = 6.
Dasturni tuzishda muammo chiqib qoladi - butun sonlar to’plamida kvadrat ildizni chiqarish funksiyasi yo’q. Bu to’siqni yengib o’tish oson. Qanday qilib deysizmi? Buning uchun d ning 1 dan d*d<n gacha bo’lgan bo’luvchilarini tanlash siklini tashkil etish, agar kvadrat ildiz butun sondan iborat bo’lsa, bu holni asosiy sikl tugatilgandan so’ng alohida ko’rib chiqish kerak.
Nima uchun bunday qilish kerak? Bu 36 soni uchun keltirilgan misolda ravshan bo’ladi. sqrt(36)= 6,  dxd < 6 bo’lganicha-sikli;
d = 1, dxd = 1x1 = 1 < 36 (rost),
sikl davom etadi;
qoldiq topiladi: 36 mod 1 = 0; 1 va 36 ni 1 ga bo’lgandagi butun son ekranga chiqariladi, 36 div 1 =36;
d = 2, dxd = 2x2 = 4 < 36 (rost),
sikl davom etadi;
36 mod 2 = 0;
2 va 36 ni 2 ga bo’lgandagi butun son ekranga chiqariladi, 36 div 2 = 18;
d = 3, dxd = 3x3 = 9 < 36 (rost),
sikl davom etadi;
36 mod 3 = 0;
3 va 36 ni 3 ga bo’lgandagi butun son ekranga chiqariladi, 36 div 3 = 12;
d = 4, dxd = 4x4 = 16 < 36 (rost),
sikl davom etadi;
36 mod 4 =0;
4 va 36 div 4 = 9 ekranga chiqariladi;
d = 5, dxd = 5x5 = 25 < 36 (rost),
sikl davom etadi;
36 mod 5 <>0, ekranga hech narsa chiqarilmaydi,
sikl davom etadi;
d = 6, dxd = 6x6 = 36 < 36 (yolg’on), sikl tugatiladi.
d = 6 (dxd = n), 6x6 = 36 tekshiriladi  (rost), 6 ekranga chiqariladi.
Agar sikl dxd <= n bo’lguncha davom etganda, u holda d = 6 da ekranga 6 va  36 div 6 = 6 chiqarilar edi, ya’ni ikkita olti, bu esa xato bo’lar edi

Dastur
Program L24a;    {Sonning bo’luvchilari. 2 -usul }
uses Crt;
var
n, d : integer;
begin
write('Butun sonni kiriting '); readln(n);
writeln(n, ‘sonining bo’luvchilari’);
d := 1;
while d*d < n do
begin
if n mod d=0 then write(d, ' ', n div d, ' ');
d := d + 1
end;
if d*d = n then write(d);  writeln
end.

 25-misol. a va b sonlarining EKUB ini toping.

Ikkita sonning EKUB ini topish masalasi barcha o’quv qo’llanmalarida shunchalik aniq tushuntirilganki, EKUB ni topish algoritmini tuzishda biron bir yangilik kiritish juda qiyin.
Lekin, ko’plab qo’llanmalarda EKUB ning Evklid algoritmi yordamida topilishi ko’rsatilgan.
Lekin biz bu masalaga tabiiyroq yondashamiz.
Shunday qilib, biz Evklid algoritmini bilmaymiz deb faraz qilaylik. U holda, matematikaning elementar tushunchalari va oddiy mantiqiy mulohazalar yordamida sonlarning eng katta umumiy bo’luvchisini topamiz va dastur tuzamiz.
Avvalambor, ikki sonning EKUBi deb nimaga aytilishini aniq tushunib olaylik. Masalan, 36 va 45 ning uchta umumiy bo’luvchisi: 1,3,9 mavjud. Ularning orasida eng kattasi 9. Demak 36 va 45 sonlari uchun EKUB 9 sonidir.
30 va 45 ning biroz ko’proq umumiy bo’luvchilari bor: 1,3,5 va 15. Eng kattasi 15, demak EKUB(30, 45)=15. 

U holda, mantiqan o’ylab qaralsa, EKUB ni topishning quyidagi usuli paydo bo’ladi.
Birinchidan, sonlarning biri ikkinchiga bo’linish yoki bo’linmasligi tekshirilishi kerak, agar bo’linsa, u holda bo’lingani eng katta umumiy bo’luvchi bo’ladi. Masalan, 45 va 15 uchun EKUB 15 sonidir. Agar ulardan biri ikkinchisiga  bo’linmasa, u holda ketma-ket ravishda 1 dan to a va b sonlarining kichigigacha bo’lgan natural sonlarni olib, ulardan qaysi biriga ikkala son ham bo’linishini tekshiramiz, umumiy bo’luvchilarning oxirgisi eng kattasi bo’ladi. 
36 va 45 uchun bunday jarayon quyidagi ko’rinishda bo’ladi:
a ni b ga va  b ni a ga bo’linishini tekshiramiz;
1 ga bo’lgandagi qoldiqni topamiz, 36 mod 1= 0, 45 mod 1 = 0, demak 1 – umumy bo’luvchi;
2 ga, 36 mod 2 = 0, 45 mod 2 <>0, 2 umumiy bo’luvchi emas;
3 ga, 36 mod 3 = 0, 45 mod 3 = 0, 3 – umumiy bo’luvchi;
4 ga, .................................................. va hokazo 36 gacha.
Umumiy bo’luvchilarning oxirgisi 9 soni bo’lib, u EKUB dir.
Bunday oson algoritm bo’yicha dastur tuzish qiyin emas.

Program L25;
uses Crt;
var
a, b, n, k, i : integer;
begin
write('Birinchi sonni kiriting'); readln(a);
write('Ikkinchi sonni kiriting '); readln(b);
if a mod b = 0
then n := b
else
if b mod a = 0
then n := a
else
begin
if a > b then i := b else i := a;
k := 1;
while k < i do
begin
if (a mod k = 0) and (b mod k = 0) then n := k;
k := k + 1
end
end;
writeln( a,' va ', b, 'sonlarining EKUBi= ', n)
end.

Lekin kompyuter ushbu dastur bo’yicha ishlayotganida qancha foydasiz ishlarni qilayotganini o’ylab ko’ring!
Masalan, 36 va 45 sonlari uchun sikl 36 marta bajariladi. Bulardan “sof” foydasizlari yoki “bo’sh” lari 27 ta, chunki EKUB 9 ga teng, 9 dan 36 gacha esa- foydasiz ish.  

EKUB ni aniqlashda boshqa yo’lni tanlash mumkinmi degan savol tug’ilishi tabiiy. Masalani “boshqa tomondan” ko’rib chiqsak, ya’ni eng kichik sonni topib uni 1 ga kamaytirib, har doim hosil bo’lgan son bo’luvchimi yoki bo’luvchi emasligini tekshirish kerak.
Bunday bo’luvchi topilishi bilan, sikl tugatiladi, ushbu bo’luvchi esa eng katta bo’ladi, shunday qilib foydasiz sikllar soni kamayadi.
Masalan, 36 va 45 sonlari uchun sikl 36 marta emas 27 marta bajariladi:
36, 35, 34, 33, 32, 31, ..., 9.

Algoritm

Kiritilgan sonlardan eng kichigini tanlaymiz; sonlarning kichigini 1 ga kamaytirish bilan birga u sonlarning umumiy bo’luvchisi yoki bo’luvchisi emasligini tekshiradigan sikl boshlanadi; bo’luvchi topilishi bilan sikl tugatiladi; ekranga topilgan bo’luvchi chiqariladi, u ham bo’lsa EKUB hisoblanadi.

Algoritm bo’yicha dastur tuzamiz:

Program L25b; 
uses Crt;
var
a, b, n, k : integer;
begin
write('Birinchi sonni kiriting '); readln(a);
write('Ikkinchi sonni kiriting '); readln(b);
if a > b then k := b else k := a;
n := k + 1;
repeat
n := n - 1
until (a mod n = 0) and (b mod n = 0) ;
writeln(a,' va ', b, 'sonlarining EKUBi= ', n)
end.

Dasturning bunday ko’rinishida bir sonning boshqasiga bo’linishini tekshirish kerak emas (nima uchunligini tushuntiring?).  
Albatta bunday dasturlarni takomillashtirish, kompyuter uchun soddalashtirish mumkin (o’zingiz qilib ko’ring), lekin baribir biz matematikada bebaho bo’lgan  Evklid algoritmlariga murojaat qilishimizga to’g’ri keladi.
Ular nafaqat matematik o’zgachaligi, balki soddaligi bilan ham farq qiladilar. Hamma daho soddadir! 
Shunday qilib, EKUBni topishning  birinchi Evklid algoritmi quyidagidan iborat. Masalan, 36 va 45 sonlarining EKUB ini topish kerak bo’lsin.
Katta sondan kichigini ayiramiz: 45-36=9,
berilgan sonlarning kattasini ayirma bilan almashtirib, ikkita boshqa son hosil qilamiz:
9 va 36;
yana bir marta kattadan kichigini ayiramiz: 36-9=27,
kattasini ayirma bilan almashtirib 9 va 27 larni hosil qilamiz; kattasidan kichigini ayiramiz:
27 - 9 = 18,
kattasini ayirma bilan almashtirib 9 va 18 larni hosil qilamiz; kattasidan kichigini ayiramiz:
18 - 9 = 9,
kattasini ayirma bilan almashtirib 9 va 9 larni hosil qilamiz.
Ikkita bir xil son hosil bo’ldi, demak 45 va 36 larning EKUBi 9 ga teng.

Ushbu Evklid algoritmi qat’iy matematik isbotga ega bo’lib hech qanday shubha uyg’otishi mumkin emas.

 

Dastur
Program L25c;
uses Crt;
var
a, b, c, a1, b1 : integer;
begin
write('Birinchi sonni kiriting '); readln(a);
write('Ikkinchi sonni kiriting '); readln(b);
a1 := a; b1 := b;
while a <> b do
begin
if a > b then a := a - b else b := b - a
end;
writeln(a1,' va ', b1, 'sonlarining EKUBi= ', a)
end.

Bu dasturda “gacha” sikli emas, “bo’lguncha” sikli ishlatilgan. Nima uchun deb o’ylaysiz? Bu savolga javob berish uchun, " bo’lguncha" siklini "... gacha " sikliga, ya’ni  while ... do operatorlarini  repeat ... until ...  operatorlariga almashtirib ko’ring. Sikl quyidagi ko’rinishga kiradi:

                                    repeat
if a > b then a := a - b else b := b - a
until a = b;

Bu yerdan sizga ma’lum bo’ldiki, repeat sikli albatta aqalli bir marotaba bajarilmoqda. Agar siz ikkita bir xil son kiritsangiz, dastur "qotib qoladi". Haqiqatdan ham, a> b sharti bajarilmayapti, demak b:=b-a operatori bajariladi. b 0 qiymat qabul qiladi, sikl qaytariladi, a>b shart bajariladi, a a:=a-0 qiymat qabul qiladi, ya’ni a ning qiymati o’zgarmaydi, a=b tenglik hech qachon bajarilmaydi va “dastur qotib qoladi” bu degani sikl “ cheksiz ko’p marta” davom etadi.
Agarda  while a <> b do ... sikli qo’llanilsa, o’zaro teng a va b (a=b) sonlar kiritilgan taqdirda ham sikl qotib qolmaydi, aksincha u biron marta ham bajarilmaydi va EKUB o’zaro teng sonlardan bittasining qiymatini qabul qiladi.
EKUBni topishning  ikkinchi  Evklid algoritmi ham bor.  
a va b- natural sonlar bo’lsin, b<>0 va r- a ni b ga bo’lgandagi qoldig’i. U holda EKUB(a, b) = EKUB(r, b).
Isbot tariqasida eng katta umumiy bo’luvchining yaqqol xossasi qo’llaniladi: d soni quyidagi hollarda a va b sonlarining eng katta umumiy bo’luvchisi bo’ladi: 
1) d - a va b ni bo’ladi, ya’ni a va b ning umumiy bo’luvchisi bo’ladi;
2) a va b ning ixtiyoriy umumiy bo’luvchisiga bo’linadi. 
a >= b >= 0 va  a > 0 bo’lsin. U holda Evklid algoritmi quyidagcha qo’llanadi: agar  b = 0, u holda EKUB (a, b) = a. Aks holda a ni b ga bo’lgandagi qoldiqqa teng r ni hisoblab topamiz va EKUB (a,b) ni topish masalasini EKUB (r,b) ni topish masalasi bilan almashtiramiz. r<0 da bu jarayonni davom ettirish mumkin. Quyidagilarga ega bo’lamiz: b > r > r1 > r2 > r3 >, ..., lekin b, r, r1, r2, r3 – musbat butun sonlar bo’lgani uchun, rn = 0 bo’lgan n topiladi. Aytib o’tilgan fikrga mos ravishda
EKUB(a, b) = EKUB(b, r) = EKUB(r1, r) = ... = EKUB(rn-1, 0) = rn-1.
Amaliy jihatdan bu quyidagi ko’rinishga ega.  888  va  351 sonlarining EKUB ini topish kerak.  
Bularning kattasi 888, a = 888, b = 351.
a ni b ga bo’lgandagi  qoldiqni topamiz: 888 mod 351 = 186,
r = 186;
a ni b bilan va b ni r qoldiq bilan almashtiramiz: a = 351, b = 186;
yana bir marta a ni b ga bo’lgandagi  qoldiqni topamiz:
351 mod 186 = 165, r = 165;
a ni b bilan va b ni r qoldiq bilan almashtiramiz: a = 186, b = 165;
a ni b ga bo’lgandagi  qoldiqni topamiz: 186 mod 165 = 21,
r = 21;
a ni b bilan va b ni r qoldiq bilan almashtiramiz: a = 165, b = 21;
a ni b ga bo’lgandagi  qoldiqni topamiz; 165 mod 21 = 18,
r = 18;
a ni b bilan va b ni r qoldiq bilan almashtiramiz: a = 21, b = 18;
a ni b ga bo’lgandagi  qoldiqni topamiz; 21 mod 18 = 3, r = 3;
a ni b bilan va b ni r qoldiq bilan almashtiramiz: a = 18, b = 3;
a ni b ga bo’lgandagi  qoldiqni topamiz: 18 mod 3 = 0, r = 0;
a ni b bilan va b ni r qoldiq bilan almashtiramiz: a = 3, b = 0.
b nolga teng bo’lishi bilan, sikl tugatiladi, a ning qiymati chiqariladi, aynan u eng katta umumiy bo’luvchi bo’ladi, EKUB(888, 351) = a = 3.
Ushbu jarayonni umumlashtirilgan  quyidagi zanjir ko’rinishida tasvirlash mumkin:
EKUB(888, 351) = EKUB(351, 186) = EKUB(186, 165) =
= EKUB(165, 21) = EKUB(21, 18) = EKUB(18, 3) = EKUB(3,  0) = 3.

Chuqur tahlilsiz ham ravshanki, bu algoritm bizni natijaga tezroq olib keladi va keragi yo’q buyruqlarsiz bajariladi, ya’ni, kompyuterni bekor ishlashga majbur qilmaydi. 

 

 

Dastur

Program L25d; { 2 – usul. Evklid algoritmi }
uses Crt;
var
        a, b, r, a1, b1 : integer;
begin
write('Birinchi sonni kiriting '); readln(a);
write('0 ga teng bo’lmagan ikkinchi sonni kiriting’);
readln(b);
a1 := a; b1 := b;
repeat
r := a mod b;
a := b; b := r
until b = 0;
writeln(a1,' va ', b1, 'sonlarining EKUBi= ', a)
end.

 

26-misol. Ikki sonning eng kichik umumiy karralisini (EKUK) kamida ikkita usul bilan topuvchi dastur tuzing.

Eslatma
a va b sonlarining eng kichik umumiy karralisi, EKUK(a, b) deb a ga ham b ga ham bo’linadigan eng kichik songa aytiladi.
Masalan, 18 va 27 sonlari uchun eng kichik umumiy karrali 54. U 18 ga ham 27 ga ham qoldiqsiz bo’linadi. Ushbu sonlar uchun umumiy karralilar cheksiz ko’p bo’lsada: 54, 108, 162, 216, ..., lekin, 54 ular ichida eng kichigidir.

Yo’nalish
1. Birinchi dasturni tuzish g’oyasi yoki boshqacha qilib aytganda birinchi algoritm g’oyasi quyidagidan iborat:
Sonlarning kattasini olamiz, agar u kichigiga bo’linsa, u holda u eng kichik umumiy karrali hisoblanadi, aks holda, sonlarning kattasi ikkiga ko’paytirilib, ya’ni unga yana o’zi qo’shilib, yangi son kichigiga bo’linish yoki bo’linmasligi tekshiriladi, agar bo’linsa, u holda u EKUK hisoblanadi, bo’linmasa, huddi shu songa oshiriladi, ya’ni boshida ikkita sonning ichida kattasi bo’lgan son 3 ga ko’paytiriladi va h.k.
Masalan, 10 va 36 sonlari uchun ushbu jarayon quyidagi ko’rinishda bo’ladi: 36 sonlar ichida kattasi, 36 mod 10 <>0, ya’ni 36 10 ga bo’linmaydi; 36 ni 36 ga oshiramiz: 36+36=72 tekshiramiz: 72 mod 10 <> 0; 72 ni yana 36 ga oshiramiz: 72+36=108 tekshiramiz: 108 mod 10 <> 0; 36 ga oshiramiz: 108+36=144kshiramiz:  144 mod 10 <> 0; oshiramiz: 144+36=180  tekshiramiz: 180 mod 10=0, 180 10 ga bo’linadi, demak 180 10 va 36 ning eng kichik umumiy karralisi hisoblanadi, EKUK(10, 36) = 180.

2. Ikkinchi algoritmning g’oyasi quyidagi matematik formulaga asoslanadi: axb = EKUK(a, b) xEKUB(a, b).

Program L26; { Ikki sonning EKUK i. 1 – usul }
uses Crt;
var
a, b, m, n, p : integer;
begin
write('Birinchi sonni kiriting '); readln(a);
write('Ikkinchi sonni kiriting '); readln(b);
p := 0;
repeat
if a>b then
begin
m := a; n := b
end
 else
                          begin
m := b; n := a
end;
p := p + m
until p mod n =0;
writeln(a,' va ', b, 'sonlarining EKUKi= ', p)
end.

27-misol. Berilgan n soni tub son bo’lishini tekshiruvchi dastur tuzing. Faqatgina 2 ta bo’luvchiga - 1 va o’ziga ega bo’lgan  natural songa tub son deyiladi. Shuni qayd etish kerakki, 1 soni tub songa kirmaydi, chunki uning faqatgina bitta bo’luvchisi - o’zi bor.
1 dan farqli va tub bo’lmagan sonlar murakkab sonlar deyiladi.  
Shunday qilib 1 soni na tu

2946 marta o`qildi.

Foydalanuvchi ismi: 101-g/ Ergashev Safarali
Qo`shilgan sana: 2015-04-08

yaxshi

Foydalanuvchi ismi: 101-Humoyiddin
Qo`shilgan sana: 2015-04-08

yaxshi

Foydalanuvchi ismi: 101-g/ Ergashev Safarali
Qo`shilgan sana: 2015-04-08

yaxshi

Foydalanuvchi ismi: 101 sayitov
Qo`shilgan sana: 2015-04-09

yaxshi

Foydalanuvchi ismi: 101 sayitov
Qo`shilgan sana: 2015-04-09

yaxshi

Foydalanuvchi ismi: rivoj 203
Qo`shilgan sana: 2015-04-16

ajoyib

Foydalanuvchi ismi: 203-Botirov Ilhom
Qo`shilgan sana: 2015-04-17

123456789

Foydalanuvchi ismi: zilola
Qo`shilgan sana: 2015-04-25

ajoib.zur

Foydalanuvchi ismi: said
Qo`shilgan sana: 2015-10-19

raxmat

Foydalanuvchi ismi: Jamshid
Qo`shilgan sana: 2016-01-16

Raxmat ustoz

Parol:
Eslab qolish.


Ro`yhatdan o`tish

testing

+998915878681

Siz o`z maxsulotingizni 3D reklama ko`rinishda bo`lishini xohlaysizmi? Unda xamkorlik qilamiz.

3D Reklama

testing

masalalar.zn.uz/

Turli xil mavzuda, internet mavzular, faqat masalalar.zn.uz saytda.


Рейтинг@Mail.ru
Рейтинг@Mail.ru

Besucherzahler
счетчик посещений