Đếm số chuỗi nhị phân không có 1 liên tiếp trong C

Nhiệm vụ được giao là đếm số lượng của tất cả các chuỗi nhị phân có độ dài n mà không có bất kỳ 1 nào liên tiếp.

Hệ thống số nhị phân là một loại kỹ thuật biểu diễn số. Nó phổ biến nhất và được sử dụng trong các hệ thống kỹ thuật số. Hệ nhị phân được sử dụng để biểu diễn các đại lượng nhị phân có thể được biểu diễn bằng bất kỳ thiết bị nào chỉ có hai trạng thái hoạt động hoặc các điều kiện có thể. Ví dụ, một công tắc chỉ có hai trạng thái:mở hoặc đóng.

Trong Hệ thống nhị phân, chỉ có hai ký hiệu hoặc các giá trị chữ số có thể có, tức là 0 và 1 được biểu thị bởi bất kỳ thiết bị nào chỉ có 2 trạng thái hoạt động hoặc các điều kiện có thể. Chuỗi nhị phân là những chuỗi có chứa các giá trị nhị phân, tức là 0 hoặc 1

Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -

Đầu vào - n =2

Đầu ra - Đếm các chuỗi nhị phân không có số 1 liên tiếp của 2 là:3

Giải thích - 00, 01, 10 vì vậy chỉ có 3 chuỗi nhị phân có độ dài n không có 1 liên tiếp nào

Đầu vào - n =7

Đầu ra - Số chuỗi nhị phân không có số 1 liên tiếp của 7 là - 34

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Lấy một đầu vào n cho độ dài chuỗi

• Trong hàm đếm, chúng ta sẽ đếm các chuỗi nhị phân không có các số 1 liên tiếp, xác định hai mảng arr [] và arr_2 có kích thước n và một biến temp để lưu trữ kết quả.

• Gán phần tử thứ 0 của cả hai mảng là 1

• Lặp lại từ i =1 cho đến khi tôi nhỏ hơn n.

• Khi ở trong vòng lặp, Đặt arr [i] =arr [i-1] + arr_2 [i-1] và arr_2 [i] =arr [i-1]

• Đặt temp =arr [n-1] + arr_2 [n-1], rồi in nhiệt độ.

Ví dụ

#include<stdio.h>
//create function to calculate binary strings without consecutive 1’s
void count(int num){
   int arr[num];
   int arr_2[num];
   int i=0, temp=0;
   arr[0] = arr_2[0] = 1;
   //loop till number isn't equals to 0
   for (i = 1; i < num; i++){
      arr[i] = arr[i-1] + arr_2[i-1];
      arr_2[i] = arr[i-1];
   }
   temp = arr[num-1] + arr_2[num-1];
   printf("Count of binary strings without consecutive 1’s of %d is : %d",num,temp);
   printf("\n");
}
int main(){
   //call the count function
   count(10);
   count(7);
   count(1);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -

Count of binary strings without consecutive 1’s of 10 is : 144
Count of binary strings without consecutive 1’s of 7 is : 34
Count of binary strings without consecutive 1’s of 1 is : 2