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

Nhiệm vụ: đếm số chuỗi nhị phân độ dài n không có hai số 1 liên tiếp.

Hệ nhị phân (Binary Number System) là kỹ thuật biểu diễn số phổ biến trong hệ thống số. Chỉ có hai ký hiệu: 0 và 1. Chuỗi nhị phân chỉ chứa 0 và 1.

Ví dụ:

Đầu vào – n = 2

Đầu ra – Số chuỗi nhị phân không 1 liên tiếp độ dài 2 là: 3

Giải thích – 00, 01, 10 (chỉ 3 chuỗi độ dài 2 không có 1 liên tiếp)

Đầu vào – n = 7

Đầu ra – Số chuỗi nhị phân không 1 liên tiếp độ dài 7 là: 34

Cách tiếp cận trong chương trình

• Nhập n độ dài chuỗi
• Trong hàm count: khai báo hai mảng arr[], arr_2 kích thước n, biến temp lưu kết quả
• Gán phần tử 0 của cả hai mảng = 1
• Vòng lặp i=1 đến n-1
• Trong vòng lặp: arr[i] = arr[i-1] + arr_2[i-1]; arr_2[i] = arr[i-1]
• temp = arr[n-1] + arr_2[n-1], in temp

Ví dụ

#include 
// hàm tính chuỗi nhị phân không 1 liên tiếp
void count(int num){
    int arr[num];
    int arr_2[num];
    int i=0, temp=0;
    arr[0] = arr_2[0] = 1;
    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(){
    count(10);
    count(7);
    count(1);
    return 0;
}

Kết quả

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