Таблица кодирования букв в виде трехразрядных двоичных кодов

@pechka_ne_sed · Регистрация: 20.11.2023

Студворк — интернет-сервис помощи студентам

Вот задача:

Для алфавита из 8 букв дана таблица кодирования букв в виде трехразрядных двоичных кодов:
М - 000
К - 001
А - 010
Р - 011
О - 100
Л - 101
Е -110
П - 111

Для некоторого слова, используя двоичные коды его букв, составили новую двоичную последовательность следующим образом. Двигаясь слева направо, рассматривается очередная пара соседних букв в слове и для неё записывается результат одной из трех побитовых операций над двоичными кодами этих букв:

если обе буквы согласные: записывается операция побитового И
если обе буквы гласные: записывается операция побитового ИЛИ
если буквы разной гласности: записывается побитовый XOR

Обратим внимание, что коды всех букв, кроме первой и последней, будут участвовать в двух побитовых операциях.

Например, для слова МАК результатом кодирования будет последовательность 010011.

Расшифруйте последовательность 011110000010 и запишите в ответ получившееся слово.

Задача, на мой взгляд, несложная, но комплексная.
Ответ: ЛЕММА, и он верный.
Вопрос не про ответ, а про код, алгоритм решения, на листочке решить легко за полчаса, но это неприемлемо.
Я написал класс единицы кода (CodeUnit), которая является оберткой над std::bitset<3> (Data), и имеет функцию-член decode, которая возвращает std::vector пар возможных букв, из которых могла получится
эта самая единица. В теории, это можно посчитать в компаил-тайме.
Уже весь шифр представлен массивом единиц (Code::Units).
Я выбираю единицу, у которой меньше всего вариантов пар возможных букв, из которых она могла получится, чтобы по идее, дальше меньше перебирать, но что дальше, не совсем понятно(
Возможно, ничего непонятно из всех моих объяснений, поэтому извините, объяснил, как смог

.
Код:

Minimal.hh

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#pragma once
 
#include <cstddef>
#include <bitset>
#include <unordered_map>
 
constexpr std::size_t CODE_UNIT_SIZE { 3 };
constexpr std::size_t CODE_UNIT_VARIANTS_COUNT { 1 << CODE_UNIT_SIZE };
 
using Data = std::bitset<CODE_UNIT_SIZE>;
using Symbol = wchar_t;
using DecodingTable = std::unordered_map<Data, Symbol>;
using ConcordanceTable = std::unordered_map<Data, bool>;
 
namespace abc {
    inline constexpr Data M { 0b000 };
    inline constexpr Data K { 0b001 };
    inline constexpr Data A { 0b010 };
    inline constexpr Data R { 0b011 };
    inline constexpr Data O { 0b100 };
    inline constexpr Data L { 0b101 };
    inline constexpr Data E { 0b110 };
    inline constexpr Data P { 0b111 };
}

CodeUnit.hh

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#pragma once
 
#include "Minimal.hh"
 
#include <vector>
 
class CodeUnit {
public:
    using DecodeInfo = std::vector<std::pair<Data, Data>>;
 
    CodeUnit(const Data&);
 
    DecodeInfo decode(const ConcordanceTable &table) const;
private:
    Data data_ { 0 };
};

CodeUnit.cc

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include "CodeUnit.hh"
 
CodeUnit::CodeUnit(const Data &data) : data_ { data } { }
 
CodeUnit::DecodeInfo CodeUnit::decode(const ConcordanceTable &table) const {
    DecodeInfo decodeInfo;
 
    for (std::size_t i { 0 }; i < CODE_UNIT_VARIANTS_COUNT; i++)
        for (std::size_t j { 0 }; j < CODE_UNIT_VARIANTS_COUNT; j++) {
            Data result;
 
            std::pair<Data, Data> searchInfo { { i }, { j } };
 
            if (table.at(searchInfo.first) && table.at(searchInfo.second))
                result = searchInfo.first & searchInfo.second;
            else if (!table.at(searchInfo.first) && !table.at(searchInfo.second))
                result = searchInfo.first | searchInfo.second;
            else
                result = searchInfo.first ^ searchInfo.second;
 
            if (result == data_)
                decodeInfo.push_back(searchInfo);
        }
 
    return decodeInfo;
}

Code.hh

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#pragma once
 
#include "CodeUnit.hh"
 
class Code {
public:
    using Units = std::vector<CodeUnit>;
    using SummaryDecodeInfo = std::vector<Data>; 
 
    Code(const Units&);
 
    SummaryDecodeInfo decode(const ConcordanceTable&);
 
private:
    Units units_;
};

Code.cc (вопрос, собственно, возник тут)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "Code.hh"
 
#include <algorithm>
 
Code::Code(const Units &units) : units_ { units } { }
 
Code::SummaryDecodeInfo Code::decode(const ConcordanceTable &table) {
    Code::SummaryDecodeInfo result;
 
    std::vector<CodeUnit::DecodeInfo> input { units_.size() };
 
    for (std::size_t i { 0 }; i < input.size(); i++)
        input[i] = units_[i].decode(table);
 
    const auto pivotIt = std::min_element(input.begin(), input.end(), [](auto rhs, auto lhs) {
        return rhs.size() < lhs.size();
    });
 
    // ???
 
    return result;
}

@igorrr37 · 08.12.2023, 14:59

У слов МАК и ААК одинаковый код, так что неоднозначно.
Вот так получилось

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <bitset>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstdlib>
 
int main()
{
    system("chcp 1251 > 0");
    std::string strInit{ "011110000010" };
    std::unordered_map<char, std::string> ump{ {'А', "010"},{'О', "100"},{'Е', "110"}, {'М', "000"},{'К', "001"},{'Р', "011"},{'Л', "101"},{'П', "111"} };
    std::unordered_set<int> ustCon{ 'М', 'К', 'Р', 'Л', 'П' }; // согласные
    std::string sAbc = "АОЕМКРЛП"; // алфавит
    std::vector<std::vector<std::pair<char, std::string>>> vres{{{'~', sAbc}}}; // результат (с фиктивной последней буквой)
    std::vector<std::pair<char, std::string>> vtmp;
    enum enumVC { UNDEF = -1, CON, VOW };
    enumVC prev = UNDEF, cur = UNDEF;
    
    // Дешифруем слово с конца
    // Кладём во vres элементы от последнего до второго включительно
    for (int i = strInit.size() - 3; i >= 0; i -= 3)
    {
        auto ans = std::bitset<3>(strInit, i, 3).to_ulong();
        vtmp.clear();
        for (int j = 0; j < vres.back().size(); ++j)
        {
            for (auto charCur : vres.back()[j].second)
            {
                vtmp.emplace_back(charCur, "");
                int intCur = std::bitset<3>(ump[charCur]).to_ulong();
                cur = ustCon.contains(charCur) ? CON : VOW;
                for (auto charPrev : sAbc)
                {
                    int intPrev = std::bitset<3>(ump[charPrev]).to_ulong();
                    prev = ustCon.contains(charPrev) ? CON : VOW;
                    if ((prev == CON && cur == CON && (intPrev & intCur) == ans)
                        || (prev == VOW && cur == VOW && (intPrev | intCur) == ans)
                        || (prev == CON && cur == VOW && (intPrev ^ intCur) == ans)
                        || (prev == VOW && cur == CON && (intPrev ^ intCur) == ans))
                    {
                        vtmp.back().second.push_back(charPrev);
                    }
                    int yy = 0;
                }
                if (vtmp.back().second.empty())
                    vtmp.pop_back();
                int yy = 0;
            }
            int yy = 0;
        }
        vres.push_back(vtmp);
        int yy = 0;
    }
 
    // удаляем те записи из vres в которых прогнозируемая предыдущая буква не совпадает с фактической предыдущей
    std::reverse(vres.begin(), vres.end());
    vres.pop_back(); // удаляем фиктивный элемент
    for (int i = 0; i < vres.size() - 1; ++i)
    {
        std::string sFact; // набор фактических предыдущих букв
        for (int j = 0; j < vres[i].size(); ++j)
        {
            sFact += vres[i][j].first;
        }
        for (int j = 0; j < vres[i + 1].size(); )
        {
            if (vres[i + 1][j].second.find_first_of(sFact) == std::string::npos)
            {
                vres[i + 1].erase(vres[i + 1].begin() + j);
            }
            else
            {
                ++j;
            }
        }
        int yy = 0;
    }
 
    // вывод результата
    for (auto& pr : vres.front())
    {
        std::cout << pr.second;
    }
    std::cout << "\n";
    for (auto& v : vres)
    {
        for (auto& pr : v)
        {
            std::cout << pr.first;
        }
        std::cout << "\n";
    }
}

@pechka_ne_sed · 08.12.2023, 18:17 **[ТС]**

Ну, попробую разобраться.

Добавлено через 2 минуты
igorrr37, к сожалению, я не умею читать чужой код, поэтому прошу вас просто описать алгоритм, ибо даже с комментариями мне понять сложновато.

@igorrr37 · 08.12.2023, 18:54

Сообщение от pechka_ne_sed

описать алгоритм

Берём первую тройку бит из кода и перебором находим все пары букв которые могут дать такую тройку. Найдя эти пары мы фактически нашли все варианты первых и вторых букв в искомом слове. Теперь перебираем все варианты третьих букв в слове которые в паре с найденными вторыми буквами дадут вторую тройку бит кода. И так далее.

@pechka_ne_sed · 08.12.2023, 19:12 **[ТС]**

Спасибо, теперь понял

Добавлено через 2 минуты
А что, если такой пары нет?

@igorrr37 · 08.12.2023, 19:25

Сообщение от pechka_ne_sed

А что, если такой пары нет?

Есть. Если перебрать все пары одинаковых букв то они дадут все возможные тройки бит

@pechka_ne_sed · 08.12.2023, 19:44 **[ТС]**

Сообщение от igorrr37

std::bitset<3>(strInit, i, 3)

Можно же просто сдвинуть влево на 8 - i?

@igorrr37 · 08.12.2023, 21:23

для заданного кода выводит список всех слов подходящих под этот код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <bitset>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstdlib>
 
std::string sAbc = "АОЕМКРЛП"; // алфавит
std::vector<std::vector<std::pair<char, std::string>>> vres{ {{'~', sAbc}} }; // результат (с фиктивной последней буквой)
std::unordered_map<char, std::string> ump{ {'А', "010"},{'О', "100"},{'Е', "110"}, {'М', "000"},{'К', "001"},{'Р', "011"},{'Л', "101"},{'П', "111"} };
std::unordered_set<int> ustCon{ 'М', 'К', 'Р', 'Л', 'П' }; // согласные
std::vector<std::pair<char, std::string>> vtmp;
enum enumVC { UNDEF = -1, CON, VOW };
enumVC prev = UNDEF, cur = UNDEF;
 
 
std::string sWord;
void foo(int n, char c)
{
    if (n == vres.size())
    {
        std::cout << sWord << " ";
    }
    else
    {
        for (auto& [f, s] : vres[n])
        {
            if (s.find(c) != std::string::npos)
            {
                sWord.push_back(f);
                foo(n + 1, f);
                sWord.pop_back();
            }
        }
    }
}
 
void getWords()
{
    for (auto& [f, str] : vres[0])
    {
        for (auto c : str)
        {
            sWord.push_back(c);
            sWord.push_back(f);
            foo(1, f);
            sWord.pop_back();
            sWord.pop_back();
        }
    }
}
 
int main()
{
    system("chcp 1251 > 0");
    std::string strInit{ "101111011" }; // входная строка
 
    // Дешифруем слово с конца
    // Кладём во vres элементы от последнего до второго включительно
    for (int i = strInit.size() - 3; i >= 0; i -= 3)
    {
        auto ans = std::bitset<3>(strInit, i, 3).to_ulong();
        vtmp.clear();
        for (int j = 0; j < vres.back().size(); ++j)
        {
            for (auto charCur : vres.back()[j].second)
            {
                vtmp.emplace_back(charCur, "");
                int intCur = std::bitset<3>(ump[charCur]).to_ulong();
                cur = ustCon.contains(charCur) ? CON : VOW;
                for (auto charPrev : sAbc)
                {
                    int intPrev = std::bitset<3>(ump[charPrev]).to_ulong();
                    prev = ustCon.contains(charPrev) ? CON : VOW;
                    if ((prev == CON && cur == CON && (intPrev & intCur) == ans)
                        || (prev == VOW && cur == VOW && (intPrev | intCur) == ans)
                        || (prev == CON && cur == VOW && (intPrev ^ intCur) == ans)
                        || (prev == VOW && cur == CON && (intPrev ^ intCur) == ans))
                    {
                        vtmp.back().second.push_back(charPrev);
                    }
                    int yy = 0;
                }
                if (vtmp.back().second.empty())
                    vtmp.pop_back();
                int yy = 0;
            }
            int yy = 0;
        }
        std::sort(vtmp.begin(), vtmp.end());
        vtmp.erase(std::unique(vtmp.begin(), vtmp.end()), vtmp.end());
        vres.push_back(vtmp);
        int yy = 0;
    }
 
    // удаляем те записи из vres в которых прогнозируемая предыдущая буква не совпадает с фактической предыдущей
    std::reverse(vres.begin(), vres.end());
    vres.pop_back(); // удаляем фиктивный элемент
    for (int i = 0; i < vres.size() - 1; ++i)
    {
        std::string sFact; // набор фактических предыдущих букв
        for (int j = 0; j < vres[i].size(); ++j)
        {
            sFact += vres[i][j].first;
        }
        for (int j = 0; j < vres[i + 1].size(); )
        {
            if (vres[i + 1][j].second.find_first_of(sFact) == std::string::npos)
            {
                vres[i + 1].erase(vres[i + 1].begin() + j);
            }
            else
            {
                ++j;
            }
        }
        int yy = 0;
    }
 
    // вывод результата
    getWords();
    std::cout << "\n";
}
/*
клао    001111110
река    101111011
лемма   011110000010
клемма  001011110000010
мак     010011
мел     110011
*/

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@pechka_ne_sed 27 / 24 / 4 Регистрация: 20.11.2023 Сообщений: 131
	08.12.2023, 18:17 [ТС]
	Ну, попробую разобраться. Добавлено через 2 минуты igorrr37, к сожалению, я не умею читать чужой код, поэтому прошу вас просто описать алгоритм, ибо даже с комментариями мне понять сложновато. 0

@pechka_ne_sed 27 / 24 / 4 Регистрация: 20.11.2023 Сообщений: 131
	08.12.2023, 19:12 [ТС]
	Спасибо, теперь понял Добавлено через 2 минуты А что, если такой пары нет? 0

Таблица кодирования букв в виде трехразрядных двоичных кодов

Решение