ให้หาจำนวน binary strings ทั้งหมดที่มีความยาว n โดยไม่มี 1 ติดกัน
Binary Number System เป็นหนึ่งในเทคนิคการแสดงตัวเลข ที่นิยมและใช้ในระบบดิจิทัล ระบบ binary ใช้แสดงปริมาณ binary ซึ่งสามารถแสดงได้โดยอุปกรณ์ใดๆ ที่มีสถานะการทำงานเพียง 2 แบบ ตัวอย่างเช่น สวิตช์มีแค่ 2 สถานะ: เปิด หรือ ปิด
ในระบบ Binary มีสัญลักษณ์หรือค่าตัวเลขที่เป็นไปได้เพียง 2 ค่า คือ 0 และ 1 แสดงโดยอุปกรณ์ที่มีสถานะการทำงาน 2 แบบ Binary strings คือสตริงที่มีค่า binary คือ 0 หรือ 1
มาทำความเข้าใจว่าต้องทำอะไรด้วยตัวอย่าง −
Input − n = 2
Output − Count of binary strings without consecutive 1's of 2 is : 3
Explanation − 00, 01, 10 ดังนั้นมีเพียง 3 binary strings ที่มีความยาว n และไม่มี 1 ติดกัน
Input − n = 7
Output − Count of binary strings without consecutive 1's of 7 is − 34
แนวทางที่ใช้ในโปรแกรมด้านล่าง
รับค่า n สำหรับความยาวสตริง
ในฟังก์ชัน count จะนับ binary strings ที่ไม่มี 1 ติดกัน กำหนดอาร์เรย์ arr[] และ arr_2 ขนาด n และตัวแปร temp เก็บผลลัพธ์
กำหนดค่าองค์ประกอบที่ 0 ของทั้งสองอาร์เรย์เป็น 1
วนลูปจาก i=1 ถึง i < n
ในลูป กำหนด arr[i] = arr[i-1] + arr_2[i-1] และ arr_2[i] = arr[i-1]
กำหนด temp = arr[n-1] + arr_2[n-1] แล้วพิมพ์ temp
ตัวอย่าง
#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;
}
ผลลัพธ์
ถ้ารันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −
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
