Kiểm tra xem dãy A có phải là con của dãy B hay không?

Yêu cầu:

Cho 2 dãy A, B các số nguyên (kích thước dãy A nhỏ hơn dãy B). Hãy kiểm tra xem A có phải là con của B hay không?

Thuật toán:

Code:

/************************************************************
* Author: VNCODING
* History 
* 2014/11/16 first create VNCODING
*************************************************************/
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

bool is_a_contain_b(int A[], int n, int B[], int m);

void main( void )
{
    int A[] = {1, -2, 5, 6, 8, -9, 4, 5, 11, -7};
    int B[] = {6, 8, -9, 4};
    int n = sizeof(A)/sizeof(int);
    int m = sizeof(B)/sizeof(int);
    int k = 5;

    if(is_a_contain_b(A, n, B, m))
        printf("\nA contains B");
    else
        printf("\nA doesn't contain B");

    getch();
}

//Check whether A contains B or not?\
//Return: true: if A contains B, otherwise return false.
bool is_a_contain_b(int A[], int n, int B[], int m)
{
    int i, j, k;
    bool res = false;
    if(n < m)
        return false;
    for(i = 0; i < n; i++)
    {
        if(B[0] == A[i] && n - i >= m)
        {
            k = i + 1;
            res = true;
            for(j = 1; j < m; j++, k++)
            {
                if(B[j] != A[k])
                {
                    res = false;
                    break; 
                }
            }
            if(res)
                break;
        }
    }
    return res;
}

Kết quả:

A contains B

4 Comments on Kiểm tra xem dãy A có phải là con của dãy B hay không?

    • >int n = sizeof(A)/sizeof(int);
      >int m = sizeof(B)/sizeof(int);

      2 câu lệnh này để xác định số lượng phần tử của mảng A và B.
      Vì sao lại rắc rối thế?
      Vì kích thước kiểu dữ liệu nguyên thủy (int, float, long,..) phụ thuộc vào trình biên dịch. Ví dụ: Turbo C: sizeof(int) = 2, Visual studio: sizeof(int) = 4.
      int n = sizeof(A)/sizeof(int) = 40/4 = 10
      int m = sizeof(B)/sizeof(int) = 16/4 = 4

      • Em củng dựa theo cách này nhưng mảng a b là nhập từ bàn phím mà nó k chạy.e cứ tưởng khác nhau ở chỗ sizeof nên k chạy đc

        • Anh chưa hiểu ý em lắm.
          Nếu nhập từ bàn phím thì:
          – Yêu câu user nhập kích thước N cho mảng
          – Sau đó dùng malloc cấp phát bộ nhớ động với kích thước N phần tử
          – Yêu cầu user nhập giá trị các phần tử

          Làm thế này sẽ không sợ bị thừa hay thiếu vùng nhớ so với cách khai báo mảng tĩnh (ex: int A[100])

Leave a Reply to VietVH Cancel reply