В Древней Греции (2 век до н.э.) был известен шифр, называемый "Квадрат Полибия". Шифровальная таблица представляла собой квадрат с пятью столбцами и пятью строками, которые нумеровались цифрами от 1 до 5. В каждую клетку такого квадрата записывалась одна буква. В результате каждой букве соответствовала пара чисел, и шифрование сводилось к замене буквы парой чисел. Для латинского алфавита "Квадрат Полибия" имеет вид:
1 2 3 4 5
1 A B C D E
2 F G H J,I K
3 L M N O P
4 Q R S T U
5 V W X Y Z
И мне нужно было написать программу которая могла делать следующее:
а) Зашифровать введенный текст из консоли и сохранить его в текстовый файл;
б) Считает зашифрованный текст из файла и расшифрует данный текст выведя его на консоль.
Вообще "Квадрат Полибия" может иметь разный вид, но сегодня поговорим о создании программы с данной ранее таблице. Мы будем делать нашу программу в Visual Studio 2019, но для каких-нибудь 2020 и т.п. тоже подойдет.
!!!Все буквы будут обрабатываться исключительно капслоком в этой программе, т.е. если вы заполните массив буквами с маленькой буквы, то буквы с консоли будут обрабатываться исключительно с маленькой буквы!!!
И так, нам для работы нужны будут следующие библиотеки:
System;//основная
System.Collections.Generic;//основная
System.Linq;//основная
System.Text;//основная
System.Threading.Tasks;//основная
System.IO;//для записи и чтения файла
System.Threading;//основная
Для начала мы в классе создадим двумерный массив для букв из таблицы, строчку для чтения слов с консоли и три переменные, первая для дальнейшего соединения двух последних, вторая для указания пути к нужному файлу, а третья само наименование файла и его формат. В данном случае текстовый (txt).
Вот как это выглядит:
string[,] tableEng = new string[,]
{
{ "A", "B", "C", "D","E" },
{ "F", "G", "H", "I", "K" },
{ "L", "M", "N", "O", "P" },
{ "Q", "R", "S", "T", "U" },
{ "V", "W", "X", "Y", "Z" },
};
string text;
string filePath;
string path = @"D:\\ТЫ ХОЧЕШЬ ЧТО ЛИ БАОБАБ НАЙТИ\\";
string file = @"\\память.txt";Затем в классе мы объявляем публичный метод, где уже мы будем реализовать свой код. Я его назвала квадратом полибия, но только по английский, а вы можете назвать его по другому, но так чтобы каждый при одном его названии смог понять за что этот кусок кода отвечает.
Выводим на консоль инструкцию, а на следующей строке соединяем нужные нам переменные в одну для указания нужного файла.
Затем мы реализуем начало записи с консоли данных(букв) и в теле метода мы пишем следующее:
⦁ Объявляем цикл while для завершения ввода нужных слов, т.е. считываем данные с консоли до тех пор пока пользователь не введет * и не тыкнет ентер,
⦁ Считываем данные с клавиатуры,
⦁ С помощью Split разделяем слова на и записываем его в массив m,
C помощью Split мы можем с строки удалять пробелы, символы, знаки препинания, а также не нужные нам буквы. И это можно записать как показано ниже:
string[] words = line.Split(' ', ',', '.', '-', '=', '+', '!', '?', '^', '&');⦁ С помощью foreach мы перебираем текст из массива,
⦁ А в следующем foreach мы перебираем текст уже с помощью переменной для символов, это нам понадобится для сравнения букв с буквами из массива tableEng,
⦁ Теперь мы перебираем с помощью циклов for массив tableEng, делаем цикл в цикле. Т.к. у нас массив двумерный, то нам нужно именно два цикла для перебора двух измерений в нем. А в сравнении, в циклах, где мы переменную i сравниваем с массивом, вместо Length мы будем использовать GetLength(), т.к. Length используется для одномерных массивов, а GetLength() для измерений многомерных массивов,
Length - для длины одномерных массивов
GetLength() - для длины измеренний многомерный массивов, в нашем случае двумерным. Если в скобочках напишем 0, то это будет длина первого измерения, если 1, то второго и т.д.
⦁ И пишем первое условие в if. Если в массиве какой-то из элементов массива tableEng равен символу из строки, то прибавляем к i + 1 и тоже самое к j + 1. Далее выводим все на консоль,
⦁ А внутри первого условия пишем второе для самого первого цикла while. Если переменная text равна *, то цикл прекращается, а данные с консоли записываются в файл.
Вот как выглядит код:
Console.WriteLine("Введите текст(только капслоком!!!!), который хотите зашифровать(для выхода * и ентер): ");
filePath = Path.Combine("D:\\", path + file);
//здесь зашифровываю текст по квадрату полибия и шифровку записываю в файл
using (StreamWriter streamWriter = new StreamWriter(filePath, true, Encoding.UTF8)) //это страка для записи данных с консоли в файл
{
while (text != "*")
{
text = Console.ReadLine();
string[] m = text.Split(' ');
foreach (string letter in m)
{
foreach (char c in letter)
{
for (int i = 0; i < tableEng.GetLength(0); i++)
{
for (int j = 0; j < tableEng.GetLength(1); j++)
{
if (tableEng[i, j] == c.ToString())
{
int result = i + 1;
int resu = j + 1;
Console.WriteLine($"{i + 1}{j + 1} ");
if (text == "*") break;
streamWriter.Write($" {result}{resu} ");
}
}
}
}
}
}
}Далее мы реализуем начало чтения с файла данных(букв) и в теле мы пишем следующее:
⦁ Объявляем переменную для дальнейшего чтения строк из файла,
⦁ Объявляем цикл while, в котором мы считываем строки с файла до тех пор, пока они не будут равны нулю, т.е. пока не закончатся,
⦁ Далее мы объявляем массив words и в нем разделяем строки на отдельные слова и записываем в него,
⦁ В цикле foreach мы перебираем символы из массива words. И в этом цикле мы выводим данные из файла. А также мы символы из файла сравниваем с определенными символами с помощью оператора switch case и если есть совпадение, то вручную с помощью Console.WriteLine выводим определенный элемент из массива tableEng.
Вот как это будет выглядить:
using (StreamReader streamReader = new StreamReader(filePath))
{
string line;
while ((line = streamReader.ReadLine()) != null)
{
string[] words = line.Split(' ');
foreach (var word in words)
{
Console.Write(word);
switch (word)
{
case "11":
Console.WriteLine($"{tableEng[0, 0]}");
break;
case "12":
Console.WriteLine($"{tableEng[0, 1]}");
break;
case "13":
Console.WriteLine($"{tableEng[0, 2]}");
break;
case "14":
Console.WriteLine($"{tableEng[0, 3]}");
break;
case "15":
Console.WriteLine($"{tableEng[0, 4]}");
break;
case "21":
Console.WriteLine($"{tableEng[1, 0]}");//
break;
case "22":
Console.WriteLine($"{tableEng[1, 1]}");
break;
case "23":
Console.WriteLine($"{tableEng[1, 2]}");
break;
case "24":
Console.WriteLine($"{tableEng[1, 3]}");
break;
case "25":
Console.WriteLine($"{tableEng[1, 4]}");
break;
case "31":
Console.WriteLine($"{tableEng[2, 0]}");
break;
case "32":
Console.WriteLine($"{tableEng[2, 1]}");
break;
case "33":
Console.WriteLine($"{tableEng[2, 2]}");
break;
case "34":
Console.WriteLine($"{tableEng[2, 3]}");
break;
case "35":
Console.WriteLine($"{tableEng[2, 4]}");
break;
case "41":
Console.WriteLine($"{tableEng[3, 0]}");
break;
case "42":
Console.WriteLine($"{tableEng[3, 1]}");
break;
case "43":
Console.WriteLine($"{tableEng[3, 2]}");
break;
case "44":
Console.WriteLine($"{tableEng[3, 3]}");
break;
case "45":
Console.WriteLine($"{tableEng[3, 4]}");
break;
case "51":
Console.WriteLine($"{tableEng[4, 0]}");
break;
case "52":
Console.WriteLine($"{tableEng[4, 1]}");
break;
case "53":
Console.WriteLine($"{tableEng[4, 2]}");
break;
case "54":
Console.WriteLine($"{tableEng[4, 3]}");
break;
case "55":
Console.WriteLine($"{tableEng[4, 4]}");
break;
}
}
}
Console.ReadLine();
}Если мы это делали в другой вкладке:
Далее в Main() мы объявляем класс, потом метод Cube_Polibiai() для вывода.
Вот так:
static void Main(string[] args)
{
Task_1 t = new Task_1();
t.Cube_Polibiai();
}Вот так я писала эту программу :)
Комментарии (38)
vfreeeman
02.11.2023 13:14+2switch (word) можно было бы на что-нибудь поэлегантнее заменить...
HotMilkTicTac Автор
02.11.2023 13:14Например?
myswordishatred
02.11.2023 13:14+2У вас же взаимно однозначное соответствие между позицией в таблице и числом. Почему бы тогда не придумать формулу, которая из одного будет получать другое?
saboteur_kiev
02.11.2023 13:14-1Почитай эту статью хотя бы через год-два, и отпишись в камментах, так сказать "письмо молодой себе"
DGG
02.11.2023 13:14+2Молодец.
Теперь замени страшный свитч на Console.WriteLine($"{tableEng[x, y]}");
Как получить x,y из word - подумай
navferty
02.11.2023 13:14+10И так, нам для работы нужны будут следующие библиотеки:
System;//основная
System.Collections.Generic;//основная
То что вы перечислили - это не библиотеки, а пространства имён, все они входят в BCL (base class library).
В алгоритме шифрования у вас на каждый символ два вложенных цикла поиска символа в массиве, что делает его чрезвычайно медленным (асимптотика O(n^3), подробнее тут). Я бы рекомендовал обратить внимание на использование словаря, под капотом у которого - хэш-таблица.
Алгоритм дешифрования чересчур громоздкий - что если у вас таблица будет 10х10? А если 128х128? Если вы точно знаете, что на входе - число, тогда его можно разделить на две компоненты, и с помощью int.Parse/int.TryParse получить нужные индексы для нахождения буквы.
Ну и перед публикацией статьи желательно хотя бы выровнять код, который Вы публикуете.
В целом, Вы молодец что изучаете программирование, но технический уровень этой статьи точно не соответствует уровню хабра. Рекомендую найти кого-то, кто бы помог Вам с вычитыванием статьи перед публикацией, ну и в целом в изучении языка C#. Можете писать мне, почта navferty@ymail.com
astec
02.11.2023 13:14+1Зачем хэш-таблицу? Достаточно массива и [CharCode-A]
navferty
02.11.2023 13:14+1Ну шифр на то и шифр, что порядок не обязан быть последовательным, как таблице Unicode =)
astec
02.11.2023 13:14+2В массиве хранить коды соответсвующие буквам. Код находить по индексу буквы где А=0
navferty
02.11.2023 13:14+2Честно говоря, я бы предпочел в такой ситуации всё равно использовать словарь, пусть даже это повлечёт некоторый оверхед по памяти - так код будет намного проще, а значит меньше шансов накосячить.
astec
02.11.2023 13:14+2Не только по памяти но и по CPU.
ris58h
02.11.2023 13:14+1Вы оба правы, но для понимания лучше начать с map, т.к. это классическое решение для получения значения по ключу. То, что это можно под капотом превратить в получению по индексу - приятный бонус.
navferty
02.11.2023 13:14-1В дотнете мапа - это и есть словарь. Разница будет в вызове GetHashCode, который делает немного арифметики, а именно
public override int GetHashCode() { return (int)(this | ((uint)this << 16)); }и нахождения в массиве (внутри словаря) значение по полученному индексу, или прямого обращения к массиву в варианте @astec
GrigorGri
02.11.2023 13:14+1Не могли бы пояснить, Асимптотика O(n^3) - что тут n?
Два вложенных цикла поиска символа в массиве - тут n вроде бы будет "длина одной стороны таблицы"? Проще принять тогда n за "количество символов в таблице" и поиск уже выходит за O(n), где n - длина алфавита. Ведь алгоритмически нет разницы между искать по прямоугольной таблицы vs искать по одномерному массиву, и там и там пройдешься по всем буквам алфавита один раз. Конечно это все еще хуже чем O(1).
Третий n получили из-за этого цикла?
foreach (string letter in m) foreach (char c in letter)?
Если так, мне кажется неправильным ставить куб из-за этого.
Кажется, должно быть
O(n*m), где n - количество букв в сообщении и m - количество букв в алфавите? Ведь это же разные параметры. Тогда звучит не так страшно: алгоритм автора O(n*m) против O(n) как получилось бы с словарем.
P.S.
Так как речь идет об английском алфавите, где количество букв постоянно, то и весь поиск можно обозначить за O(1). В O нотации нет разницы: мы же не ожидаем что в следущий раз в алфавите будет 100 букв, это константа. С словарем или без в обоих случаев выходит O(n*Const) = O(n), где n - количество букв в сообщении.
navferty
02.11.2023 13:14Окей, с чисто теоретической точки зрения, я погорячился, и при константном количестве букв этот множитель сводится к константе. На практике же, константа тоже может существенно повлиять на реальные требования по памяти и CPU.
Иногда оптимизация алгоритма может быть сопряжена с усложнением кода, и приходится выбирать между читабельным и поддерживаемым кодом, с одной стороны, и эффективностью с другой.
Но в данном случае, необходимость для каждой буквы ввода множество сравнений с каждой буквой алфавита - точно будет менее оправдана чем простой поиск по словарю, который будет эффективнее, и при этом описан более простым кодом.
redf1sh
02.11.2023 13:14+4Мне кажется, что если бы вы свою таблицу заменили на хэш-таблицу <key: символ value:набор из 2 цифр>, то сложность вашего решения сразу бы резко упала. Тем более, вы оперируете с заранее известным алфавитом и эту таблицу можно инициализировать статически.
Зачем текст разбивать на слова? Почему просто нельзя итерироваться по массиву символов в один проход?Свитч, как уже сказали действительно страшный, не ясно зачем он вообще нужен
Ну и статья не совсем для хабра на мой взгляд.
navferty
02.11.2023 13:14+2Я бы предложил автору скрыть статью в черновики, если есть желание не утонуть в минусах, и переделать код, а заодно занять форматированием и исправлением орфографических ошибок. Заодно можно было бы добавить небольшую историческую справку про сам шифр: как возник, где применялся реально, чтобы статья была интереснее. @HotMilkTicTac
iamawriter
02.11.2023 13:14То, что разобралась и написала самостоятельно (в этом нет сомнений) - это здорово, потенциал налицо. Я бы предложил теперь разобраться в моем коде ниже, и внести поправки в свой код, опираясь на идеи из моего кода (он, в свою очередь, опирается на идеи из вашего)):
Код на python
Square = [ list("abcde"), list("fghik"), list("lmnop"), list("qrstu"), list("vwxyz"), ] Alphabet = dict() Code = dict() SquareSize = len(Square) for i in range(SquareSize): for j in range(SquareSize): code = f"{i+1}{j+1}" letter = Square[i][j] Alphabet[code] = letter Code[letter] = code Splitter = ", " def encode(text): return Splitter.join([Code[letter] for letter in text if letter in Code]) def decode(encoded): return "".join( [Alphabet[code] for code in encoded.split(Splitter) if code in Alphabet] ) def encodeInput(filename): text = input("\nType your text to encode it. Press Enter to save it:\n").lower() encoded = encode(text) with open(filename, "w") as file: file.write(encoded) def decodeFile(filename): with open(filename, "r") as file: text = file.read() decoded = decode(text) print(decoded) encodeInput("my-secrets.txt") decodeFile("my-secrets.txt")Предлагаю код на python, потому что он легко читается, практически как псевдокод, с одной стороны, и не выглядит так, как будто я сделал вашу работу за вас, с другой. Я ни в коем случае не утверждаю, что мой код эталонный (и я не сильно думал над ним, если честно, поэтому он может быть где-то и некорректен), но он немного лучше вашего. Не сомневаюсь, что если кто-то здесь заморочится, то сумеет предложить и гораздо лучше, а по мне - для начала должно хватить и этого.
HemulGM
02.11.2023 13:14Предлагаю код на delphi, потому что он легче читается, практически псевдокод.
Код на Delphi
var Square := [ 'abcde', 'fghik', 'lmnop', 'qrstu', 'vwxyz']; var Alphabet := TDictionary<string, Char>.Create; var Codes := TDictionary<Char, string>.Create; var SquareSize := Length(Square); for var i := 0 to SquareSize - 1 do for var j := 1 to SquareSize do begin var code := Format('%d%d', [i + 1, j + 1]); var letter := Square[i][j]; Alphabet.Add(code, letter); Codes.Add(letter, code); end; var Splitter := ', '; var encode := function(text: string): string begin for var letter in text do if Codes.ContainsKey(letter) then Result := Result + Codes[letter] + Splitter; end; var decode := function(encoded: string): string begin for var code in encoded.Split(Splitter) do if Alphabet.ContainsKey(code) then Result := Result + Alphabet[code]; end; var encodeInput := procedure(filename: string) begin var text := input('Type your text to encode it. Press Enter to save it: '); TFile.WriteAllText(filename, encode(text.ToLower)); end; var decodeFile := procedure(filename: string) begin writeln(decode(TFile.ReadAllText(filename))); Readln; end; encodeInput('my-secrets.txt'); decodeFile('my-secrets.txt');
Tempest23
02.11.2023 13:14+2Не буду говорить о коде. Разные советы уже были выданы, а ваш прогресс в этой области - дело ответной реакции, анализа и дальнейшей практики.
Я хотел добавить, что и к написанию постов стоит подходить столь же тщательно. Когда вы читаете хорошие посты других авторов, обращайте внимание на то, как они написаны. Попытайтесь понять, что делает их хорошими. Это вовсе не обязательно уровень знаний: интересно и качественно можно рассказывать хоть сложение и вычитание первокласснику.
Вы детально описываете код словами, будто ваша целевая аудитория вообще ничего о программировании не знает и не сможет его прочесть. В результате, текст утопает в мелких деталях, которые и так очевидны: мы объявляем переменную, мы перебираем значения в цикле, и т.д. Было бы лучше, если бы описание фокусировалось на конкретном алгоритме и его реализации.
Пишите больше, пишите чаще. Не выкладывайте пост в тот же день, когда вы его написали. Отложите черновик на сутки, а затем вернитесь и прочтите его со свежей головой. Это поможет быть лучшим редактором для самого себя, если нет других опций.
На мой взгляд крайне полезно писать о том, что вы изучаете. Но этот навык тоже необходимо оттачивать. Успехов.
opv88
02.11.2023 13:14-1Живое олицетворение того, что, прежде чем писать код на каком-нибудь языке и абы как, нужно изучить хотя бы базовые основы и алгоритмизацию. А то потом это все перетекает на govnokod.ru (если честно, думал, что там уже все примеры искусственные, но похоже, что нет).
iig
02.11.2023 13:14думал, что там уже все примеры искусственные, но похоже, что нет
Студенты порой очень изобретательны, куда тем индусам ;)
arthurlomakin
02.11.2023 13:14Можно послушать детскую речь и заключить, что говорить можно только после того, как выучишь грамматику, строение языка
zaiats_2k
02.11.2023 13:14+1Толково придумано, зачем преподу возиться с учениками, проверять задания, наставлять на путь истинный. Ведь проще отправить их на хабр, писать статью о своей лабе...
v10k13
02.11.2023 13:14+2Очень много интересных рекомендаций, может это уже и не очень необходимо, все же постараюсь дать пару рекомендаций по коду
Во первых формула про которую так много говорили, думаю стоит дать пояснение того как её лучше реализовать, в скрытом тексте будет детальное пояснение и реализация в конце:
Формула
Сначала определимся, что наши исходные данные это таблица которая по длине и ширине не превосходит 9 т.к. иначе будет невозможно однозначно расшифровать результат после сцепления чисел
Обратим внимание, что при делении целых значений в c# остаток отбрасывается, этот факт нам пригодиться
Далее по решению буду считать что нумерация колонок начинается с 0
Итак, наш выход это число вида AB = 10 * A + B, где A - строка и B - колонка таблицы
Далее из нашего символа вычтем начало алфавита (большое а для кода в вашем решении)
Так как в нашей таблице определенное число колонок, а элементы расположены друг за другом в виде:0 1 2 3 4Не сложно заметить что номер нашей колонки равен остатку от деления на количество колонок:
5 6 7 8 9
...0 1 2 3 4Отлично, мы знаем как получить B теперь давайте посмотрим на строки
0 1 2 3 4
...
Каждая строка начинается с числа кратного числу колонок, из чего не трудно заметить что мы можем разделить наш символ на длину строки чтобы получить строку то есть А
Теперь вспоминаем что мы начинали с нуля, поэтому к A и B теперь нужно добавить по 1 чтобы не нарушалась оригинальная индексация
В результате получим:
A = (символ - начало алфавита) / длина строки + 1
B = (символ - начало алфавита) % длина строки + 1(uint, uint) CalculateCharecterCode(char Symbol, char AlphabetBegin = 'A', int RowSize = 5) { uint Column = (Symbol - AlphabetBegin) % RowSize + 1; uint Row = (Symbol - AlphabetBegin) / RowSize + 1; return (Row, Column); }Обратную формулу оставлю на вас
Далее скажу по поводу метода считывания текста, несмотря на то что сама идея мне не совсем понятна, попробую дате рекомендации:
Не стоит разделять текст на слова, воспользуйтесь методом streamReader.ReadToEnd() чтобы получить весь текст.
Используйте цикл того чтобы пройти по всем символам, вы можете использовать break при встрече * чтобы не перебирать текст дальше
Для того чтобы определять какие символы вам не нужно шифровать вы можете использовать реализованную в С# коллекцию HashSet<T>. Ссылочка:
https://learn.microsoft.com/ru-ru/dotnet/api/system.collections.generic.hashset-1?view=net-7.0
Я также заметил что в комментариях прозвучала проблема о размере таблицы. Сразу скажу что идея использования большой таблицы в методе шифрования времен древней Греции бесполезна. Изначально метод предназначен для шифрования ограниченного числа последовательно идущих символов переиначивать используя словари бесполезно.
Далее касательно капслока. У объекта строки есть специальный метод ToUpper() который переводит все символы строки в верхний регистр. Ссылочка:
https://learn.microsoft.com/ru-ru/dotnet/api/system.string.toupper?view=net-7.0#system-string-toupper
VBDUnit
02.11.2023 13:14Работает же? Работает. Да, не быстро, да, код неоптимальный. Но для начала, имхо, очень хорошо. В коде прослеживается именно человеческая логика, без оглядки на всякие особенности «мышления» машины (именно эти особенности диктуют «использовать Dictionary» и прочие вещи). Это нормально, понимание «мышления» машины — это следующий этап. И, глядя на то, как развивается технология, которую все называют «ИИ», не уверен, что это глубокое понимание мышления машины будет прям нужно, кроме узких случаев. Всякое ChatGPT + генетические алгоритмы хорошо будут генерировать быстрый оптимальный код, имхо.
Уже сейчас процессор может выполнять код по‑своему, переставляя команды и делая прочие штуки. Я уже не говорю про оптимизирующие компиляторы. В будущем это вообще может свестить к «компилятор/процессор читает код» → «компилятор/процессор понимает, чего от него хотят» → «пишет с нуля свой ультраоптимальный код, делающий то же самое, но хорошо, быстро, замечательно и с правильно поставленными отступами» → «выполняет код». И да, на входе, может быть уже не код, а вполне человеческий язык. Почему нет.
Да, программист («машинный тренер»?) уже не будет понимать/знать что там происходит. Но сейчас это тоже есть: программист на питоне почти всегда не знает, как там выделяется память и как вообще синхронизируются такты у блоков процессора, но это абстрагирование не мешает создавать продукты, пусть и не очень оптимальные. Программисту на питоне это не обязательно для решения задачи.
PS. Вот быстрый вариант в виде класса, чтобы примерно показать, что есть «затачивание под особенности мышления машины». Общий смысл: вместо того, чтобы каждый раз думать и что‑то искать на каждой букве, мы один раз создаём таблицу для всех возможных вариантов и комбинаций, и потом тупо дёргаем оттуда готовые значения. Это как таблица умножения. В моём варианте используются массивы, но можно использовать Dictionary, код будет лучше и проще, но чуть медленнее.
Можно ещё нажестить с unsafe/Marshal.AllocHGlobal с указателями, и всё будет ещё быстрее, но смысла в этом здесь нет, имхо: оно будет уже совсем страшное.
Класс PolybiusQuad
using System.Text; public class PolybiusQuad { public PolybiusQuad() { //При создании класса заполняем таблицу дефолтными значениями Table = new char[,] { { 'A', 'B', 'C', 'D','E' }, { 'F', 'G', 'H', 'I', 'K' }, { 'L', 'M', 'N', 'O', 'P' }, { 'Q', 'R', 'S', 'T', 'U' }, { 'V', 'W', 'X', 'Y', 'Z' }, }; } //Помимо типа string, который текст, есть ещё тип char //char - это один символ //Тут храним табличку-квадрат char[,] table; //Это свойство-обёртка таблички //Нам это нужно, чтобы после каждого присваивания Table выполнялись наши методы пересчёта карт public char[,] Table { get => table; //get происходит, когда значение Table считывают set //происходит, когда Table прирванивают к чему-то { if (value == null) throw new NullReferenceException("Не надо так"); table = value.Clone() as char[,]; /* * почему не просто table = value; * * есть риск, что сначала нам зададут table, а потом поменяеют в ней значения * переменные типа char[,] хранят не саму таблицу, а ссылку на неё * мы тут детектим изменение ссылки, а не самих значений * изменение самих значений не вызовет rebuildTableMap() и rebuildAntimap() * это потенциальный баг и плохо, поэтому мы создаём копию с помощью метода Clone() * а поскольку C# древнее зло, и метод Clone() тоже, он возвращает не char[,] а страшный ужас * чтобы вернуть его в тип char[,] используется оператор as. Можно ещё сделать (char[,])value */ /*При каждом задании новой таблицы пересчитываем карты преобразования в квадрат и обратно. * карты позволят нам работать очень быстро * программа не будет что-то там искать на каждой букве * она просто будет дёргать готовые значения из карты-массива по номеру * а номер будет вычисляться очень легко */ rebuildTableMap(); rebuildAntimap(); } } //длина карты преобразования (шифровки) const int linearTableLength = char.MaxValue + 1; //65535 + 1 /*карта преобразования В квадрат * идея следующая: * 1) В C# string - это набор charов, char - это символ (буква, цифра, знак препинания и т.п.) * 2) Всех возможных символов 65536, потому что char состоит из двух байт. Каждый байт имеет 256 возможных значений, всех возможных комбинаций всех байтов 256 * 256 = 65536. Соответственно, всех возможных значений char тоже 65536 * 3) В то же время, char можно интерпретировать как число. По сути, это и есть число от 0 до 65535. Это, как бы, номер в алфавите, только алфавит тут в 65536 букв. Поэтому мы можем взять букву, и использовать её как номер элемента массива. Не номер буквы в тексте, а прям саму букву. * 4) Мы создаём карту преобразования. Подобно тому, как можно выучить таблицу умножения и просто вспоминать нужные результаты, здесь мы будем вспоминать сразу готовые пары чисел для каждой буквы. Чтобы не путаться, эта штука называется картой, а таблица - это исходная таблица Полибия * 5) Расчёт карты преобразования происходит 1 раз при задании таблицы Полибия, в дальнейшем при каждой шифровке мы пользуемся готовой: берем символ, интерпретируем его как число, вытаскиваем из карты пары готовых значений, добавляем к тексту * 6) То есть наша карта это такой массив. В качестве индекса у него выступает сам символ (который на самом деле число от 0 до 65535 включительно), а в качестве значений - пара (строка-столбец) * 7) Нюанс: пару (строка-столбец) мы будем хранить не как пару чисел, а сразу как пару символов, чтобы преобразование числа в символ также вынести в карту и не делать каждый раз при шифровке. Нам же номер строки и столбца надо в стекст добавлять */ //карта проеобразования - массив длиной 65656, каждое значение - пара символов. Длина массива такова, что каждому возможному вообще в природе символу мы можем сопоставить пару каких-то других символов readonly (char row, char column)[] linearTableMap = new (char row, char column)[linearTableLength]; //В качестве типа элементов массива указан не int, не char, а (char row, char column) //это значит, что каждый элемент массива - пара чисел. Одно называется row, второе - column //readonly означает, что массив linearTableMap нельзя менять и присваивать, можно менять только значения внутри него void rebuildTableMap() { //Очищаем карту. Каждому элементу массива присваивается значение из пары непечатаемых символов, означающих отсутствие символа Array.Clear(linearTableMap, 0, linearTableLength); //Проходим по всем строкам и столбцам табилцы for (int row = 0; row < table.GetLength(0); row++) for (int column = 0; column < table.GetLength(1); column++) { //Берем символ из таблицы var symbol = table[row, column]; var rowChar = (char)(row + '0' + 1); //Это быстрый аналог (row + 1).ToString() var columnChar = (char)(column + '0' + 1); //Это быстрый аналог (column + 1).ToString() /* Почему (char)(row + '0' + 1) это быстрый аналог (row + 1).ToString() * * * Дело в том, что, хотя символы можно * интерпретировать как числа, а числа как символы (например, 'Ы' есть число 1067, а '!' есть число 33) * символы цифр - 0, 1, 2, 3 ... 9 * не совпадают с их численными эквивалентами, * то есть символ '0' не есть число 0, символ '0' есть число 48, * а символ '7', например, есть число 55 * В целом всё вот так: '0' это 48 '1' это 49 '2' это 50 '3' это 51 '4' это 52 '5' это 53 '6' это 54 '7' это 55 '8' это 56 '9' это 57 * то есть значения не совпадают. Однако есть нюанс: совпадает порядок * поэтому, если прибавить символ '0' к номеру колонки, то получим символ, означающий номер колонки. Потому что C# интерпретирует '0' как число 48 и сложит его с номером колонки * важно понимать: '0' - это символ, а "0" - это строка из одного символа. Повеедение у них оттличается: * когда делаем "0" + row - это мы к строке "0" добавим номер строки, и получим что-то в духе "03", то есть оно превратит row в строку и потом просто стыкует их (конкатенация) * когда делаем '0' + row - это мы к числу 48 прибавим номер строки, и получим, например, 51. То есть оно '0' превращает в число, и потом складывает два числа * * Поэтому преобразование номера строки в символ, который означает номер строки, имеет вид: * (char)(row + '0') * Но у нас номера надо выводить не с нуля, а с единицы, поэтому смещаемся ещё на 1: * (char)(row + '0' + 1) */ //Получили символ номера строки и символ номера колонки //Теперь сохраним их в виде пары в одну переменную var numberPair = (rowChar, columnChar); //Так можно объединять несколько значений, т.е. можно, например, написать var number = (3,2); //Взяли тот символ, например, 'A' или 'H' //И использовали его как номер в массиве //В этом случае C# интерпретирует symbol как число //К примеру, 'A' - это 65 linearTableMap[symbol] = numberPair; } //Теперь для любой существующей буквы у нас есть пара символов (не цифр, а сразу букв!), означающая строку и столбец в таблице Полибия при нумерации с 1 //Если в таблице Полибия такой буквы нет, то значения в карте будут равны паре особых непечатаемых символов, означающих отсутствие символа //Ещё щепотка магии: вносим в карту пробел, и говорим, //что его пара символов - это не всякие '1', '2', '3' и прочее, а символы переноса строки //так мы добъёмся того, что пробелы будут заменяться на переносы строки { var nl = Environment.NewLine; //Символ новой строки в Windows состоит из двух символов, в Linux из одного if (nl.Length == 2) linearTableMap[' '] = (nl[0], nl[1]); else linearTableMap[' '] = (' ', nl[0]); } //и происходить это будет по той же таблице } /*А это карта обратного преобразования пар чисел в букву * тут всё хитрее: * каждая буква у нас - это два символа-числа. * 1) делаем метод, который принимает на вход сразу два символа и возвращает уникальный номер в карте, по которому дёргаем символ * 2) но размер карты получится суровым: поскольку всех существующих символов 65536, то всех возможных комбинаций пар этих символов 65536 * 65536 = 4 294 967 296, то есть больше 4 миллиардов * 3) карта у нас - это массив char ов, каждый char занимает 2 байта. Соответственно, нам понадобится 8.6 ГБайт оперативной памяти, чтобы вместить всё * 4) это слишком сурово на сегодняшний день, поэтому попытаемся уменьшить объем, зарезав функционал * 5) если интерпретировать символы как числа, то из русского и английского алфавитов-цифр-знаков препинания самое большое значение * имеет строчная буква 'ё', она равна 1105. Все остальные потенциальные символы меньше. * 6) Поэтому мы спокойно делаем карту длиной не 65536*65536 значенйи, а всего лишь 1105*1105 значений. Это чуть больше миллиона * 7) Символ пробела ' ' есть число 32 * 8) Символы перевода строки обычно числа 10 и 13 */ const int biggestCharWhatAllowed = 'ё' + 1; //Функция, преобразуюущая два символа в номер в карте. Действие основано на интерпретации символа как числа static int rowColumnCharsToAntimapIndex(char row, char column) => row * biggestCharWhatAllowed + column; //Длина карты обратного преобразования (дешифровки) const int antimapLength = biggestCharWhatAllowed * biggestCharWhatAllowed; //сама карта обратного преобразования readonly char[] linearAntimap = new char[linearTableLength]; void rebuildAntimap() { //очищаем карту Array.Clear(linearAntimap, 0, linearTableLength); //проходим по таблице for (int row = 0; row < table.GetLength(0); row++) { char rowChar = (char)('1' + row); //Преобразуем номер строки в символ, означающий номер строки при нумерации с 1 for (int column = 0; column < table.GetLength(1); column++) { char columnChar = (char)(column + '1'); //Преобразуем номер столбца в символ, означающий номер столбца при нумерации с 1 //Получаем номер в карте var index = rowColumnCharsToAntimapIndex(rowChar, columnChar); //Указываем, что по этому номеру у нас символ из таблицы linearAntimap[index] = table[row, column]; } } //Делаем магию для того, чтобы символы перевода строки превращались в пробелы if (Environment.NewLine.Length == 1) { //Если длина символа перевода строки в данной операционной системе равна 1 //То перебираем все возможные комбинации этого символа со всеми возможными номерами и пробелом var index = rowColumnCharsToAntimapIndex(Environment.NewLine[0], ' '); linearAntimap[index] = ' '; for (int number = 0; number < 9; number++) { //по этой комбинации находим индекс index = rowColumnCharsToAntimapIndex(Environment.NewLine[0], (char)(number + '1')); //и говорим интерпретировать эту комбинацию как пробел linearAntimap[index] = ' '; } } else { //Если длина символа перевода строки в данной операционной системе равна 2 //то говорим, что данная пара символов - это пробел var index = rowColumnCharsToAntimapIndex(Environment.NewLine[0], Environment.NewLine[1]); linearAntimap[index] = ' '; } } /// <summary> /// Шифровка /// </summary> public string Encrypt(string text) { if (string.IsNullOrWhiteSpace(text)) return string.Empty; //Штука для быстрого составления строк var r = new StringBuilder(); //Перебираем все символы текста foreach (char c in text) { /*Интерпретируя каждый символ как число * выдёргиваем пару строка-столбец из карты-массива для этого символа */ var (row, column) = linearTableMap[c]; //row и column - это не числа, это уже сразу символы, означающие номера //потому что мы заранее сделали это преобразование при составлении карты //и карту составляли с символами, а не числами if (row == '\0') // '\0' это не '0'. '\0' это особый непечатаемый символ, числовое значение которого как раз равно 0. Напомню, у '0' числовое значение это 48. Когда мы обнуляли массивы charов, они все выставились в значение '\0' throw new Exception($"Ошибка! Символ {c} не поддерживается!"); r.Append(row); //Добавляем номер строки r.Append(column); //Добавляем номер столбца r.Append(' '); //Пробел } return r.ToString(); } /// <summary> /// Дешифровка /// </summary> public string Decrypt(string quad) { if (string.IsNullOrWhiteSpace(quad)) return string.Empty; var r = new StringBuilder(); /*Перебираем все символы начиная со ВТОРОГО, храним предыдущий символ и текущий * Тут нам типо как бы надо сначала разделить всё на строки, потом на пары чисел, разделённых пробелами * и только потом начинать распознавание. Но вместо этого мы опять делаем немного уличной магии * мы тупо перебираем все символы по одному, но начинаем не с нулевого, а с первого * * если текущий символ и предыдущий - это числа, значит мы должны распознать букву и добавить её к тексту * если текущий символ и предыдущий - это перевод строки, значит мы должны добавить пробел к тексу * в остальных случаях тупо идём дальше. То есть когда у нас встретилось "55" или "31" мы думаем и делаем дело * а когда встретилось "5 " или " 3" - это значит мы ещё недостаточно сместились, поэтому тупо идём дальше * то есть мы берем два символа, если это пара чисел или новая строка - делаем дело, если нет - мы понимаем, * что это мусор, и идём дальше * * это первое. Второе: нам ничего из этого проверять не надо, ибо у нас таблица. * Вот мы бежим по тексту и втупую берём комбинации пар символов. Нам будут попадаться и осмысленные пары символов-цифр * и всякий мусор, в котором один символ пробел, а второй число, или перевод строки, или ещё что-нибудь * Наша карта обратного преобразования составлена для всех возможных комбинаций символов вплоть до буквы 'ё' включительно * Поэтому все мусорные пары в ней тоже встретятся - все комбинации пробелов, запятых, переводов строки, букв и цифр * Напоминаю: берем пару символов, считаем для них индекс, и по нему дёргаем из массива результирующий дешифрованый символ * Так вот, для всех мусорных индексов в нашей карте проставлено '\0' - непечатаемый символ, означающий отсутствие символа * Это произошло когда мы сделали для нашей карты Array.Clear * А для нормальных комбинаций в духе ('5','3') в карте есть соотвествующая буква, а не '\0' * Поэтому всё что нам надо делать: * 1) без оглядки, без проверок просто брать два символа из строки * 2) считать для них индекс * 3) по нему дёргать символ из карты обратного преобразования * 4) если этот символ не '\0', то добавлять к результату * * о пробелах мы тоже позаботились при составлении карты обратного преобразования - все комбинации символа перевода строки * в карте проставлены как пробелы */ //В этой переменной храним предыдущий символ. В самом начале это будет первый символ строки char prevousChar = quad[0]; //Перебираем все символы текста начиная со 2 for (int charIndex = 1; charIndex < quad.Length; charIndex++) { //Берем текущий символ var currentChar = quad[charIndex]; //Вычисляем номер в карте-массиве обратного преобразования var index = rowColumnCharsToAntimapIndex(prevousChar, currentChar); //Тупо вытаскиваем из карты обратного преобразования имвол var symbol = linearAntimap[index]; //Если это что-то годное, то добавляем к строке if (symbol != '\0') r.Append(symbol); //Обновляем предыдущий символ prevousChar = currentChar; } return r.ToString(); } /// <summary> /// Тестирование: возвращает дешифровку шифрованного текста. Должна получиться исходная строка /// </summary> public string Test(string text) => Decrypt(Encrypt(text)); }Использование:
var p = new PolybiusQuad(); /*Если надо задать особую таблицу: p.Table = new char[,] { { 'B', 'A', 'C', 'D','E' }, { 'F', 'G', 'H', 'I', 'K' }, { 'L', 'M', 'N', 'O', 'P' }, { 'Q', 'R', 'S', 'T', 'U' }, { 'V', 'W', 'X', 'Y', 'Z' }, };*/ //Далее шифруем/дешифруем: var encryptedStr = p.Encrypt("MAMA MILA RAMY"); var decryptedStr = p.Decrypt(encryptedStr);
colussus
02.11.2023 13:14+1Если говорить просто об оптимизированном кодировании последовательности символов по этой таблице, то это можно было бы реализовать как-то вот так:
using System; using System.Collections.Generic; using System.Linq; using System.Text; class PolybiusSquare { public static IEnumerable<byte> Encrypt(string str) { int i = 0, strLen = str.Length; byte[] enc = new byte[strLen]; foreach (char c in str) { int n = Char.ToLower(c) - 'a'; if (n < 0 || n > 25) { continue; } if (n > 8) { --n; } enc[i] = (byte)((n / 5 + 1) * 10 + (n % 5 + 1)); ++i; } return enc.Take(i); } public static StringBuilder Decrypt(IEnumerable<byte> enc) { var dec = new StringBuilder(enc.Count()); foreach (byte b in enc) { int n = (b / 10 - 1) * 5 + (b % 10 - 1); if (n > 8) { ++n; } dec.Append((char)('a' + n)); } return dec; } public static void Main() { var str = "abcdefghijklmnopqrstuvwxyz"; Console.Write("str: {0}\nenc: ", str); var enc = Encrypt(str); foreach (byte b in enc) { Console.Write("{0} ", b); } var dec = Decrypt(enc); Console.WriteLine("\ndec: {0}", dec.ToString()); } }
Ratenti
02.11.2023 13:14Для курсовой или РГР в ВУЗе писал?
HotMilkTicTac Автор
02.11.2023 13:14Нет, для колледжа. А точнее надо было выполнить задачку и сделать по ней отчет
colussus
Если говорить просто об оптимизированном кодировании последовательности символов по этой таблице, то это можно было бы реализовать как-то вот так: