Given positive integer n, print all binary sequences
of length n without consecutive ones, in lexicographical order.
Input. One positive integer n
(n ≤ 20).
Output. Print each
sequence in a separate line. Digits in a sequence must be separated with a
space.
|
Sample
input |
Sample
output |
|
3 |
0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 |
combinatorics
Let x be an integer.
In binary representation number x contains two ones in a row if x & (x <<
1) is
not zero.
Iterate in the
variable x over the numbers from 0 to 2n – 1. If number x in the binary
representation does not contain two ones in a row, then output such binary
representation.
Second solution. Consider a
recursive solution. Let’s declare an array and construct the required
sequences in it. For the current position p (0 ≤ p < n) there are two options for setting values:
·
m[p] = 0, and then generate a sequence from the position p + 1;
·
m[p] = 1, m[p + 1] = 0, and then generate a
sequence from the position p + 2;
For the second
option, for p = n – 1 (the last
position), we only assign m[p] = 1.
Read value of n.
scanf("%d",&n);
Iterate over the numbers from 0 to 2n – 1.
for(x = 0; x < (1 << n); x++)
{
If number x
contains two ones in a row in its binary representation, then skip it.
if (x &
(x << 1)) continue;
In one line print the binary code of the number x from left to
right as a sequence of 0 and 1.
for(i = n -
1; i >= 0; i--)
printf("%d
",(x >> i) & 1);
printf("\n");
}
Algorithm realization – recursive solution
#include <stdio.h>
int n;
int m[22];
void gen(int p)
{
if (p >= n)
{
for (int i = 0; i < n; i++)
printf("%d ", m[i]);
printf("\n");
return;
}
m[p] = 0; gen(p + 1);
m[p] = 1; m[p + 1] = 0; gen(p + 2);
}
int main(void)
{
scanf("%d", &n);
gen(0);
return 0;
}
Algorithm realization – recursive solution, string
#include <iostream>
#include <string>
using namespace std;
int n;
string s;
void gen(int p, string s)
{
if (p == n)
{
cout << s << endl;
return;
}
gen(p + 1, s + "0 ");
if (p < n - 1) gen(p + 2, s + "1 0
");
else gen(p + 1, s + "1 ");
}
int main(void)
{
cin >> n;
gen(0, "");
return 0;
}