ในโจทย์นี้ เราต้องหาตัวเลขไบนารีที่ไม่มี 1 ติดกัน ในสตริงไบนารี 3 บิต มีตัวเลข 3 ตัวคือ 011, 110, 111 ที่มี 1 ติดกัน และมี 5 ตัวที่ไม่มี 1 ติดกัน ดังนั้นคำตอบสำหรับ 3 บิตคือ 5
ถ้า a[i] เป็นเซตของตัวเลขไบนารีที่มี i บิต และไม่มี 1 ติดกัน และ b[i] เป็นเซตที่มี 1 ติดกัน จะมีความสัมพันธ์แบบเวียนเกิดดังนี้:
a[i] := a[i - 1] + b[i - 1]
b[i] := a[i - 1]
อินพุต
อัลกอริทึมรับจำนวนบิตของตัวเลขไบนารี สมมติอินพุตคือ 4
เอาต์พุต
คืนค่าจำนวนสตริงไบนารีที่ไม่มี 1 ติดกัน
ผลลัพธ์คือ 8 (มีสตริงไบนารี 8 ตัวที่ไม่มี 1 ติดกัน)
อัลกอริทึม
countBinNums(n)
Input: n is the number of bits. Output: Count how many numbers are present which have no consecutive 1. Begin define lists with strings ending with 0 and ending with 1 endWithZero[0] := 1 endWithOne[0] := 1 for i := 1 to n-1, do endWithZero[i] := endWithZero[i-1] + endWithOne[i-1] endWithOne[i] := endWithZero[i-1] done return endWithZero[n-1] + endWithOne[n-1] End
ตัวอย่างโค้ด
#include <iostream> using namespace std; int countBinNums(int n) { int endWithZero[n], endWithOne[n]; endWithZero[0] = endWithOne[0] = 1; for (int i = 1; i < n; i++) { endWithZero[i] = endWithZero[i-1] + endWithOne[i-1]; endWithOne[i] = endWithZero[i-1]; } return endWithZero[n-1] + endWithOne[n-1]; } int main(){ int n; cout << "Enter number of bits: "; cin >> n; cout << "Number of binary numbers without consecutive 1's: "<<countBinNums(n) << endl; return 0; }ผลลัพธ์
Enter number of bits: 4 Number of binary numbers without consecutive 1's: 8
