Tìm BCNN bằng đệ quy ?

[tun_tun]

Cho 2 số a và b . Viết hàm tìm đệ quy BCNN của a và b.
Với bài trên thì em viết được nếu thêm 1 biến phụ là c chẳng hạn.
Nhưng đề bài bắt yêu cầu không dùng biến phụ và viết theo mẫu
int BCNN (int a , int b)
{
....
}

Còn cách tìm bội chung nhỏ nhất của 2 số
Ví dụ : Cho số 4 và số 5
Ta lấy số lớn hơn là 5 + 5 = 10
Nếu chưa mod hết cho 4 thì tiếp tục +
10 + 5 = 15 ( vẫn chưa được )
15 + 5 = 20 (được rồi ^_^) thì kết quả là 20
Mong các anh chị giải đáp cho em !

[Ada]

Bài này theo mình nghĩ có thể đưa về giải bằng UCLN

BCNN(a,b) = a*b / UCLN(a,b)
UCLN(a,b) = UCLN(b,a)
UCLN(a,b) = b nếu a = 0
UCLN(a,b) = UCLN(a, a%b) nếu a > b

[tun_tun]

Bài này theo mình nghĩ có thể đưa về giải bằng UCLN

BCNN(a,b) = a*b / UCLN(a,b)
UCLN(a,b) = UCLN(b,a)
UCLN(a,b) = b nếu a = 0
UCLN(a,b) = UCLN(a, a%b) nếu a > b

Cách trên mình biết rồi nhưng ở đây là áp dụng cách mình nêu ví dụ ở trên

[sieuphuong]

Còn cách tìm bội chung nhỏ nhất của 2 số
Ví dụ : Cho số 4 và số 5
Ta lấy số lớn hơn là 5 + 5 = 10
Nếu chưa mod hết cho 4 thì tiếp tục +
10 + 5 = 15 ( vẫn chưa được )
15 + 5 = 20 (được rồi ^_^) thì kết quả là 20
Mong các anh chị giải đáp cho em !

Nếu vậy thì bạn viết đệ quy như sau:

int BCNN(int a,int b){ static int i=1;  if(a<b) {   if(b%a==0) return b;  else {         i++;         BCNN(a,b*i);        } } else {  if(a%b==0) return a;  else {         i++;         BCNN(a*i,b);        }   }}}

[tun_tun]

Nếu vậy thì bạn viết đệ quy như sau:

int BCNN(int a,int b){ static int i=1;  if(a<b) {   if(b%a==0) return b;  else {         i++;         BCNN(a,b*i);        } } else {  if(a%b==0) return a;  else {         i++;         BCNN(a*i,b);        }   }}}

Sai rồi anh ơi ,anh có thể kiểm tra lại , anh có thể viết mà không cần dùng thêm biến phụ không ?

[kidkid]

int BCNN(int a,int b)
{
   if(b%a == 0) return b;
   return BCNN(a,b*2);
} 

được chưa Tủn ?

# Hix. Viết chưa tối ưu lắm. Ku Tủn coi lại và sửa thử xem sao ? Ý của cậu mà.

[Forlorn_hope]

int BCNN(int a,int b)
{
   if(b%a == 0) return b;
   return BCNN(a,b*2);
} 

được chưa Tủn ?

# Hix. Viết chưa tối ưu lắm. Ku Tủn coi lại và sửa thử xem sao ? Ý của cậu mà.

nếu thế thì kidkid chạy tay thế này thử đúng ko?
-a=3,b=4;
-qua hàm, b>a -> gọi hàm với a=3,b=8
- 8%3-> chưa đúng, gọi tiếp hàm với a=3, b=16;
-> sai rùi, b=12 mới chính xác.
Hihihihi, bài này có lẽ hơi căng đó kidkid

[kidkid]

Không cho dùng biến tạm. SH có ý gì ko ?

Tớ có ý thế này, bằng cách tùy biến các con số, tuy ko hay nhưng tạm giải quyết được cái đã (Hết tiền net rồi nè ..)

Bây giờ, cũng hàm trên, nhưng a,b không phải là a,b như người ta nhập nữa. VD:
a=3,b=4 thì :
Main: Kiểm tra a,b thỏa đk chưa nếu chưa : a = a*(b+b) + b, b = b+b; sau đó gọi BCNN(int,int)
lúc này: a/b = a (ban đầu), a%b = b (ban đầu )

int BCNN(int a,int b) 
{ 
   int a1 = a/b; int b1 = a%b;
   if(b%(a1) == 0) return b; 
   else { a = a1*(b+b1) + b1; b = b+b1 ; return BCNN(a,b); }
} 

Test thử nhé:
a=3,b=4:
b%a != 0 -> a= 3*(4+4) + 4 =28, b= 8;
BCNN 1:
a1 = 28/8 = 3; b1 = 28%8 = 4;
b%a1 == 8%3 != 0;
a = a1*(b+b) + b1 = 3*(8+4) + 4 = 40; b = 8+4 = 12;
BCNN 2:
a1 = 40/12 = 3; b1 = 40%12 = 4;
b%a1 = 12%3 == 0 return b;

Hieubm nói là còn biến tạm, a1,và b1, cái này thì chưa hẳn, có thể viết lại thế này :

int BCNN(int a,int b) 
{ 
   //int a1 = a/b; int b1 = a%b;
   if(b%(a/b) == 0) return b; 
   else { a = (a/b)*(b+(a%b)) + a/b; b = b+a%b ; return BCNN(a,b); }
} 

Nhưng sợ các cậu ko hiểu thôi ?

Biếng thật, tí tôi về tôi viết thử? Hi vọng tối thảo luận tiếp. Chờ SH và ANIT

[tuonghuy]

/*chuong trinh tim BCNN cua hai so bang de quy*/

#include<stdio.h>#include<conio.h>#include<math.h>int UCLN(int a,int b);void main(){        int a,b;    printf("nhap vao 2 so a va b:\n");    scanf("%d%d",&a,&b);    printf("BCNN cua %d va %d la:%d",a,b,(a*b)/UCLN(a,b));    getch(); }int UCLN(int a,int b){        a=abs(a);b=abs(b);    if(b==0)        return a;    else        return UCLN(b,a%b);     }

Cách này được không bạn?

[kscntt_46]

Nhưng sợ các cậu ko hiểu thôi ?

else { a = (a/b)*(b+(a%b)) + a/b; b = b+a%b ; return BCNN(a,b);

Nhưng mình thấy bạn hướng dẫn nó có vẻ rất trừu tượng và code rất ngắn. Mình đang test bài theo ý tưởng của Kidkid rùi.
Ok ! Giờ em đã hiểu, cứ tưởng sai. Thuật toán lạ quá.