Trong các bài toán căn bản về lập trình thì bài toán tìm số chính phương là một trong các bài toán được xem là kinh điển của lập trình. Hôm nay chúng ta sẽ cũng tìm hiểu về chủ đề này.
Tóm Tắt
Số chính phương là gì?
Số chính phương là số khi lấy căn bậc 2 của nó ta được một số nguyên hay có thể hiểu số chính phương là số có kết quả là bình phương của một số nguyên.
Một số ví dụ tìm số chính phương
Ví dụ 1: Nhập một số từ bàn phím và kiểm tra có phải là số chính phương hay không
Thuật toán: lấy căn của số vừa nhập và ép kiểu về kiểu số nguyên, sau đó bình phương số đã ép kiểu. nếu sau khi bình phương kết quả bằng số ban đầu thì kết luận số vừa nhập là số chính phương, ngược lại không phải
Code C/C++
#include<stdio.h> #include<conio.h> #include<math.h> void main() { int x; printf("Nhap 1 so nguyen: "); scanf("%d", &x); if (x > 3) { int a = sqrt((double)x); if (a*a == x) printf("%d la so chinh phuong", x); else { printf("%d khong la so chinh phuong", x); } } else printf("%d khong la so chinh phuong",x); getch(); }
Ví dụ 2: Tìm các số có trong 1 khoảng [x,y] nhập từ bàn phím ( khoảng từ [1-10] ) và xuất ra màn hình
Thuật toán:
Chạy từ x đến y,
Kiểm tra tất cả các giá trị đã đi qua, nếu thỏa thì xuất ra màn hình.
Để kiểm tra thì chúng ta cần phải có 1 hàm kiểm tra số chính phương
Code C/C++
Hàm kiểm tra:
int KTchinhphuong(int a) { if (a>3) { if (a == int(sqrt(double(a)))*int(sqrt(double(a)))) // ép kiểu về số nguyên return 1; // đúng trả về 1 else return 0; // sai trả về 0 } return 0; }
Hàm liệt kê:
void Lietkechinhphuong (int x, int y) { for(int i=x ; i<=y ; i++) if(KTchinhphuong(i)==1) // gọi hàm kiểm tra số chính phương printf("%5d",i); }
Ví dụ 3: Tìm và xuất ra màn hình các số chính phương có trong mảng 1 chiều
Thuật toán: Đi từ đầu mảng đến cuối mảng, kiểm tra tất cả các giá trị nếu thỏa thì xuất ra màn hình theo yêu cầu. Để thao tác trên mảng thì chúng ta cần tạo ra mảng 1 chiều. xem thêm ở bài viết Nhập xuất mảng một chiều
Code C/C++
//Tạo mảng: void NhapMang1C(int a[], int &n) { do { printf("Nhap so phan tu mang: "); scanf("%d", &n); }while (n<1); for (int i=0;i<n;i++) { printf("Nhap phan tu a[%d] : ", i); scanf("%d", &a[i]); } } //Xuất mảng void XuatMang1C (int a[] , int n) { for (int i=0 ; i<n ; i++) printf("%4d",a[i]); } //Hàm kiểm tra: int KTchinhphuong(int a) { if (a>3) { if (a == int(sqrt(double(a)))*int(sqrt(double(a)))) // ép kiểu về số nguyên return 1; // đúng trả về 1 else return 0; // sai trả về 0 } return 0; } //Hàm xuất các số chính phương của mảng void Lietkechinhphuong(int a[], int n) { for (int i = 0; i <= n; i++) if (KTchinhphuong(i) == 1) // gọi hàm kiểm tra số chính phương printf("%5d", i); } //Hàm main: void main() { // khai báo mảng và biến int a[100],n; NhapMang1C(a,n); Lietkechinhphuong(a,n); getch(); }
Ví dụ 4: Tìm và xuất ra màn hình các số chính phương của ma trận a[n,m].
Thuật toán: Để thao tác trên ma trận thì chúng ta cần tạo ra một mảng 2 chiều, sau đó tương tự chúng ta lại kiểm tra điều kiện số chính phương và xuất các số ra như đề bài.
Code C/C++
//Tạo ma trận: #define MaxD 100 #define MaxC 100 void NhapMaTran(int a[][MaxC], int &m, int &n) { do { printf("Nhap so dong: "); scanf("%d", &m); } while (m<=0); do { printf("Nhap so cot: "); scanf("%d", &n); } while (n<=0); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { printf("Phan tu a[%d][%d]", i, j); scanf("%d", &a[i][j]); } } //Xuất ma trận: void XuatMaTran(int a[][MaxC], int m, int n) { for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { printf("%5d \n", a[i][j]); } } //Tìm các số chính phương của ma trận: void MaTranSoChinhPhuong(int a[][MaxC], int m, int n) { for (int i = 0; i < m;i++) for (int j = 0; j < n; j++) { if (KTchinhphuong(a[i][j]) == 1) printf("%5d", a[i][j]); } } //Hàm main: void main() { int A[MaxD][MaxC]; int M, N; NhapMaTran(A, M, N); XuatMaTran(A, M, N); printf("Cac so chinh phuong co trong ma tran la:"); MaTranSoChinhPhuong(A, M, N); getch(); }
Kết quả:
Nhap so dong: 5
Nhap so cot: 1
Phan tu a[0][0]2
Phan tu a[1][0]3
Phan tu a[2][0]4
Phan tu a[3][0]5
Phan tu a[4][0] 6
2 3 4 5 6
Cac so chinh phuong co trong ma tran la: 4 9
Trên đây là một số ví dụ về tìm kiếm và liệt kê số chính phương! các bạn có thể xem thêm Số nguyên tố là gì ? Hàm tìm số nguyên tố
Chúc các bạn thành công!