THUẬT TOÁN TÌM ƯỚC CHUNG LỚN NHẤT VÀ BỘI CHUNG NHỎ NHẤT

Đề bài bác

Viết chương trình C tìm cầu số chung lớn nhất (USCLN) cùng bội số chung nhỏ tuổi nhất (BSCNN) của nhị số nguyên dương a cùng b.

*

Bạn đang xem: Thuật toán tìm ước chung lớn nhất và bội chung nhỏ nhất

Định nghĩa

USCLN của 2 số nguyên dương a với b là một số k béo nhất, sao để cho a cùng b hồ hết chia hết cho k.

BSCNN của 2 số nguyên dương a cùng b là một số h bé dại nhất, làm sao cho h phân tách hết cho cả a với b.

giải thuật

Một phương pháp đơn giản đề tra cứu USCLN của a cùng b là chú tâm từ số nhỏ hơn trong 2 số a và b cho tới 1, khi chạm chán số nào này mà cả a với b đa số chia hết mang lại nó thì đó đó là USCLN của a và b. Mặc dù vậy phương thức này chưa hẳn là kết quả nhất.

Vào chũm kỷ 3 TCN, đơn vị toán học tập Euclid (phiên âm tiếng Việt là Ơ-clit) đã phát minh sáng tạo ra một lời giải tìm USCLN của nhị số nguyên dương rất hiệu quả được hotline là giải thuật Euclid. Ví dụ về ý tưởng phát minh của bài xích toán, trả sử a to hơn b, khi đó việc tính UCSLN của a và b vẫn được mang đến bài toán tính USCLN của a hack b cùng b vày USCLN(a, b) = USCLN(a thủ thuật b, b).

khi đã kiếm được USCLN thì việc tìm BSCNN của hai số nguyên dương a cùng b khá solo giản. Khi ấy BSCNN(a, b) = (a * b) / UCSLN(a, b).


search USCLN và BSCNN của 2 số a với b vào C

Ví dụ tiếp sau đâ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ới bội số chung nhỏ tuổi nhất (BSCNN) của nhị số nguyên dương a và b.


/** * Chuong trinh tim uoc tầm thường lon nhat (USCLN) * va boi so bình thường nho nhat (BSCNN) cua 2 so a với b * *
author umakarahonpo.com */#include/** * Tim uoc so tầm thường lon nhat (USCLN) */int USCLN(int a, int b) if (b == 0) return a; return USCLN(b, a % b);/** * Tim boi so phổ biến nho nhat (BSCNN) */int BSCNN(int a, int b) return (a * b) / USCLN(a, b);/** * mê say main */int main() int a, b; printf("Nhap so nguyen duong a = "); scanf("%d", &a); printf("Nhap so nguyen duong b = "); scanf("%d", &b); // tinh USCLN cua a và b printf("USCLN cua %d va %d la: %d", a, b, USCLN(a, b)); // tinh BSCNN cua a với b printf("USCLN cua %d va %d la: %d", a, b, BSCNN(a, b));
Kết quả:


Nhap so nguyen duong a = 3Nhap so nguyen duong b = 4USCLN cua 3 va 4 la: 1USCLN cua 3 va 4 la: 12
Giải phương trình bậc 2 trong C
Liệt kê toàn bộ các số nguyên tố nhỏ hơn n
Recent Updates giải pháp xử lý duplicate vào SQLPhím tắt hay sử dụng trong ExcelBảo mật tập tin ExcelDịch trang tính trong ExcelIn trang tính trong ExcelHàm VLOOKUP trong ExcelĐối tượng giao diện trong ExcelSử dụng macro trong ExcelSử dụng Templates vào ExcelSử dụng chủ thể (theme) trong ExcelSử dụng Style trong ExcelXác thực tài liệu (Data Validation) trong Excel

Xem thêm: Văn Phòng Kinh Tế Văn Hóa Đài Bắc Tại Hà Nội, Văn Phòng Kinh Tế Và Văn Hóa Đài Bắc

umakarahonpo.com on facebook
học tập Lập Trình Online Miễn giá thành - umakarahonpo.com
Danh sách bài học kinh nghiệm
học java học tập servlet học jsp học Hibernate học tập Struts2 học Spring học SQL


câu hỏi phỏng vấn

201 câu hỏi phỏng vấn java 25 câu hỏi phỏng vấn servlet 75 thắc mắc phỏng vấn jsp 52 câu hỏi phỏng vấn Hibernate 70 câu hỏi phỏng vấn Spring 57 thắc mắc phỏng vấn SQL


About umakarahonpo.com

khối hệ thống bài học tập trên umakarahonpo.com bao gồm các bài triết lý và thực hành về các technology java và technology web. Những bài lý thuyết trên khối hệ thống umakarahonpo.com được tham khảo và tổng hòa hợp từ các trang http://javatpoint.com, http://www.tutorialspoint.com, http://docs.oracle.com/en …


Scroll back to top