Правильные скобочные последовательности

      Комментарии к записи Правильные скобочные последовательности отключены

Главная Форумы Программирование Алгоритмы и структуры данных Правильные скобочные последовательности

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 3 мес., 3 нед. назад.

  • Автор
    Сообщения
  • #3789

    ghost
    Участник

    Предлагаю всем посетителям форума решить задачу и написать свой алгоритм.
    Требуется написать алгоритм что бы получить все возможные правильные комбинации для функции типа:
    f(1)=()
    f(2)=()()

    f(n)=()..()

    Пример правильных комбинаций:
    f(3)
    ()()()
    ()(())
    (())()
    ((()))

    Для оптимизации работы оперативной памяти можно скобки заменить на 0 и 1.
    Я писал алгоритм на питоне мне удалось получить комбинации для до f(11) больше не хватило памяти.

    Хорошо если бы код выложили на репозиторий типа гитхаб.

  • #3814

    Решение задачи предоставил Данил Рязанцев:

    #include <iostream>
    #include <vector>
    #include <string>
    #include <bitset>
     
    // 1 - (
    // 0 - )
     
    using uint = unsigned int;
     
    bool check(uint seq, uint bit){
        int num = 0; // +1 = (
                     // -1 = )
     
        if(!((seq >> (bit-1)) & 1) || (seq & 1)){
            return false;
        }
     
        for(int i = bit-1; i >= 0; --i){
            if((seq >> i) & 1){
                ++num;
            }
            else {
                --num;
            }
     
            if(num < 0){
                return  false;
            }
        }
     
        return num == 0;
    }
     
     
     std::string coder(uint seq, int bit){
         std::string s;
         for(int i = bit-1; i >= 0; --i){
             if((seq >> i) & 1){
                 s += '(';
             }
             else {
                 s += ')';
             }
         }
     
         return s;
     }
     
     uint decoder(const std::string& s) {
         uint res = 0;
     
         for (auto i : s) {
             res  |= (i == '(');
             res <<= 1;
         }
     
         return res;
     }
     
     
     
    int main() {
        size_t N;
        std::cin >> N;
     
        std::vector<std::string> vec_seq;
     
        uint begin = 0;
        for(size_t i = 0; i < N; ++i){
            begin <<= 2;
            begin |= 2;
        }
     
        uint end = 0;
        for(size_t i = 0; i < N; ++i){
            end <<= 1;
            end |= 1;
        }
        end <<= N;
     
     
        do{
     
            if(check(begin, N*2)){
                vec_seq.push_back(coder(begin, N*2));
            }
     
            begin += 2;
        } while(begin <= end);
     
        std::cout << "F(" << N << "): " << std::endl;
        for(const auto &i : vec_seq){
            std::cout << i << std::endl;
        }
     
        std::cout << vec_seq.size() << std::endl;
     
        return 0;
    }

    Комментарий:

    только не знаю зачем вычислять большие значения, когда уже при 10 количество правильных перестановок равно 16796, а при 11 = 58786

Для ответа в этой теме необходимо авторизоваться.