Môn Tin Học Lớp 10 viết thuật toán Tìm ước chung lớn nhất của 2 số nguyên dương a và b.

Question

Môn Tin Học Lớp 10 viết thuật toán Tìm ước chung lớn nhất của 2 số nguyên dương a và b. Giúp em bài này với ạ em cần gấp, đừng copy nguồn trên mạng nha. Em xin cảm ơn thầy cô và các bạn nhiều.

in progress 0
Lydia 2 giờ 2022-07-21T00:32:56+00:00 2 Answers 0 views 0

Trả lời ( )

    0
    2022-07-21T00:34:06+00:00

    Gửi bn:

    -Xác định bài toán

    +In: 2 số nguyen dương a và b

    +Out: ucln(a,b);

    -Xây dựng thuật toán

    +Bước 1: nhập 2 số nguyen dương a và b

    +Bước 2: nếu a>b thì a:=a-b

    +Bước 3: ngược lại thì b:=b-a

    +Bước 4: Nếu a<>b thì quay lại bước 2

    +Bước 5: ucln:=a;

    +Bước 6: Xuất ucln

    +Bước 7: Kết thúc

    chúc bn học tốt

    XIn hay nhất

    0
    2022-07-21T00:34:36+00:00

    ƯCLN của hai số có thể tìm được bằng việc phân tích hai số đó ra thừa số nguyên tố. Nhưng có 1 phương pháp tối ưu nhất là sử dụng thuật toán Euclid dựa trên dãy liên tiếp các phép chia có dư.

    Ví dụ: Tính ước số chung lớn nhất của 91 và 287.

    Trước hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:

    • 287 = 91*3 + 14 (91 & 14 sẽ được dùng cho vòng lặp kế)

    Nhận xét: bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 – 91*3 = 14. Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm ƯSCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia không còn số dư như sau:

    91 = 14*6 + 7 (14 & 7 sẽ được dùng cho vòng lặp kế)
    14 = 7*2 (không còn số dư, kết thúc, nhận 7 làm kết quả)
    Cuối cùng ta có: 7 = ƯSCLN(7,0) = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).

Leave an answer

Browse

14:7-5x6+12:4 = ? ( )