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

@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
*/

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию 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 и. . .

@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

Опции темы

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

Решение