Thuật toán kiểm tra số chính phương trong C / C++

Trong bài viết này, codehow sẽ giới thiệu đến các bạn thuật toán kiểm tra số chính phương trong C / C++. Đây là thuật toán được sử dụng khá nhiều khi bắt đầu học bất kì ngôn ngữ lập trình nào, bởi tính căn bản của nó.

Trước khi đi vào tìm hiểu về thuật toán, các bạn cùng mình tìm hiểu về khái niệm số chính phương là gì? Tính chất của nó đã nhé.

Số chính phương là gì?

Ví dụ: Mình có số 9 là một số chính phương bởi vì

• Căn bậc hai của 9 là 3 (đây là một số tự nhiên).
• Bình phương số 3 bằng 9 (bình phương của một số tự nhiên).

Như vậy các số tự nhiên đầu tiên sẽ là CP = {4, 9, 16, 25, ...}.

Thuật toán kiểm tra số chính phương trong C / C++

Để kiểm tra một số có phải là số chính phương hay không thì có rất nhiều cách. Tuy nhiên mình sẽ giới thiệu đến cách đơn giản và sử dụng nhiều nhất dưới đây.

• Kiểm tra bằng vòng lặp.
• Kiểm tra bằng hàm sqrt() trong thư viện math.h.

Vậy làm thế nào để viết thuật toán kiểm tra số chính phương trong C / C++ sử dụng hai cách trên thì hãy bắt đầu cùng mình thôi nhé.

Thuật toán kiểm tra số chính phương trong C / C++ sử dụng vòng lặp

Dưới đây là thuật toán kiểm tra số chính phương trong C / C++ với tham số truyền vào là một số tự nhiên n.

bool soCP(int n){
  int i = 0;
  while(i*i <= n){
        if(i*i == n){
            return true;
        }
        ++i;
    }
    return false;
}

Giải thích thuật toán:

1. Khai báo biến i = 0 để sử dụng cho vòng lặp, đây là giá trị đầu tiên mà vòng lặp sử dụng.
2. Sử dụng vòng lặp while với điều kiện i * i == n. Đây là điều kiện dừng của vòng lặp.
3. Trong vòng lặp, nếu i * i == n thì đây chính là số chính phương, ngược lại tăng i++ để tiếp tục vòng lặp.

Thuật toán kiểm tra số chính phương trong C / C++ sử dụng hàm sqrt()

Ngoài cách sử dụng vòng lặp thì còn một cách khác nhanh hơn và tối ưu hơn rất nhiều. Thay vì phải lặp từ 0 đến số n đó để tìm ra số chính phương thì ta chỉ cần xét đúng số đó mà thôi.

Nếu sử dụng cách một cho số 10000 thì nó phải lặp rất rất nhiều lần, điều này làm tốn thời gian và có thể dẫn đến lỗi.

bool soCP(int n){
  int sqr = sqrt(n);
    if(sqr*sqr == n){
        return true;
    }
    else return false;
}

Trong thư viện math.h cho phép chúng ta sử dụng hàm sqrt() để tính căn bậc hai của một số. Cần khai báo thư viện trước khi sử dụng nhé.

Giải thích thuật toán:

1. Khai báo biến sqr để lưu kết quả trả về từ hàm sqrt() cho số n.
2. Kiểm tra nếu bình phương biến sqr mà bằng n thì đây là số chính phương.
3. Ngược lại thì không phải là số chính phương.

Ví dụ thuật toán kiểm tra số chính phương trong C / C++

Dưới đây mình sẽ thực hiện một ví dụ sử dụng thuật toán kiểm tra số chính phương trong C / C++. Mình sẽ sử dụng thuật toán thứ hai đó là dùng hàm sqrt() để kiểm tra số chính phương.

Chương trình được viết bằng hai ngôn ngữ khác nhau là C và C++, các bạn có thể tham khảo nhé.

Đề bài: Viết chương trình in ra các số chính phương có trong mảng được nhập bởi người dùng.

Gợi ý:

