30/09/2018, 20:12

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

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
", divisor(a,b));
    return 0;
}
int divisor(int m, int n)
{
    if (m%n == 0)
        return n;
    return divisor(n,m%n);
}

vũ xuân quân viết 22:23 ngày 30/09/2018

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

Sáng Béo viết 22:20 ngày 30/09/2018

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

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.

Người bí ẩn viết 22:26 ngày 30/09/2018

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

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

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

Người bí ẩn viết 22:20 ngày 30/09/2018

Uhm, đúng đó bạ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

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

Sáng Béo viết 22:16 ngày 30/09/2018

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

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

‏ viết 22:28 ngày 30/09/2018

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

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

Người bí ẩn viết 22:21 ngày 30/09/2018

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

‏ viết 22:19 ngày 30/09/2018

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; }

viết 22:23 ngày 30/09/2018

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;

Người bí ẩn viết 22:21 ngày 30/09/2018

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

Cao Cảnh Linh viết 22:20 ngày 30/09/2018

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);
}

Người bí ẩn viết 22:20 ngày 30/09/2018

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

Kira viết 22:21 ngày 30/09/2018

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ư

rogp10 viết 22:21 ngày 30/09/2018

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.

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

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Người bí ẩn

0 chủ đề

0 bài viết

Tác giả nổi bật