[C++] Sắp xếp các số nguyên tố về đầu dãy

Trong lập trình C/C++, việc sắp xếp số nguyên tố về đầu dãy là một bài toán phổ biến và thú vị. Đoạn mã dưới đây, chúng ta sẽ tạo một chương trình C++ đơn giản để đưa các số nguyên tố về đầu dãy.

Bài trước: Bài 17 (TH-CSLT-01). Hãy viết chương trình nhập vào một dãy số đến khi gặp số 0 thì dừng, sau đó tách mảng c++ số chẵn và số lẻ ra 02 mảng khác nhau. Tính trung bình cộng các số chẵn dương và trung bình cộng các số lẻ âm.

1. Bài toán

Bài 18: Nhập vào từ bàn phím dãy số gồm n số nguyên (n>0) và thực hiện các yêu cầu sau đây:

  1. Hiển thị dãy số ra màn hình.
  2. Nhập vào từ bàn phím số nguyên x. Hãy cho biết x xuất hiện trong dãy số bao nhiêu lần và các vị trí xuất hiện của x.
  3. Xoá các số có giá trị bằng 0 có trong dãy.
  4. Sắp xếp các số nguyên tố về đầu dãy, các số không phải là số nguyên tố về cuối dãy.
  5. Tính trung bình cộng các số chia hết cho 3 có trong dãy.

2. Xây dựng các thuật toán sắp xếp số nguyên tố

2.1 Hàm tìm x và cho biết vị trí xuất hiện được nhập từ bàn phím

– Các bước thực hiện:

  • Nhập x từ bàn phím
  • Duyệt mảng, nếu phẩn tử bằng x thì tăng biến dem và hiển thị ra vị trí vị trí của x
  • Nếu biến đếm khác không thì xuất ra màn hình xuất hiện, ngược lại hiển thị không có phần tử nào
void timx(int n, int a[]){

    int x,dem;
    cout<<"Nhap so nguyen x: "; cin>>x;
    for(int i=0;i<n;i++){
        if(a[i]==x){
            dem++;
            cout<<" Phan tu "<<x<<" xuat hien vi tri "<<i+1<<endl;
        }
    }

    if(dem!=0){
        cout<<"Phan tu "<<x<<" xuat hien "<<dem<<" lan";
    }else{
        cout<<"Khong co phan tu nao bang x";
    }
}

2.2 Hàm xoá các số có giá trị bằng 0 trong dãy

– Để xoá các phần tử có giá trị bằng 0, ta thực hiện duyệt mảng, nhặt các phần tử có giá trị khác 0 và xuất mảng ra màn hình.

void Xoacacsocogiatribang0(int n, int a[]){
    int j=0;
    for(int i=0;i<n;i++){
        if(a[i]!=0){
            a[j]=a[i];
            j++;
        }
    }

    for(int i=0;i<j;i++){
        cout<<setw(5)<<a[i];
    }
}

2.3 Hàm sắp xếp các số nguyên tố về đầu dãy, các số không phải là số nguyên tố về cuối dãy

– Có nhiều phương pháp để đưa các số nguyên tố về đầu dãy, dưới đây mình sẽ gợi ý cách tách thành 2 mảng theo các bước sau:

  • Xây dựng hàm kiểm tra số nguyên tố
  • Duyệt mảng, nếu là số nguyên tố thì gán vào mảng b ngược lại gán vào mảng c
  • Gộp mảng c vào mảng b và xuất mảng màn hình
void sapxepsonguyento(int n, int a[]){

    int b[255], c[255],m=0,k=0;
    //tachmang
    for(int i=0;i<n;i++){
        if(isPrime(a[i])){
            m++;
            b[m]=a[i];
        }else{
            k++;
            c[k]=a[i];
        }
    }
    //Gop mang
    for(int i=m+1;i<=n;i++){
        b[i]=c[i-m];
    }

    for(int i=1;i<=n;i++){
        cout<<setw(5)<<b[i];
    }
}

2.4 Hàm tính trung bình cộng các số chia hết cho 3 có trong dãy

void trungbinhcong(int n, int a[]){

    int sum=0,d=0;
    for(int i=0;i<n;i++){
        if(a[i]%3==0){
            sum+=a[i];
            d++;
        }
    }

    if(sum==0){
        cout<<"khong co so nao chia het cho 3"<<endl;
    }else{
        cout<<"Trung binh cac so chia het cho 3 = "<<sum/d;
    }
}

3. Chương trình hoàn thiện

