Tulis program dalam C/C++ untuk mengira bilangan rentetan binari tanpa 1 berturut-turut?

Di sini kita akan melihat soalan yang menarik. Katakan nilai n diberikan. Kita mesti mencari semua rentetan panjang n yang tidak ada 1 berturut-turut. Jika n = 2, nombornya ialah {00, 01, 10}, jadi outputnya ialah 3.

Kita boleh menggunakan pengaturcaraan dinamik untuk menyelesaikannya. Katakan kita mempunyai jadual 'a' dan 'b'. di mana arr[i] menyimpan bilangan rentetan binari panjang i yang tidak mempunyai 1 berturut-turut dan ditamatkan dengan 0. Begitu juga, b adalah sama tetapi berakhir dengan 1. Kita boleh menambah 0 atau 1 jika yang terakhir ialah 0, tetapi hanya menambah 0 jika yang terakhir ialah 1.

Mari kita lihat algoritma untuk mendapatkan idea ini.

Algoritma

noConsecutiveOnes(n) - Terjemahan bahasa Cina bagi

Begin
   define array a and b of size n
   a[0] := 1
   b[0] := 1
   for i in range 1 to n, do
      a[i] := a[i-1] + b[i - 1]
      b[i] := a[i - 1]
   done
   return a[n-1] + b[n-1]
End

Contoh

ialah:

Contoh

#include <iostream>
using namespace std;
int noConsecutiveOnes(int n) {
   int a[n], b[n];
   a[0] = 1;
   b[0] = 1;
   for (int i = 1; i < n; i++) {
      a[i] = a[i-1] + b[i-1];
      b[i] = a[i-1];
   }
   return a[n-1] + b[n-1];
}
int main() {
   cout << noConsecutiveOnes(4) << endl;
}

Output

8

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