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; }
sử dung hàm
bool check_2expK(int x)
{
return x&(x-1)==0;
}
tốc độ kiểm tra sẽ nhanh hơn