#include <iostream>
#include <iomanip>
#include <math.h>

using namespace std;

//kiem tra so nguyen to
bool isPrime(int p){

        if(p<=1) return false;
        for(int i=2;i<=sqrt(p); i++){
            if(p%i==0){
                return false;
            }
        }
        return true;
    }

//nhap mang
void nhapmang(int n,int a[]){

    for(int i=0;i<n;i++){
        cout<<"a["<<i<<"]= ";
        cin>>a[i];
    }
}

//xuat mang
void xuatmang(int n, int a[]){
    for(int i=0;i<n;i++){
        cout<<setw(5)<<a[i];
    }
}


//Nhập vào từ bàn phím số nguyên x. Hãy cho biết x xuất hiện trong dãy số bao nhiêu lần và các vị trí xuất hiện của x
void timx(int n, int a[]){

    int x,dem;
    cout<<"Nhap so nguyen x: "; cin>>x;
    for(int i=0;i<n;i++){
        if(a[i]==x){
            dem++;
            cout<<" Phan tu "<<x<<" xuat hien vi tri "<<i+1<<endl;
        }
    }

    if(dem!=0){
        cout<<"Phan tu "<<x<<" xuat hien "<<dem<<" lan";
    }else{
        cout<<"Khong co phan tu nao bang x";
    }
}


void Xoacacsocogiatribang0(int n, int a[]){
    int j=0;
    for(int i=0;i<n;i++){
        if(a[i]!=0){
            a[j]=a[i];
            j++;
        }
    }

    for(int i=0;i<j;i++){
        cout<<setw(5)<<a[i];
    }
}

//Sắp xếp các số nguyên tố về đầu dãy, các số không phải là số nguyên tố về cuối dãy
void sapxepsonguyento(int n, int a[]){

    int b[255], c[255],m=0,k=0;

    for(int i=0;i<n;i++){
        if(isPrime(a[i])){
            m++;
            b[m]=a[i];
        }else{
            k++;
            c[k]=a[i];
        }
    }

    for(int i=m+1;i<=n;i++){
        b[i]=c[i-m];
    }

    for(int i=1;i<=n;i++){
        cout<<setw(5)<<b[i];
    }
}

//Tính trung bình cộng các số chia hết cho 3 có trong dãy
void trungbinhcong(int n, int a[]){

    int sum=0,d=0;
    for(int i=0;i<n;i++){
        if(a[i]%3==0){
            sum+=a[i];
            d++;
        }
    }

    if(sum==0){
        cout<<"khong co so nao chia het cho 3"<<endl;
    }else{
        cout<<"Trung binh cac so chia het cho 3 = "<<sum/d;
    }
}
int main(){

    int i, n, chon, x, a[255];

    do{
        cout<<"1. Nhap mang"<<endl;
        cout<<"2. Xuat mang"<<endl;
        cout<<"3. Cho biet x xuat hien bao nhieu lan"<<endl;
        cout<<"4. Sap xep so nguyen to ve dau day"<<endl;
        cout<<"5. Tinh trung binh cong cac so chia het cho 3"<<endl;
        cout<<"6. Xoa cac so co gia tri bang 0 trong day"<<endl;
        cout<<"Lua chon: "; cin>>chon;

        switch(chon){
            case 1:{
                cout<<"Nhap so phan tu: "; cin>>n;
                nhapmang(n,a);
                cout<<endl;
                break;
            }
            case 2:{
                xuatmang(n,a);
                 cout<<endl;
                break;
            }
            case 3:{
                timx(n,a);
                cout<<endl;
                break;
            }
            case 4:{
                sapxepsonguyento(n,a);
                cout<<endl;
                break;
            }
            case 5:{
                trungbinhcong(n,a);
                cout<<endl;
                break;
            }
            case 6:{
                Xoacacsocogiatribang0(n,a);
                cout<<endl;
                break;
            }

            default: exit(0);
        }
    }while(chon!=0);

}

4. Kết quả

Bài thực hành 18 lập trình c++

Bài thực hành 18 lập trình c++\

Trong bài viết này, chúng ta đã tạo một chương trình đơn giản về cách sắp xếp các số nguyên tố về đầu dãy trong ngôn ngữ lập trình C++. Bạn có thể mở rộng và tùy chỉnh nó theo nhu cầu của mình.  Cảm ơn các bạn đã theo dõi trên ttnguyen.net.

Tải full tài liệu bài tập thực hành C/C++ có lời giải:

Bài tiếp theo: Bài 19: chuyển đổi số thập phân sang số la mã