Funksiyalar. Rekursiv funksiyalar

Ikkita a va b sonlari berilgan ularning EKUBini topuvchi dastur tuzing. EKUB inglizchada Greatest common divisor qisqacha gcd(a, b).

Masalan gcd(25, 20) = 5; gcd(60, 70)=10.

Evklid.

Eramizdan oldingi 325 yilda tug’ilgan. Grek

matematigi, geometriyaning otasi. Evklid

algoritmi eng qadmgi algoritmlardan biri.

Evklid algoritmi bo’yicha:

gcd(a, b) =

Masalan:

gcd(124, 36)

• a=124,b=36,b≠0. gcd(124,36)=gcd(36,124%36)=gcd(36, 16)
• a=36, b=16, b≠0. gcd(36, 16)=gcd(16, 36%16)=gcd(16, 4)
• a=16, b=4, b≠0. gcd(16, 4)=gcd(4, 16%4)=gcd(4, 0)
• a=4, b=0. gcd(4, 0) = 4;

Demak gcd(124, 36)=4.

 

Evklid algoritmining isboti.

a % b = a- *b;

g = gcd(a, b) bo’lsa, g soni a va b ga bo’linadi.

U holda a % b ham g ga qoldiqsiz bo’linadi. Demak gcd(b, a % b) g ga qoldiqsiz bo’linadi.

Bundan kelib chiqadiki a va b ning istalgan umumiy bo’luvchisi b va a%b ning ham bo’luvchisi bo’ladi.

 

int gcd(int a, int b) {

if (b==0)

return a;

return gcd(b, a % b);

}

Topshiriqlar

• Evklid algoritmini mustaql yozing.
• Ikkita sonning EKUK ini (inglizcha “lcm”-least common multiplier) topuvchi dastur tuzing.
• Butun sonlardan iborat massiv berilgan. Massiv elementlari qiymati [1..1,000,000,000] intervalda, massiv elementlari soni 1000 dan oshmaydi. Massiv elamentlarining EKUB ini topuvchi dastur tuzing.
• Butun sonlardan iborat massiv berilgan. Massiv elementlari qiymati [1..1000] intervalda, massiv elementlari soni 100 dan oshmaydi. Massiv elamentlarining EKUK ini topuvchi dastur tuzing. Kiruvchi ma’lumotlar shunday beriladiki bunda EKUK ning qiymati 9* dan oshmasligi kafolatlanadi.

 

5. Bir o’lchamli massiv ko’rinishida sonlar berilgan. Massiv elementlari [-1000…1000] oralida. Elementlari soni 24 dan oshmaydi. Bu sonlar o’rtasida ‘+’ va ‘-’ amallarini shunday qoyingki hosil bo’lgan ifodaning qiymati berilgan s soniga teng bo’lsin.

Masalan: Massiv elementlari soni 5 ta. a[1]=10, a[2]=15, a[3]=7, a[4]=6, a[5]=8 va s=0 bo’lsa u holda

Mumkin bo’lgan javoblardan bittasi: 10-15+7+6-8=0

Istalgan bitta variant topilsin.

E’tiboringiz uchun raxmat.

Savollar?