ภารกิจคือการนับจำนวนสตริงไบนารีทั้งหมดที่มีความยาว n โดยไม่มี 1 ตัวติดต่อกัน
ระบบเลขฐานสองเป็นเทคนิคการแทนตัวเลขชนิดหนึ่ง เป็นที่นิยมและใช้งานในระบบดิจิทัลมากที่สุด ระบบเลขฐานสองใช้สำหรับแสดงปริมาณไบนารีซึ่งสามารถแสดงด้วยอุปกรณ์ใดๆ ที่มีสถานะการทำงานเพียงสองสถานะหรือเงื่อนไขที่เป็นไปได้ ตัวอย่างเช่น สวิตช์มีเพียงสองสถานะ:เปิดหรือปิด
ในระบบไบนารี มีเพียงสองสัญลักษณ์หรือค่าตัวเลขที่เป็นไปได้ กล่าวคือ 0 และ 1. แสดงโดยอุปกรณ์ใดๆ ที่มีสถานะการทำงานเพียง 2 สถานะหรือเงื่อนไขที่เป็นไปได้ สตริงไบนารีคือสตริงที่มีค่าไบนารีเช่น 0 หรือ 1
ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -
ป้อนข้อมูล − n =2
ผลผลิต − จำนวนสตริงไบนารีที่ไม่มี 1 ของ 2 ติดต่อกันคือ:3
คำอธิบาย − 00, 01, 10 ดังนั้นจึงมีเพียง 3 สตริงไบนารีที่มีความยาว n ไม่มี 1 อันต่อเนื่องกัน
ป้อนข้อมูล − n =7
ผลลัพธ์ − จำนวนของสตริงไบนารีที่ไม่มี 1 ของ 7 ติดต่อกันคือ − 34
แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้
-
รับอินพุต n สำหรับความยาวสตริง
-
ในฟังก์ชันการนับ เราจะนับสตริงไบนารีโดยไม่มี 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
