Tìm phần tử đầu tiên có dạng 2^k

Yêu cầu:
– Cho mảng số nguyên
– Tìm phần tử đầu tiên trong mảng nguyên có dạng 2^k (k >= 0). Nếu không tìm thấy, hàm trả về 0.
Ví dụ:
– Cho mảng nguyên A = {123, 32, 56, 678, 973}
– Phần tử đầu tiên trong mảng có dạng 2^k là 32 (2^5)

Giải thuật:
– Duyệt mảng, kiểm tra từng phần tử có thỏa mãn điều kiện 2^k không?

Code

/************************************************************
* Author: VNCODING
* History
* 2016/12/27        first create    VNCODING
*************************************************************/

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

#define MAX_SIZE_ARR 100

bool check_2expK(int x);
int get_first_2expK(int*, int);

int main()
{
    int arr[MAX_SIZE_ARR];
    int n, i;
    int res;
    do
    {
        printf("n = ");
        scanf("%d", &n);
    }while(n <= 0 || n > 100);
    
    // Input array
    for(i = 0; i < n; i++)
    {
        printf("\narr[%d] = ", i);
        scanf("%d", &arr[i]);
    }

    res = get_first_2expK(arr, n);
    if (res == 0)
    {
        printf("\nNot found!!!");
    }
    else
    {
        printf("\nThe first element has 2^k format: %d", res);
    }
    getch();
    return 0;
}

bool check_2expK(int x)
{
    int p = 1;
    while (1)
    {       
        if (p == x)
        {
            return true;
        }
        else if (p > x)
        {
            return false;
        }
        else
        {
            //nothing to do
        }
        p *= 2;
    }
}

int get_first_2expK(int arr[], int sz)
{
    int i;
    int res = 0;
    for (int i = 0; i < sz; i++)
    {
        if (check_2expK(arr[i]))
        {
            res = arr[i];
            break;
        }
    }
    return res;
}

Tìm phần tử đẩu tiên trong mảng nguyên có dạng 2^k
Tìm phần tử đẩu tiên trong mảng nguyên có dạng 2^k

1 Comment on Tìm phần tử đầu tiên có dạng 2^k

Leave a Reply to emsongtu Cancel reply