[C]. Tính Tổng Ước Số Nguyên

main

1.Phương Pháp Cơ Bản

Bạn đang xem: [C]. Tính Tổng Ước Số Nguyên

Để tính tổng ước hay đếm ước của một số nguyên N bạn có thể làm cách đơn giản nhất là duyệt các số từ 1 đến N và kiểm tra tính chia hết của N với các số đó.

Đây là cách làm dễ hiểu nhưng lại không tối ưu về mặt thời gian thực thi.

Vì các ước của N thì chỉ nằm trong khoảng [1, N]

Code 1 : Tính tổng ước của N

#include “stdio.h” int tonguoc(int n){ int tong = 0; for(int i = 1; i <= n; i++){ if(n % i == 0){ tong += i; } } return tong; } int main(){ int N = 60; printf(“Tong uoc cua N : %dn”, tonguoc(N)); }

Output :

Tong uoc cua N : 168

Code 2 : Đếm ước của N

#include “stdio.h” int demuoc(int n){ int dem = 0; for(int i = 1; i <= n; i++){ if(n % i == 0){ dem += 1; } } return dem; } int main(){ int N = 60; printf(“So uoc cua N : %dn”, demuoc(N)); }

Output :

So uoc cua N : 12

2. Phương Pháp Tối Ưu 1

Xem thêm : Vì sao khi đã giết được kẻ thù là Bá Kiến,Chí Phèo lại tự kết liễu đời mình? Từ bi kịch đó, hãy nêu lên giá trị hiện thực sâu sắc và giá trị nhân đạo cao cả trong truyện Chí Phèo

Trong phương pháp cơ bản để tính tổng ước hay đếm ước của số N bạn cần N vòng lặp, bạn có thể cải tiến phương pháp bằng cách duyệt từ 1 tới N / 2.

Giải thích vì sao chỉ cần duyệt tới N / 2 : Các ước của N ngoại trừ chính nó đều nhỏ hơn N / 2 vậy nên ta có thể mặc định là N có ước là chính nó và xét các ước còn lại trong đoạn [1, N / 2].

Ví dụ N = 60 có các ước 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 nhưng ngoại trừ 60 thì các ước còn lại đều nằm trong đoạn [1, N / 2]

Code 1 : Tính tổng ước của N

#include “stdio.h” int tonguoc(int n){ int tong = n; for(int i = 1; i <= n / 2; i++){ if(n % i == 0){ tong += i; } } return tong; } int main(){ int N = 60; printf(“Tong uoc cua N : %dn”, tonguoc(N)); }

Code 2 : Đếm ước của N

#include “stdio.h” int demuoc(int n){ int dem = 1; // n for(int i = 1; i <= n / 2; i++){ if(n % i == 0){ dem += 1; } } return dem; } int main(){ int N = 60; printf(“So uoc cua N : %dn”, demuoc(N)); }

3. Phương Pháp Tối Ưu 2

Trong phương pháp tối ưu 1 để tìm ước của N bạn chỉ cần N / 2 vòng lặp. Phương pháp tối ưu thứ 2 thì bạn chỉ cần duyệt từ 1 tới √N là đủ.

Giải thích : Để tìm được tổng ước hay đếm ước của một số ta cần xét tất cả các ước của N, vậy nếu duyệt từ 1 tới √N thì sẽ không duyệt được các ước lớn hơn √N. Ví dụ với N = 60 thì √N = 7 (lấy số nguyên) sẽ không xét được các ước như 20, 30, 60 ?

Với số tự nhiên N, bạn luôn có thể viết N thành tích của 2 ước của nó. Ví dụ với N bằng 60 thì bạn có thể viết thành 1×60, 2×30, 3×20, 4×15, 5×12, 6×10.

Giả sử viết N = a * b và a ≤ b trong đó a và b tương ứng với 2 ước của N thì chắc chắn a ≤ √N, vì nếu a > √N thì b > √N và khi đó tích của a và b sẽ vượt quá N.

Vậy nên khi xét tất cả các ước của N thì ta chỉ cần xét được ước nhỏ hơn (√N) và từ ước nhỏ hơn đó suy ra được ước còn lại.

Ví dụ với N = 60 :

Xem thêm : Giải đáp: Bà bầu ăn rau diếp cá có ảnh hưởng tới thai nhi không

ab160230320415512610

Chú ý : Với N là số chính phương thì sẽ xảy ra trường hợp 2 ước a và b bằng nhau, khi đó bạn chỉ được xét 1 lần.

Ví dụ với N = 16

ab1162844

Code 1 : Tính tổng ước của N

#include “stdio.h” #include “math.h” int tonguoc(int n){ int tong = 0; for(int i = 1; i <= sqrt(n); i++){ if(n % i == 0){ tong += i; // ước thứ 1 if(i != n / i){ tong += n / i; // ước tương ứng } } } return tong; } int main(){ int N = 60; printf(“Tong uoc cua N : %dn”, tonguoc(N)); }

Output :

Tong uoc cua N : 168

Code 2 : Đếm ước của N

#include “stdio.h” #include “math.h” int demuoc(int n){ int dem = 0; // n for(int i = 1; i <= sqrt(n); i++){ if(n % i == 0){ dem += 1; // ước i if(i != n / i){ dem += 1; // ước n / i } } } return dem; } int main(){ int N = 60; printf(“So uoc cua N : %dn”, demuoc(N)); }

Output :

So uoc cua N : 12

KẾT LUẬN : Trong 3 phương pháp trên thì phương pháp thứ 3 tối ưu nhất tuy nhiên cũng sẽ khó hiểu nhất, các bạn nên sử dụng code thứ 3 để tìm ước và tính tổng ước sau khi kết thúc bài học này.

Xem thêm video hướng dẫn của mình về bài toán tính tổng ước :

SnQzrOaR-S4

Nguồn: https://luatduonggia.edu.vn
Danh mục: Tổng hợp