Số hoàn hảo (hay còn gọi là số hoàn chỉnh, số hoàn thiện hoặc số hoàn thành) là một số nguyên dương mà tổng các ước nguyên dương chính thức của nó bằng chính nó.
Kiểm tra số hoàn hảo là một bài toán cơ bản khi học lập trình C/C++ mà hầu hết các bạn sẽ đều làm qua, những bài toán này có thể giúp người mới học lập trình hiểu hơn về tư duy trong lập trình, vậy trong bài viết này cùng blog tuicocach.com giải quyết bài toán này cũng như tìm cách tối ưu nhất cho bài toán.
Kiểm tra Số hoàn hảo trong Lập trình C/C++
Các số hoàn hảo đầu tiên trong dãy là 6, 28, 496, 8128…..
6 có các ước chính thức là:1, 2, 3 và 1 + 2 + 3 = 6 =>6 là số hoàn hảo
28 có các ước chính thức là: 1, 2, 4,7, 14 và 1 + 2 + 4 + 7 + 14 = 28 => 28 là số hoàn hảo
……
Vậy ý tưởng của bài toán sẽ như sau, giả sử ta cần kiểm tra số n có phải là số hoàn thiện hay không.
- Khai báo 1 biến sum khởi tạo giá trị bằng 0.
- Duyệt vòng lặp i chạy từ 1 tới n.
- Nếu n chia hết cho i thì i chính là một ước của n, ta cộng i vào biến sum.
- Hết vòng lặp nếu sum chính bằng n thì kết luận n là số hoàn thiện, ngược lại n không phải là số hoàn hảo.
Code minh họa C/C++
#include <stdio.h>
//Hàm kiểm tra số hoàn hảo
bool kt_soHoanHao(int n){
int sum = 0; //Khởi tạo biến sum
//Duyệt vòng lặp từ 1 tới n để tìm các ước của n
for(int i = 1; i < n; i++){
if(n%i == 0) sum = sum + i; //Nếu i là môt ước ta cộng dồn i vào biến sum
}
//Lệnh if else viết gọn => tương đương if(sum==n) return true; else return false;
return sum==n?true:false;
}
int main()
{
int n = 28;//gắn biến n cần kiểm tra (Bạn có thể cho nhập n từ bàn phím)
//Tương đương với if(kt_soHoanHao(n) == true)
if(kt_soHoanHao(n))
printf("%d la so hoan hao", n);
else
printf("%d khong phai la so hoan hao", n);
}
Tuy nhiên, với hàm kiểm tra số hoàn hảo bên trên thì chưa được tối ưu và chương trình chạy tương đối lâu….giả sử n là số 1.000.000.000 thì vòng lặp sẽ chạy 1 tỉ bước lặp.
- Kiếm tiền Accesstrade, kiếm tiền tại nhà với Accesstrade.vn – Tiếp thị liên kết
- MegaURL – Rút gọn link kiếm tiền có giá cao tại Việt Nam
- Top 4 App kiếm tiền online trên điện thoại tốt nhất 2022
Tối ưu hàm kiểm tra số hoàn hảo
Nếu một số n mà có ước là một số x thì sẽ tồn tại một số (n/x) cũng là một ước của n.
Hay nói cách khác nếu một số n đã có 1 ước thì chắc chán sẽ còn 1 ước khác nữa, mà 2 ước này nhân với nhau bằng n, tạm gọi là 2 ước đối số. 2 đối số này chắc chán sẽ có 1 số nhỏ hơn và 1 số lớn hơn căn bậc hai của n, và trong trường hợp n là số Chính phương thì 2 đối số này bằng nhau(16 = 4×4).
Một số ví dụ cụ thể
với số 20
20 sẽ chia hết cho 2, như vậy 20 cũng sẽ chia hết cho (20/2) tức là 10…và gọi 2 và 10 là cặp ước đối số.
20 cũng chia hết cho 4, như vậy cũng sẽ chia hết cho đối số là 5.
với số 16
16 chia hết cho 2, như vậy 16 cũng sẽ chia hết cho 8
16 chia hết cho 4, mà ước đối số của 4 thì cũng sẽ chính là 4 vì 16 là số chính phương.
Như vậy, rõ rằng thay vì duyệt vòng lặp chạy từ 1 cho tới n để kiểm tra hết tất cả các ước của n, thì lúc này chúng ta sẽ rút ngắn vòng lặp chỉ cần chạy từ 1 cho tới căn bậc 2 của n là được rồi. Khi đã có 1 ước nằm phía bên trái so với căn bậc của n thì ta sẽ cộng thêm ước đối số nằm phía bên phải căn bậc của n. Lúc này để duyệt hết các ước của số 1 tỉ thay vì chạy 1 tỉ bước lặp như trên thì giờ đây chỉ chạy tới căn bậc 2 của 1 tỉ tức là 31.622 bước lặp…rõ rằng tối ưu hơn rất nhiều lần.
Hàm kiểm tra số hoàn thiện viết lại như sau.
#include <stdio.h>
#include <math.h>
bool kt_soHoanHao(int n){
//Số âm, sô 0, số 1 không phải là số hoàn hảo
if(n<2) return false;
//Một số lớn hớn 1 chắc chắn sẽ có 1 ước là 1 nên ta có thể gắn ngay sum = 1
int sum = 1;
int sq = sqrt(n); //Lấy căn bậc 2 của n
//Vì ở trên ta đã xác định 1 chính là một ước rồi nên vòng lặp ta bỏ qua và chỉ chạy vòng lặp bắt đầu từ 2
for(int i = 2; i <= sq; i++){
if(n%i == 0) {
sum = sum + (i + (n/i)); // n/i để lấy ước đối số của i
}
}
return sum==n?true:false;
}
int main()
{
int n = 28;
if(kt_soHoanHao(n)) printf("%d la so hoan hao", n);
else printf("%d khong phai la so hoan hao", n);
}
Hàm tính căn bậc sqrt nằm trong thư viện math.h trong C.
Lưu ý một chút là các bạn nên để hàm tính căn bặc 2 ra bên ngoài vòng lặp nhé, nếu để ngay bên trong điều kiện vòng lặp như sau for(int i=2;i <=sqrt(n) ;i++) là mỗi lần thực hiện lại bước lặp chương trình sẽ tính toán căn bậc 2 một lần nữa nên chương trình sẽ chậm hơn một chút đấy.
Áp dụng hàm kiểm tra số hoàn thiện vào các bài toán
Khi đã có hàm kiểm tra số hoàn hảo ta có thể áp dụng hàm này vào giải quyết các bài toán như liệt kê số hoàn thiện nhỏ hơn n, đếm số hoàn thiện nhỏ hơn n, liệt kê số hoàn thiệt trong mảng.v.v.
- Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay
- Khóa học Java cơ bản dành cho người mới bắt đầu- Giảm 40% hôm nay
- Khóa học lập trình Android từ cơ bản đến thành thạo – Giảm ngay 40%
Chương trình liệt kê số hoàn hảo nhỏ hơn n
#include <stdio.h>
#include <math.h>
bool kt_soHoanHao(int n){
if(n<2) return false;
int sum = 1;
int sq = sqrt(n);
for(int i = 2; i <= sq; i++){
if(n%i == 0) {
sum = sum + (i + (n/i));
}
}
return sum==n?true:false;
}
int main()
{
int n;
printf("Nhap n: ");
scanf("%d", &n);
printf("\n------------LIET KE SO HOAN HAO NHO HON N----\n");
for(int i=0;i<n;i++){
if(kt_soHoanHao(i)) printf("%d ", i);
}
}
Chương trình liệt kê số hoàn hảo trong mảng
#include <stdio.h>
#include <math.h>
bool kt_soHoanHao(int n){
if(n<2) return false;
int sum = 1;
int sq = sqrt(n);
for(int i = 2; i <= sq; i++){
if(n%i == 0) {
sum = sum + (i + (n/i));
}
}
return sum==n?true:false;
}
void nhapMang(int a[],int n){
for(int i = 0; i < n; i++){
printf("a[%d] = ", i);
scanf("%d", &a[i]);
}
}
int main()
{
int n;
printf("Nhap n: ");
scanf("%d", &n);
int a[n];
printf("\n------------NHAP MANG----\n");
nhapMang(a,n);
printf("\n------------LIET KE SO HOAN HAO TRONG MANG----\n");
for(int i=0;i<n;i++){
if(kt_soHoanHao(a[i])) printf("%d ", a[i]);
}
}
Cảm ơn bạn đã đọc hết bài viết! Chúc bạn học tốt!@admin
[Xem tất cả bài viết chủ đề C/C++ tại đây]
XÊM THÊM Cách tìm UCLN và BCNN Thuật toán đếm số lượng chữ số của số nguyên dương n Thuật toán tính dãy số Fibonacci Bài toán chuẩn hóa xâu ký tự
