21. Алгоритмизация и структуры данных. Примеры задач.
1. Дейкстра с двоичной кучей.
Давайте попробуем существенно ускорить стандартный алгоритм Дейкстры, используя для выбора вершины с минимальным весом из не рассмотренных двоичную кучу.
2. Дерево поиска.
Вам повезло! Созданная вами игра набирает огромное количество пользователей. Но с некоторых пор игроки стали жаловаться, что приходится очень долго ждать авторизации на сервере. Проблема в том, что большое количество игроков существенно замедляет процесс проверки правильности логина и пароля конкретного пользователя. Сервер не справляется и ставит в очередь пытающихся залогиниться игроков. Давайте попробуем использовать бинарное дерево поиска для хранения и проверки логина и пароля игроков.
Задан список запросов к серверу. В каждом запросе сначала указывается логин, затем пароль и третьим параметром тип запроса: 0 – для авторизации, 1 – для регистрации. Программа должна быстро выводить логин и фразу «Доступ открыт!» или «Доступ запрещен» для каждого запроса авторизации.
3. Гороскоп.
Пользователь вводит число и месяц рождения. Программа выводит его знак зодиака и предсказание на 2022 год. Пользователей может быть очень много, поэтому надо попытаться максимально оптимизировать программу: в идеале до одной конструкции if для каждого пользователя.
Приложение к лекции.
using System;
using System.Collections.Generic;
namespace ConsoleApplication47
{
internal class Program
{
private static int[,] _graf;
private static List<Vertex> _list;
public class Vertex
{
public Vertex(int index, int distance)
{
Index = index;
Distance = distance;
}
public int Index;
public int Distance;
}
public static void Main(string[] args)
{
int start = 0;
int end = 0;
//Console.Write("Введите N=");
//int n = Convert.ToInt32(Console.ReadLine());
int n = 7;
int[,] graf = new int[n, n];
_list = new List<Vertex>();
//Console.Write("Введите M=");
//int m = Convert.ToInt32(Console.ReadLine());
int m = 10;
/*
for (int i = 0; i < m; i++)
{
Console.Write("Номер города, из которого идет дорога: ");
start = Convert.ToInt32(Console.ReadLine());
Console.Write("Номер города, в который идет дорога: ");
end = Convert.ToInt32(Console.ReadLine());
Console.Write("Номер города, в который идет дорога: ");
int size = Convert.ToInt32(Console.ReadLine());
graf[start, end] = size;
graf[end, start] = size;
}
*/
graf[0, 3] = 25;
graf[3, 0] = 25;
graf[0, 5] = 23;
graf[5, 0] = 23;
graf[0, 6] = 27;
graf[6, 0] = 27;
graf[1, 3] = 22;
graf[3, 1] = 22;
graf[1, 4] = 29;
graf[4, 1] = 29;
graf[2, 4] = 24;
graf[4, 2] = 24;
graf[2, 6] = 23;
graf[6, 2] = 23;
graf[3, 4] = 54;
graf[4, 3] = 54;
graf[4, 5] = 59;
graf[5, 4] = 59;
graf[4, 6] = 49;
graf[6, 4] = 49;
//Console.Write("Введите X=");
//start = Convert.ToInt32(Console.ReadLine());
start = 0;
//Console.Write("Введите Y=");
//end = Convert.ToInt32(Console.ReadLine());
end = 4;
int[] path = new int[n];
for (int i = 0; i < n; i++)
{
path[i] = Int32.MaxValue;
}
Boolean[] uses = new Boolean[n];
path[start] = 0;
int usesCount = 0;
Vertex ver = new Vertex(start, 0);
Add(ver);
while (usesCount < n)
{
/* int min = Int32.MaxValue;
int current = 0;
for (int i = 0; i < n; i++)
{
if (!uses[i] && path[i] < min)
{
min = path[i];
current = i;
}
}*/
int current = GetMax();
for (int i = 0; i < n; i++)
{
if (graf[current, i] > 0 && !uses[i])
{
if (path[current] + graf[current, i] < path[i])
{
path[i] = path[current] + graf[current, i];
Add(new Vertex(i, path[i]));
}
}
}
uses[current] = true;
usesCount++;
}
for (int i = 0; i < n; i++)
{
Console.WriteLine(i + " - " + path[i]);
}
Console.WriteLine("Ответ: " + path[end]);
}
private static void Add(Vertex value)
{
_list.Add(value);
int i = HeapSize() - 1;
int parent = (i - 1) / 2;
while (i > 0 && _list[parent].Distance > _list[i].Distance)
{
Vertex temp = _list[i];
_list[i] = _list[parent];
_list[parent] = temp;
i = parent;
parent = (i - 1) / 2;
}
}
private static void Heapify(int i)
{
int leftChild;
int rightChild;
int largestChild;
for (;;)
{
leftChild = 2 * i + 1;
rightChild = 2 * i + 2;
largestChild = i;
if (leftChild < HeapSize() && _list[leftChild].Distance < _list[largestChild].Distance)
{
largestChild = leftChild;
}
if (rightChild < HeapSize() && _list[rightChild].Distance < _list[largestChild].Distance)
{
largestChild = rightChild;
}
if (largestChild == i)
{
break;
}
Vertex temp = _list[i];
_list[i] = _list[largestChild];
_list[largestChild] = temp;
i = largestChild;
}
}
private static int GetMax()
{
int result = _list[0].Index;
_list[0] = _list[HeapSize() - 1];
_list.RemoveAt(HeapSize() - 1);
Heapify(0);
return result;
}
private static int HeapSize()
{
return _list.Count;
}
private static void Print()
{
int i = 0;
int k = 1;
while (i < HeapSize())
{
while ((i < k) && (i < HeapSize()))
{
Console.Write(_list[i].Distance + " ");
i++;
}
Console.WriteLine();
k = k * 2 + 1;
}
}
}
}using System;
using System.Collections.Generic;
namespace ConsoleApplication47
{
internal class Program
{
private static int[,] _graf;
public class User
{
public User(string login, string password)
{
Login = login;
Password = password;
}
public string Login;
public string Password;
}
public class Inquiry
{
public Inquiry(string login, string password, int type)
{
Login = login;
Password = password;
Type = type;
}
public string Login;
public string Password;
public int Type;
}
public static void Main(string[] args)
{
List<Inquiry> inquiries = new List<Inquiry>();
inquiries.Add(new Inquiry("admin", "12345", 1));
inquiries.Add(new Inquiry("user", "111", 1));
inquiries.Add(new Inquiry("Admin", "777", 1));
inquiries.Add(new Inquiry("admin", "12345", 0));
inquiries.Add(new Inquiry("user", "12345", 0));
inquiries.Add(new Inquiry("user", "111", 0));
inquiries.Add(new Inquiry("Sasha123", "12011995", 1));
inquiries.Add(new Inquiry("admin", "12345", 0));
inquiries.Add(new Inquiry("Sasha123", "12011995", 0));
inquiries.Add(new Inquiry("Sasha123", "12345", 0));
User first = new User("", "wjekljkljhsf234jhkh345h34h534j5h34kj5h3jh23j45jhewjhfsdlkjfg");
BinaryTree tree = new BinaryTree(first, null);
for (int i = 0; i < inquiries.Count; i++)
{
if (inquiries[i].Type == 1)
{
User user = new User(inquiries[i].Login, inquiries[i].Password);
tree.Add(user);
}
else
{
User user = new User(inquiries[i].Login, inquiries[i].Password);
if (tree.Search(user) == null)
{
Console.WriteLine("Элемент не найден!");
}
else
{
Console.WriteLine("Элемент найден!");
}
}
}
}
public class BinaryTree
{
private BinaryTree _parent, _left, _right;
private User _value;
public BinaryTree(User value, BinaryTree parent)
{
_value = value;
_parent = parent;
}
public void Add(User value)
{
if (String.Compare(value.Login, _value.Login) < 0)
{
if (_left == null)
{
_left = new BinaryTree(value, this);
}
else if (_left != null)
{
_left.Add(value);
}
}
else
{
if (_right == null)
{
_right = new BinaryTree(value, this);
}
else if (_right != null)
{
_right.Add(value);
}
}
}
private BinaryTree Search(BinaryTree tree, User value)
{
if (tree == null)
{
return null;
}
if (string.Compare(value.Login, tree._value.Login) == 0 &&
string.Compare(value.Password, tree._value.Password) == 0)
{
return tree;
}
if (string.Compare(value.Login, tree._value.Login) > 0)
{
return Search(tree._right, value);
}
else
{
return Search(tree._left, value);
}
}
public BinaryTree Search(User value)
{
return Search(this, value);
}
private void Print(BinaryTree node)
{
if (node == null) return;
Print(node._left);
Console.Write(node + " ");
if (node._right != null)
{
Print(node._right);
}
}
public void Print()
{
Print(this);
Console.WriteLine();
}
public override string ToString()
{
return _value.Login;
}
}
}
}using System;
namespace ConsoleApplication48
{
internal class Program
{
private class ZodiacSign
{
public ZodiacSign(int day, string sign)
{
Day = day;
Sign = sign;
}
public int Day;
public string Sign;
}
public static void Main(string[] args)
{
ZodiacSign[] signs = new ZodiacSign[13];
signs[0] = new ZodiacSign(19, "Козерог");
signs[1] = new ZodiacSign(18, "Водолей");
signs[2] = new ZodiacSign(20, "Рыбы");
signs[3] = new ZodiacSign(20, "Овен");
signs[4] = new ZodiacSign(20, "Телец");
signs[5] = new ZodiacSign(20, "Близнецы");
signs[6] = new ZodiacSign(22, "Рак");
signs[7] = new ZodiacSign(22, "Лев");
signs[8] = new ZodiacSign(23, "Дева");
signs[9] = new ZodiacSign(23, "Весы");
signs[10] = new ZodiacSign(21, "Скорпион");
signs[11] = new ZodiacSign(21, "Стрелец");
signs[12] = new ZodiacSign(32, "Козерог");
while (true)
{
Console.WriteLine("Для выхода введите 0!");
Console.Write("Введите номер дня рождения:");
int day = Convert.ToInt32(Console.ReadLine());
if (day == 0)
{
break;
}
Console.Write("Введите номер месяца рождения:");
int month = Convert.ToInt32(Console.ReadLine());
string prediction = "";
if (day <= signs[month - 1].Day)
{
prediction = signs[month - 1].Sign;
}
else
{
prediction = signs[month].Sign;
}
Console.WriteLine(prediction);
}
}
}
}Итоги занятия.
Мы заканчиваем блок, в котором только прикоснулись к огромному количеству алгоритмов и структур данных, придуманных для решения самых разных задач. К каждой задаче надо подобрать свой ключик, выбрать удобный вариант хранения данных, подобрать подходящий алгоритм. Но все алгоритмы знать невозможно! Да и нужно ли?! Гораздо интереснее самому (конечно, опираясь на изученные ранее алгоритмы и написанные программы) придумать быстрое, эффективное и короткое (ну, не всегда и короткое) решение для конкретной задачи. И самое главное, получить настоящий кайф от того, что получилось! Причем получилось очень даже неплохо… Порадовались? А вас уже ждет следующая задача… И опять проблемы и непростой поиск решения… Но это и есть путь… Настоящий путь программиста…