Вывод двоичных чисел в которых две единицы не стоят рядом

Question

Задание: требуется подсчитать количество последовательностей длины N , состоящих из 0 и 1, в которых никакие две единицы не стоят рядом. Я сделал только вывод общего кол-ва, как мне сделать вывод самих двоичных чисел? Вот код:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int countStrings(const int n )
{
    vector<int> a(n), b(n); //Создадим вектор для работы со строками
    // a[i] - Двоичные числа длины i, которые не содержат двух последовательных 1 и заканчиваются 0
    // b[i] - Аналогично a[i], только заканчиваются 1
    a[0] = b[0] = 1; // Базовый случай
    for (int i = 1; i < n; i++)
    {
        a[i] = a[i-1] + b[i-1]; // К строке, заканчивающейся 0, мы можем добавить 0 или 1
        b[i] = a[i-1]; // К строке, заканчивающейся 1 мы можем добавить ТОЛЬКО 0
    }
    return a[n-1] + b[n-1];
}

int main()
{ 
    int N;
    cin >> N;
    cout << countStrings(N) << endl;
    return 0;
}

Answer 1

Примерно то же самое. Выводите 0, и далее рекурсивно для длины n-1, начинающиеся и с 0, и с 1. Потом - 1 и далее рекурсивно для n-1, начинающиеся с нуля...

Примерно так:

void out(int n, string prefix = "")
{
    char last = prefix.size() ? prefix[prefix.size()-1] : 0;
    if (n == 1)
    {
        if (last != '1') cout << prefix << '1' << endl;
        cout << prefix << '0' << endl;
        return;
    }
    if (last != '1')
        out(n-1,prefix+"1");
    out(n-1,prefix+"0");
}

См. рабочую программу - https://ideone.com/iOCXGe

Answer 2

Не смог удержаться от соблазна решить задачу строя список из узлов на стеке. Программа печатает последовательности в необычном порядке, но про порядок в условии не сказано :):

// g++ -std=c++11 -pedantic -Wall -Wextra -Werror print_fib_bins.cpp

#include <cstdio>

struct Node {
    char bit;
    const Node *next;
};

void print(const Node *list) {
    for (const Node *n = list; n != nullptr; n = n->next) {
        std::putc(n->bit, stdout);
    }
    std::putc('\n', stdout);
}

void print(int n, const Node *suffix) {
    if (n == 0) {
        print(suffix);
        return;
    }
    const Node node = {'0', suffix};
    print(n - 1, &node);
    if (suffix == nullptr || suffix->bit == '0') {
        const Node node = {'1', suffix};
        print(n - 1, &node);
    }
}

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n < 0) {
        return 1;
    }
    print(n, nullptr);
}

g++ -std=c++11 -pedantic -Wall -Wextra -Werror print_fib_bins.cpp
$ echo 5 | ./a.out 
00000
10000
01000
00100
10100
00010
10010
01010
00001
10001
01001
00101
10101
$ echo 35 | ./a.out | wc -l
24157817

БЛОГ НА HUSL

Вывод двоичных чисел в которых две единицы не стоят рядом

Ответы (2 шт):