main

1. Dãy Con Cỡ K có Tổng Lớn Nhất

Cho mảng A[] gồm N phần tử và số nguyên K, bạn hãy tính tổng các dãy con liên tiếp có K phần tử của mảng A[] và in ra màn hình

Ví dụ A[] = {3, 2, 1, 5, 6, 7, 2} và K = 3 các bạn sẽ có các dãy con : {3, 2,1}, {2, 1, 5}, {1, 5, 6}, {5, 6, 7}, {6, 7, 2}

Thuật toán : 

1. Duyệt các chỉ số i từ 0 tới N - K đại diện cho phần tử đầu tiên của dãy con
2. Tính tổng K phần tử liên tiếp từ chỉ số i và in ra màn hình 

Code : 

#include "stdio.h"

int main(){
    int n = 7, k = 3;
    int a[7] = {3, 2, 1, 5, 6, 7, 2};
    int tong = 0;
    for(int i = 0; i <= n - k; i++){
        //reset giá trị của tổng ở mỗi dãy con
        tong = 0;
        for(int j = 0; j < k; j++){
            tong += a[i + j];
        }
        printf("%d ", tong);
    }
    return 0;
}

Output : 

6 8 12 18 15

2. Dãy Con Giống Nhau Dài Nhất

Cho mảng A[] gồm N phần tử bạn hãy tìm độ dài của dãy con chứa các phần tử giống nhau dài nhất. 

Ví dụ A[] = {1, 2, 2, 2, 3, 3, 5, 4, 4, 4, 4, 2} thì dãy con {4, 4, 4, 4} là dãy con dài nhất chứa các phần tử giống nhau 

Thuật toán : 

1. Khởi tạo 1 biến đếm bằng 1 đại diện cho A[0]
2. Duyệt từ chỉ số 1 tới N - 1 và so sánh A[i] với A[i - 1]
3. Nếu A[i] = A[i - 1] thì tăng biến đếm
4. Nếu A[i] != A[i - 1] thì cập nhật kết quả thông qua biến đếm sau đó reset biến đếm về 1 để đếm lại dãy con bắt đầu từ A[i]

Code : 

#include "stdio.h"

int main(){
    int n = 12;
    int a[12] = {1, 2, 2, 2, 3, 3, 5, 4, 4, 4, 4, 2};
    int dem = 1, res = 1;
    for(int i = 1; i < n; i++){
        if(a[i] == a[i - 1]){
            ++dem;
        }
        else{
            if(res < dem){
                res = dem;
            }
            dem = 1;
        }
    }
    //Chú ý cập nhật dãy con dài nhất kết thúc tại A[n - 1]
    if(dem > res){
        res = dem;
    }
    printf("%d\n", res);
    return 0;
}

Output : 

4

Bạn thử làm thêm yêu cầu liệt kê tất cả các dãy con giống nhau dài nhất, ví dụ A[] = {1, 2, 2, 2, 3, 3, 5, 4, 4, 4, 3, 2} thì có 2 dãy con thỏa mãn là {2, 2, 2} và {4, 4, 4}

3.Dãy Con Khác Nhau Dài Nhất

Cho mảng A[] gồm N phần tử bạn hãy tìm độ dài lớn nhất của dãy con chứa các phần tử sao cho không có hai phần tử liền kề nào giống nhau.

Ví dụ A[] = {1, 2, 3, 2, 3, 3, 5, 4, 4, 4, 4, 2} thì dãy con {1, 2, 3, 2, 3} là dãy con cần tìm

Thuật toán : 

1. Khởi tạo 1 biến đếm bằng 1 đại diện cho A[0]
2. Duyệt từ chỉ số 1 tới N - 1 và so sánh A[i] với A[i - 1]
3. Nếu A[i] != A[i - 1] thì tăng biến đếm
4. Nếu A[i] = A[i - 1] thì cập nhật kết quả thông qua biến đếm sau đó reset biến đếm về 1 để đếm lại dãy con bắt đầu từ A[i]

Code : 

#include "stdio.h"

