Всем привет! Сегодня рассмотрим пример, хеширования разными алгоритмами с добавлением так называемой salt соли. Salt это всего лишь несколько бит информации прибавленной к вашему паролю к примеру. Как это выглядит допустим у вас пароль 12345+qwe. Где qwe и есть соль, но все это проходит обертку хеш алгоритмом, и приобретает не читабельный вид. Однако имеются приложения […]
Рубрика: Алгоритмы
Реализация алгоритмов на C#
Пример реализации жадного алгоритма на C#
В этом примере мы обсудим оптимальное решение для решения проблемы размена денег с помощью жадного алгоритма. Жадный алгоритм-это тот, который всегда выбирает лучшее решение в то время, без учета того, как этот выбор повлияет на будущие выборы. Здесь мы обсудим, как использовать жадный алгоритм для размена денег. Было доказано, что оптимальное решение для размена денег […]
Кодирование по алгоритму Хаффмана с помощью словаря на C#
Кодирование Хаффмана-это алгоритм сжатия данных без потерь. Идея заключается в том, чтобы присвоить коды переменной длины входным символам, длины присвоенных кодов основаны на частотах соответствующих символов. Самый частый символ получает наименьший код, а наименее частый символ — самый большой код. Node.cs :
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace HuffmanTest { public class Node { public char Symbol { get; set; } public int Frequency { get; set; } public Node Right { get; set; } public Node Left { get; set; } public List<bool> Traverse(char symbol, List<bool> data) { // Leaf if (Right == null && Left == null) { if (symbol.Equals(this.Symbol)) { return data; } else { return null; } } else { List<bool> left = null; List<bool> right = null; if (Left != null) { List<bool> leftPath = new List<bool>(); leftPath.AddRange(data); leftPath.Add(false); left = Left.Traverse(symbol, leftPath); } if (Right != null) { List<bool> rightPath = new List<bool>(); rightPath.AddRange(data); rightPath.Add(true); right = Right.Traverse(symbol, rightPath); } if (left != null) { return left; } else { return right; } } } } } |
HuffmanTree.cs :
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; namespace HuffmanTest { public class HuffmanTree { private List<Node> nodes = new List<Node>(); public Node Root { get; set; } public Dictionary<char, int> Frequencies = new Dictionary<char, int>(); public void Build(string source) { for (int i = 0; i < source.Length; i++) { if (!Frequencies.ContainsKey(source[i])) { Frequencies.Add(source[i], 0); } Frequencies[source[i]]++; } foreach (KeyValuePair<char, int> symbol in Frequencies) { nodes.Add(new Node() { Symbol = symbol.Key, Frequency = symbol.Value }); } while (nodes.Count > 1) { List<Node> orderedNodes = nodes.OrderBy(node => node.Frequency).ToList<Node>(); if (orderedNodes.Count >= 2) { // Take first two items List<Node> taken = orderedNodes.Take(2).ToList<Node>(); // Create a parent node by combining the frequencies Node parent = new Node() { Symbol = '*', Frequency = taken[0].Frequency + taken[1].Frequency, Left = taken[0], Right = taken[1] }; nodes.Remove(taken[0]); nodes.Remove(taken[1]); nodes.Add(parent); } this.Root = nodes.FirstOrDefault(); } } public BitArray Encode(string source) { List<bool> encodedSource = new List<bool>(); for (int i = 0; i < source.Length; i++) { List<bool> encodedSymbol = this.Root.Traverse(source[i], new List<bool>()); encodedSource.AddRange(encodedSymbol); } BitArray bits = new BitArray(encodedSource.ToArray()); return bits; } public string Decode(BitArray bits) { Node current = this.Root; string decoded = ""; foreach (bool bit in bits) { if (bit) { if (current.Right != null) { current = current.Right; } } else { if (current.Left != null) { current = current.Left; } } if (IsLeaf(current)) { decoded += current.Symbol; current = this.Root; } } return decoded; } public bool IsLeaf(Node node) { return (node.Left == null && node.Right == null); } } } |
Program.cs:
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; namespace HuffmanTest { class Program { static void Main(string[] args) { Console.WriteLine("Please enter the string:"); string input = Console.ReadLine(); HuffmanTree huffmanTree = new HuffmanTree(); // Build the Huffman tree huffmanTree.Build(input); // Encode BitArray encoded = huffmanTree.Encode(input); Console.Write("Encoded: "); foreach (bool bit in encoded) { Console.Write((bit ? 1 : 0) + ""); } Console.WriteLine(); // Decode string decoded = huffmanTree.Decode(encoded); Console.WriteLine("Decoded: " + decoded); Console.ReadLine(); } } } |
C# — поиск в глубину(DFS) с помощью списка.
Поиск в глубине (DFS) — это алгоритм для обхода или поиска структур данных дерева или графика. Он начинает с корня (выбирая некоторый произвольный узел в качестве корня в случае графа) и исследует как можно дальше вдоль каждой ветви, прежде чем вернуться назад.
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace DefthFirst { class Program { public class Employee { public Employee(string name) { this.name = name; } public string name { get; set; } public List<Employee> Employees { get { return EmployeesList; } } public void isEmployeeOf(Employee e) { EmployeesList.Add(e); } List<Employee> EmployeesList = new List<Employee>(); public override string ToString() { return name; } } public class DepthFirstAlgorithm { public Employee BuildEmployeeGraph() { Employee Eva = new Employee("Eva"); Employee Sophia = new Employee("Sophia"); Employee Brian = new Employee("Brian"); Eva.isEmployeeOf(Sophia); Eva.isEmployeeOf(Brian); Employee Lisa = new Employee("Lisa"); Employee Tina = new Employee("Tina"); Employee John = new Employee("John"); Employee Mike = new Employee("Mike"); Sophia.isEmployeeOf(Lisa); Sophia.isEmployeeOf(John); Brian.isEmployeeOf(Tina); Brian.isEmployeeOf(Mike); return Eva; } public Employee Search(Employee root, string nameToSearchFor) { if (nameToSearchFor == root.name) return root; Employee personFound = null; for (int i = 0; i < root.Employees.Count; i++) { personFound = Search(root.Employees[i], nameToSearchFor); if (personFound != null) break; } return personFound; } public void Traverse(Employee root) { Console.WriteLine(root.name); for (int i = 0; i < root.Employees.Count; i++) { Traverse(root.Employees[i]); } } } static void Main(string[] args) { DepthFirstAlgorithm b = new DepthFirstAlgorithm(); Employee root = b.BuildEmployeeGraph(); Console.WriteLine("Пересечения графа\n------"); b.Traverse(root); Console.WriteLine("\nПоиск в графе\n------"); Employee e = b.Search(root, "Eva"); Console.WriteLine(e == null ? "Сотрудник, не найден" : e.name); e = b.Search(root, "Brian"); Console.WriteLine(e == null ? "Сотрудник, не найден" : e.name); e = b.Search(root, "Soni"); Console.WriteLine(e == null ? "Сотрудник, не найден" : e.name); Console.ReadKey(); } } } |
Вывод: Пересечения графа Eva Sophia Lisa John Brian Tina Mike Поиск в […]
C# — поиск в ширину (BFS) с использованием очереди.
В этом примере мы напишем программу на языке C# для реализации поиска в ширину (BFS) с помощью Queue Поиск в ширину (BFS) — это алгоритм для обхода или поиска структур данных дерева или графа. Он начинается с корня дерева (или некоторого произвольного узла графа) и сначала исследует соседние узлы, прежде чем перейти к соседям следующего […]