• Tạo hàm kiểm tra số chính phương (sử dụng hàm sqrt()).
• Yêu cầu người dùng nhập vào số lượng phần tử và giá trị cho các phần tử trong mảng.
• Sử dụng vòng lặp for để lặp qua từng phần tử và gọi hàm kiểm tra số chính phương để kiểm tra phần tử đó. Nếu là số chính phương thì hiển thị ra màn hình, ngược lại thì nhảy qua vòng lặp tiếp theo.

Chương trình C:

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

//định nghĩa hàm kiểm tra số nguyên tố
bool scp(int n){
    int sqr = sqrt(n);
    return (sqr*sqr == n);
}
  
int main(){
  //khai báo biến n là số lương phần tử có trong mảng
    int n;
  //sủ dụng vòng lặp do...while để yêu cầu người dùng nhập vào số lương phần tử
  //điều kiện phải lớn hơn 0, nếu nhỏ hơn hoặc bằng thì bắt nhập lại
    do{
        printf("\nNhập vào số lượng phần tử có trong mảng: ");
        scanf("%d", &n);
        if(n <= 0) printf("\nVui lòng nhập số phần tử lớn hơn 0 !!\n");
    }while(n <= 0);
  //khai báo mảng với kích thước bằng số lượng người dùng nhập
    int a[n];
  //sử dụng vòng lặp for để nhập giá trị cho các phần tử trong mảng
    for(int i = 0;i < n;i++){
        printf("a[%d]=",i);
       scanf("%d", &a[i]);
    };
  //sử dụng vòng lặp for để lặp qua từng phần tử trong mảng
  //sau đó gọi hàm và kiểm tra phần tử đó có phải là số chính phương hay không
    printf("\nCác số chính phương là: \t");
    for(int i = 0;i < n; i++){
      //nếu là số chính phương thì hiển thị ra màn hình
        if(scp(a[i])){
            printf("%d   ",a[i]);
        }
    }
 
    printf("\n------------------------------\n");
    printf("Chương trình này được đăng tại codehow.net");
}

Kết quả:

Chương trình C++:

#include <iostream>
#include <math.h>
  
using namespace std;
//định nghĩa hàm kiểm tra số nguyên tố
bool scp(int n){
    int sqr = sqrt(n);
    return (sqr*sqr == n);
}
  
int main(){
  //khai báo biến n là số lương phần tử có trong mảng
    int n;
  //sủ dụng vòng lặp do...while để yêu cầu người dùng nhập vào số lương phần tử
  //điều kiện phải lớn hơn 0, nếu nhỏ hơn hoặc bằng thì bắt nhập lại
    do{
        cout << "\nNhập vào số lượng phần tử có trong mảng: ";
        cin >> n;
        if(n <= 0) cout<<"\nVui lòng nhập số phần tử lớn hơn 0 !!\n";
    }while(n <= 0);
  //khai báo mảng với kích thước bằng số lượng người dùng nhập
    int a[n];
  //sử dụng vòng lặp for để nhập giá trị cho các phần tử trong mảng
    for(int i = 0;i < n;i++){
        cout<<"a["<<i<<"]=";
       cin >> a[i];
    };
  //sử dụng vòng lặp for để lặp qua từng phần tử trong mảng
  //sau đó gọi hàm và kiểm tra phần tử đó có phải là số chính phương hay không
    cout << "\nCác số chính phương là: \t";
    for(int i = 0;i < n; i++){
      //nếu là số chính phương thì hiển thị ra màn hình
        if(scp(a[i])){
            cout << a[i] << "    ";
        }
    }
 
    cout<<"\n------------------------------\n";
    cout<<"Chương trình này được đăng tại codehow.net";
}

Kết quả:

Như vậy là chúng ta đã cùng nhau tìm hiểu về thuật toán kiểm tra số chính phươn trong C / C++. Các bạn hãy luyện tập thật nhiều để có thể sử dụng nó một cách thông thạo nhé. Chúc các bạn thành công !!!!