PHP Đề bài : viết chương trình tìm ước số chung lớn nhất [ USCLN ] và bội số chung nhỏ nhất [ BSCNN ] của hai số nguyên dương a và b. Định nghĩa USCLN của 2 số nguyên dương a và b là một số k lớn nhất, sao cho a và b đều chia hết cho k. BSCNN của 2 số nguyên ...
PHP
Đề bài: viết chương trình tìm ước số chung lớn nhất [USCLN] và bội số chung nhỏ nhất [BSCNN] của hai số nguyên dương a và b.
Định nghĩa
USCLN của 2 số nguyên dương a và b là một số k lớn nhất, sao cho a và b đều chia hết cho k.
BSCNN của 2 số nguyên dương a và b là một số h nhỏ nhất, sao cho h chia hết cho cả a và b.
Lời giải
Một phương pháp đơn giản đề tìm USCLN của a và b là duyệt từ số nhỏ hơn trong 2 số a và b cho đến 1, khi gặp số nào đó mà cả a và b đều chia hết cho nó thì đó chính là USCLN của a và b. Tuy vậy phương pháp này chưa phải là hiệu quả nhất.
Vào thế kỷ 3 TCN, nhà toán học Euclid [phiên âm tiếng Việt là Ơ-clit] đã phát minh ra một giải thuật tìm USCLN của hai số nguyên dương rất hiệu quả được gọi là giải thuật Euclid. Cụ thể về ý tưởng của bài toán, giả sử a lớn hơn b, khi đó việc tính UCSLN của a và b sẽ được đưa về bài toán tính USCLN của a mod b và b vì USCLN[a, b] = USCLN[a mod b, b].
Khi đã tìm được USCLN thì việc tìm BSCNN của hai số nguyên dương a và b khá đơn giản. Khi đó BSCNN[a, b] = [a * b] / UCSLN[a, b].
Tìm USCLN và BSCNN của 2 số a và b trong PHP
Ví dụ dưới đây sử dụng giải thuật Euclid để giải quyết bài toán tìm ước số chung lớn nhất [USCLN] và bội số chung nhỏ nhất [BSCNN] của hai số nguyên dương a và b.
File: uscln_bscnn.php
Kết quả:
USCLN của 15 và 40 là: 5 BSCNN của 15 và 40 là: 120
PHP
Viết chương trình PHP tìm ước số chung lớn nhất [USCLN] và bội số chung nhỏ nhất [BSCNN] của hai số nguyên dương a và b. Đề bài
Định nghĩa
USCLN của 2 số nguyên dương a và b là một số k lớn nhất, sao cho a và b đều chia hết cho k.
BSCNN của 2 số nguyên dương a và b là một số h nhỏ nhất, sao cho h chia hết cho cả a và b.
Lời giải
Một phương pháp đơn giản đề tìm USCLN của a và b là duyệt từ số nhỏ hơn trong 2 số a và b cho đến 1, khi gặp số nào đó mà cả a và b đều chia hết cho nó thì đó chính là USCLN của a và b. Tuy vậy phương pháp này chưa phải là hiệu quả nhất.
Vào thế kỷ 3 TCN, nhà toán học Euclid [phiên âm tiếng Việt là Ơ-clit] đã phát minh ra một giải thuật tìm USCLN của hai số nguyên dương rất hiệu quả được gọi là giải thuật Euclid. Cụ thể về ý tưởng của bài toán, giả sử a lớn hơn b, khi đó việc tính UCSLN của a và b sẽ được đưa về bài toán tính USCLN của a mod b và b vì USCLN[a, b] = USCLN[a mod b, b].
Khi đã tìm được USCLN thì việc tìm BSCNN của hai số nguyên dương a và b khá đơn giản. Khi đó BSCNN[a, b] = [a * b] / UCSLN[a, b].
Ví dụ dưới đây sử dụng giải thuật Euclid để giải quyết bài toán tìm ước số chung lớn nhất [USCLN] và bội số chung nhỏ nhất [BSCNN] của hai số nguyên dương a và b.
File: uscln_bscnn.php
Kết quả:
USCLN của 15 và 40 là: 5 BSCNN của 15 và 40 là: 120