Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8824

Jo'natishlar soni: 714631

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1177


So'ngi izohlar

Evkilida algoritmi operatsiya (log max(a,b))

 

Evkilda algoritmi asosan sonlarni Eng Katta Umumiy Bolinuvchisi(EKUB) va Eng Kichik Umumiy Karralisi(EKUK) larni topishda ishlatiladi.

 

EKUB topish goyasi

EKUB ni ayirish orqali topish xam mumkin masalan:bizga 2 ta son berilgan (12,56)

Shu sonlar EKUB(12,56)=4 buni isbotlaymiz ayirish usuli orqali yani ayirish usulida berilgan 2 ta sonni xar safar kattasida kichigini ayiramiz bu jarayon 1 son nol bolguncha davom etiladi va nol bolmagan son javob boladi.

 

12 va 56

12 va 44

12 va 32

12 va 20

8 va 12

4 va 8

4 va 4

56-12=44

44-12=32

32-12=20

20-12=8

12-8=4

8-4=4

4-4=0

 

Bu misolda 4 va 4 teng qiymatli boldi demak EKUB(12,56)=4 ekan

Siz bu ayirish usuli orqali xam EKUB topib olishingiz mukin lekin bu usul optimal

usul emas yani biz xozir jadvalda bir xil opertsiyani bir necha bor ishlatdik buni qisqartirish mumkun 12 va 56 ni 8 va 12 kelguncha bir xil operatsiya bajariladi buni qisqartiramiz yani 56 ni 12 bolib qoldiq qismini olamiz (56 mod 12=8) natija 8 xosil boladi qarabsizki 8 va 12 xosil boladi buni yana davom ettirsak 12 mod 8=4 natija 4 va 8 xosil boladi 8 mod 4=0 natija 4 va 0 demak 4 ekan

 

56 va 12

12 va 8

8 va 4

4 va 0

56 mod 12=8

12 mod 8=4

8 mod 4=0

Javob 4 ekan

Korib turibsizki amallar soni kamaydi

Endi siz bu misoni realizatsiyasini korib chiqamiz.

 

Pascal tilida rekursiyasiz va rekursiyali

 

Rekursiyasiz

 

var

a,b,k:integer;

begin

read(a,b);

while(b<>0)do

begin

a:=a mod b;

k:=a;

a:=b;

b:=k;

end;

write(a)

end.

 

rekursiyali

 

function EKUB(a,b:integer):integer;

begin

if (b=0) then

EKUB:=a

else

EKUB:=EKUB(b,a mod b);

end;

var

x,y:integer;

begin

read(x,y);

write(EKUB(x,y));

end.

 

C++ tilda

 

 int gcd (int a, int b)
{
 if (b == 0)
 return a;
 else
 return gcd (b, a % b);
}
 
bu yerda rekursiyasiz
 
int gcd (int a, int b)
{
 while (b){
 a %= b;
 swap (a, b);
 }
 return a;
}
 

Endi esa JAVA tilidagi kodini korib chiqamiz.

 

import java.util.Scanner;

public class gcd {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int x=sc.nextInt();

int y=sc.nextInt();

System.out.println(ekub(x,y));

}

private static int ekub(int a, int b) {

return (b==0)?a:ekub(b,a%b);

} }

Endi sizlar bilan EKUK topishni korib chiqamiz.

Hammamiz bilamizki ekuk(a,b)=(a*b)/ekub(a,b); shundan kelib chiqib dastur quyidagicha boladi. Ekub topishni bilamiz shundan foydalanamiz

 

Pascal tilidagi kodi

 

function EKUB(a,b:integer):integer;

begin

If (b=0) then

EKUB:=a

else

EKUB:=EKUB(b,a mod b);

end;

var

x,y:integer;

begin

read(x,y);

write((x*y)/EKUB(x,y));

end.

 

Bilimingizni sinab korish uchun quyidagi misollarni yechib koring.

 

acmp.ru 0014,0085,0148

acm.tuit.uz 0019

algo.urgench-tuit.uz 206,207,208,209,269

va boshqa saytlar orqali

 

Ro`yxatga qaytish        Muallifi: Bahrom Sultonov