Chương trình tìm ƯCLN của 2 số bằng thuật toán Euclid

#1

Xin chào. Hôm nay mình có viết code cho 1 đề bài như sau: : Viết chương trình tìm ƯCLN của 2 số nguyên dương a, b bằng thuật toán Euclide.
Cái đề bài này nằm trong chuyên đề Đệ Quy Nhị Phân.
Mà Đệ Quy Nhị Phân thì phải có 2 lời gọi hàm nhưng sao trong code mình chỉ có 1 lời gọi hàm? Nhưng code mình vẫn chạy bình thường, vẫn tìm được ƯCLN (các bạn có thể check lại cho chắc ăn!).
Dưới đây là code của mình, có gì sai sót thì các bạn góp ý và chỉnh sửa nhé!
Xin cảm ơn!

#include <stdio.h>
#include <stdlib.h>

int divisor(int m, int n);
int main()
{
    int a,b;
    printf("Type number 1: ");
    scanf("%d", &a);
    printf("Type number 2: ");
    scanf("%d", &b);
    printf("Result: %d\n", divisor(a,b));
    return 0;
}
int divisor(int m, int n)
{
    if (m%n == 0)
        return n;
    return divisor(n,m%n);
}
3 Likes
#2

Vi dụ mình nhập 2 số theo 2 cách:
91 287 và 287 91
thì mình nghĩ thuật toán này chạy không đúng rồi

3 Likes
#3

vẫn chạy giống nhau mà, nó chỉ thêm 1 lần đảo 287 với 91 là thành 91 với 287 ngay thôi.

2 Likes
#4

Sao mình nhập kiểu nào cũng đúng mà?

Pasted image779×473 69.9 KB

và đây là đảo ngược:

Pasted image779×473 133 KB

Bạn xem xét lại giùm mình nhé! Thanks!

1 Like
#5

Uhm, đúng đó bạn.

Bạn giúp mình trả lời câu này nhé! Dựa vào code ấy :smiley:

1 Like
#6

cái này mình cũng không rõ :cold_sweat:

#7

bài toán nằm lộn chuyên đề chứ còn gì nữa :joy:

sách sai là chuyện bình thường

2 Likes
#8

Thế à? :smiley: :smiley: :smiley: Thế bạn có thể viết 1 đoạn code theo cách khác không?

1 Like
#9

ko :joy:

nhưng viết thế này thì gọn hơn:

int gcd(int m, int n) { return m%n ? gcd(n, m%n) : n; }
#10

Dạng khác của thuật toán Euclid:

while(a!=b){
      if(a>b)
        a=a-b;
      else
        b=b-a;
}
return a;

Cách nữa là so sánh để tìm min trong 2 số rồi làm theo ý tưởng ước chung lớn nhất của 2 số không vượt quá min. Cho chạy từ min về 1 rồi kiểm tra 1 số mà a và b đều chia hết thì break vòng for rồi return.

int i, min;
if(a>b)
   min=b;
else
   min=a;
for(i=min; i>=1; i--){
    if((a%i==0)&&(b%i==0))
       break;
}
return i;
#11

Tks bạn nhiều nhé! Nhưng mình đang giải theo hướng đệ quy :smiley: :smiley:

1 Like
#12

Bài này quả thật có rất nhiều cách làm nhưng em thấy cách làm này khá là hay nhưng vẫn không hiểu lắm ạ. em cũng mới học lập trình. Mong anh(chị) chỉ bảo.
int xxx(int m, int n)
{
if (m%n == 0)
return n;
return xxx(n,m%n);
}

#13

Cái này áp dụng đệ quy + thuật toán Euclid tìm ƯCLN của 2 số (search GG sẽ rõ)
Còn mới học thì cứ từ từ đi bạn, đừng vội khi không hiểu :slight_smile:

#14

Thuật toán này vẫn đúng vì nó tìm số dư nên số nhỏ hơn chia ra vẫn có phần dư

#16

Cách này thì không nên bàn vì nó quá ẹ :smiley:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?