HomeChia sẻ

Thuật toán tìm ƯCLN minh họa trong Pascal và Scratch

Like Tweet Pin it Share Share Email
Like và share giúp mình phát triển website nhé.
  •  
  •  

Thuật toán tìm ƯCLN là thuật toán số học tiếp theo mà mình lựa chọn giới thiệu trong Blog này, mình sẽ lại tiếp tục minh họa trong Free Pascal và Scratch để các bạn cùng tham khảo.

Chắc có lẽ không cần phải nhắc lại khái niệm về ƯCLN (Ước chung lớn nhất) mình sẽ đi ngay vào vấn đề chính.

Có nhiều thuật toán tìm ƯCLN, ở đây mình đưa ra thuật toán tối ưu hơn cả, thuật toán như sau:

Thuật toán tìm ƯCLN(a,b)

Thuật toán được xây dựng dựa trên kiến thức ƯCLN(a,b) = ƯCLN(a,r) với r là số dư khi chia a cho b, nội dung thuật toán viết theo tiếng việt như sau:

Lặp lại cho đến khi nào b = 0 các thao tác sau;

r = phần dư của của a chia cho b

a=b;

b=r

Kết thúc vỏng lặp thì a chính là ƯCLN(a,b)

Chương trình tìm ƯCLN(a,b) minh họa bằng Pascal

 

Dữ liệu vào file: UCLN.inp Dữ liệu ra file: UCLN.out
Chứa 2 số a, b cách nhau

VD: 12345   1

ƯCLN(a,b)

1

Code Pascal


Chương trình trên giúp tìm ƯCLN của hai số nguyên, nếu đầu bài yêu cầu tìm ƯCLN của hai số tự nhiên thì các bạn có thể bỏ hai dòng lệnh a:=abs(a) (thế a bằng giá trị tuyệt đối của a) và b:=abs(b) đi

Chương trình tìm ƯCLN(a,b) minh họa bằng Scratch

(Phía dưới có file Word hướng dẫn)

Vì trong khi thực hiện chương trình 2 biến a, b thay đổi, vì vậy muốn lưu lại giá trị của hai biến này để cuối cùng xuất ra kết quả mình dùng hai biến lưu a và lưu b, Còn cách viết thuật toán thì không có gì thay đổi cả, còn dễ hơn Pascal phải không các bạn.

Hãy xem chương trình mình viết minh họa

Mở rộng bài toán

Viết chương trình tìm ƯCLN (a,b,c) (a,b,c< 2 tỉ) (dùng chương trình con)

Dữ liệu vào file: UCLN_3.inp Dữ liệu ra file: UCLN_3.out
Chứa 3 số a, b, c cách nhau

VD: 12345   1   23

ƯCLN(a,b,c)

1

Các bạn hãy sử dụng Pascal và Scratch để giải quyết bài toán trên xem thế nào nhé.

Đã có UCLN thì nên đón đọc: Tìm BCNN trong Pascal và Scratch nhé

File Word hướng dẫn

Comments (0)

Trả lời

Your email address will not be published. Required fields are marked *