40. Rekursiv Bezu koeffitsientlari haqidagi masalani yechish uchun rekursiv triada ishlab chiqing? Ixtiyoriy n va m natural sonlar uchun Bezu koeffitsientlarini toping, ya’ni bu koeffitsientlar shunday a va b butun sonlar bo’lishi kerakki, EKUB(n,m)=a*n+b*m (bu yerda EKUB(n,m) –n va m butun sonlarning eng katta umumiy bo’luvchisi).
Parametrlarni aniqlash. m, n – berilgan natural sonlar, o’zgarmas parametrlar; d – berilgan sonlarning umumiy bo’luvchisi, o’zgarmas parametr; bm, bn – mos ravishda n va m lar uchun Bezu koeffitsientlari, bu parametrlar rekursiv tarzda funktsiyani navbatdagi chaqirishda o’zgaradi.
Rekursiya tayanchi. Agar berilgan parametrlar bilan funktsiyani navbatdagi chaqirishda d=m*bm–n*bn tenglik bajarilsa, u holda Bezu koeffitsientlari topilgan bo’ladi. Chiziqli kombinatsiya talab qilinadi.
Dekompozitsiya. Agar tenglik bajarilmasa, u holda (n yoki m) sonlardan kichik koeffitsientlarni inkrement ravishda oshirib boring. Rekusiv funktsiya keyingi chaqirishda alohida parametrlar to’plamining o’zgarishi bilan bajariladi. Buning uchun rekursiya tayanchi qayta tekshiriladi va rekursiv algoritm qayta takrorlanadi (yoki tayanchga erishiladi va funktsiya ishi yakunlanadi, yoki dekompozitsiyali o’tishlar bajariladi).
#include "stdafx.h"
#include using namespace std;
int nod(int m, int n);
void bezu(int d, int m, int n, int bm, int bn);
int _tmain(int argc, _TCHAR* argv[]) {
int x,y,del,buf;
printf("Bezu koeffitsientlarini topish masalasi");
printf("\nIkkita natural son kiriting:");
printf("\nX= "); scanf("%d",&x);
printf("Y= "); scanf("%d",&y);
if (x < y) { buf = x; x = y; y = buf; }
del=nod(x,y);
printf("\nChiziqli kombinatsiya:\n");
bezu(del,x,y,1,1); system("pause"); return 0; }
