Program C/C++: Kira bilangan rentetan binari tanpa 1 berturut-turut?

Nombor binari ialah nombor yang mengandungi dua digit sahaja, 0 dan 1 sahaja. Setiap nombor binari ialah aliran bit binari, yang kami anggap sebagai rentetan binari. Untuk rentetan ini, kita perlu mencari bilangan rentetan binari N panjang yang tidak mengandungi 1 berturut-turut.

Sebagai contoh, untuk N=5, rentetan binari yang memenuhi syarat yang diberikan ialah 00000 00001 00010 00100 00101 01000 01001 01010 10000 10000 101010 10001 101010 .

Salah satu cara ialah menjana semua rentetan N-digit dan hanya mencetak rentetan yang memenuhi syarat yang diberikan. Walau bagaimanapun, pendekatan ini tidak cekap apabila melibatkan operasi berskala besar.

Cara lain ialah menggunakan rekursi. Pada setiap langkah rekursi, kami tambahkan 0 dan 1 pada nombor yang terbentuk separa dan mengulangi dengan kurang satu nombor. Kuncinya ialah hanya jika digit terakhir nombor yang dibentuk separa ialah 0, kita tambahkan 1 dan ulang. Dengan cara ini, tidak akan ada 1 berturut-turut dalam rentetan output.

Input: n = 5
Output: Number of 5-digit binary strings without any consecutive 1's are 13

Contoh

#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
   if (n == 0)
      return 0;
   if (n == 1) {
      if (last_digit)
         return 1;
      else
         return 2;
   }
   if (last_digit == 0)
      return countStrings(n - 1, 0) + countStrings(n - 1, 1);
   else
      return countStrings(n - 1, 0);
}
int main() {
   int n = 5;
   cout << "Number of " << n << "-digit binary strings without any "
   "consecutive 1&#39;s are " << countStrings(n, 0);
   return 0;
}

Atas ialah kandungan terperinci Program C/C++: Kira bilangan rentetan binari tanpa 1 berturut-turut?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!