int main(){
    int n = 12;
    int a[12] = {1, 2, 3, 2, 3, 3, 5, 4, 4, 4, 4, 2};
    int dem = 1, res = 1;
    for(int i = 1; i < n; i++){
        if(a[i] != a[i - 1]){
            ++dem;
        }
        else{
            if(res < dem){
                res = dem;
            }
            dem = 1;
        }
    }
    //Chú ý cập nhật dãy con dài nhất kết thúc tại A[n - 1]
    if(dem > res){
        res = dem;
    }
    printf("%d\n", res);
    return 0;
}

Output : 

5

4. Kiểm Tra Mảng Tăng Dần

Bài toán yêu cầu bạn kiểm tra mảng A[] có N phần tử đã cho có tăng dần (giảm dần hay không), mảng tăng dần thỏa mãn yêu cầu phần tử đứng sau lớn hơn hoặc bằng phần tử đứng ngay trước nó.

Ví dụ A[] = {1, 2, 2, 3, 4, 5} là mảng tăng dần

Thuật toán : 

Xét N - 1 cặp phần tử đứng cạnh nhau, nếu N - 1 cặp phần tử này đều thỏa mãn phần tử đứng sau A[i] lớn hơn hoặc bằng phần tử ngay trước nó là A[i - 1] thì mảng tăng dần

Chú ý không cần kiểm tra A[0] và phần tử đứng trước nó.

Code : 

#include "stdio.h"

int check(int a[], int n){
    for(int i = 1; i < n; i++){
        if(a[i] < a[i - 1]){
            return 0;
        }
    }
    return 1;
}

int main(){
    int n = 6;
    int a[6] = {1, 2, 2, 3, 4, 5};
    if(check(a, n)){
        printf("Mang tang dan\n");
    }
    else{
        printf("Mang khong tang dan\n");
    }
    return 0;
}

Output : 

Mang tang dan

5. Dãy Nguyên Tố Dài Nhất

Cho mảng A[] gồm N phần tử, hãy in ra dãy con dài nhất chứa toàn số nguyên tố, nếu có nhiều dãy con thỏa mãn thì chọn ra dãy con có tổng lớn nhất và xuất hiện đầu tiên.

Ví dụ A[] = {2, 3, 5, 8, 7, 11, 19, 4, 10, 23, 5} thì dãy con {7, 11, 19} có độ dài 3 và có tổng lớn nhất.

Thuật toán : 

1. Khởi tạo 1 biến đếm bằng 0 và một biến tổng bằng 0
2. Duyệt qua các phần tử A[i] trong mảng từ chỉ số 0 tới N - 1
3. Nếu phần tử A[i] là số nguyên tố thì tăng biến đếm và cộng thêm A[i] vào biến tổng
4. Nếu phần tử A[i] không phải là số nguyên tố thì cập nhật kết quả, sau đó reset biến đếm về 0 và tổng về 0 

Code : 

#include "stdio.h"
#include "math.h"

int prime(int n){
    if(n < 2){
        return 0;
    }
    for(int i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            return 0;
        }
    }
    return 1;
}

int main(){
    int n = 11;
    int a[11] = {2, 3, 5, 8, 7, 11, 19, 4, 10, 23, 5};
    int dem = 0, tong = 0;
    int res_dem = 0, res_tong = 0, start = -1;
    for(int i = 0; i < n; i++){
        if(prime(a[i])){
            ++dem;
            tong += a[i];
        }
        else{
            if(dem > res_dem){
                res_dem = dem;
                res_tong = tong;
                start = i - res_dem;
            }
            else if(dem == res_dem){
                if(tong > res_tong){
                    res_tong = tong;
                    start = i - res_dem;
                }
            }
            dem = 0; tong = 0;
        }
    }
    //cap nhat day con ket thuc tai a[n - 1]
    if(dem > res_dem){
        res_dem = dem;
        res_tong = tong;
        start = n - res_dem;
    }
    else if(dem == res_dem){
        if(tong > res_tong){
            res_tong = tong;
            start = n - res_dem;
        }
    }
    if(start == -1){
        printf("Mang khong chua so nguyen to !\n");
    }
    else{
        for(int i = 0; i < res_dem; i++){
            printf("%d ", a[i + start]);
        }
    }
    return 0;
}

Output : 

7 11 19

Xem thêm bài giảng của mình về Mảng 1 Chiều :

DrKvp90X0Uo