Модуль 12: Алгоритмы и структуры данных в C#

Примеры кода

Бинарный поиск

Эффективный алгоритм поиска в отсортированном массиве.

Сложность: O(log n)

public static int BinarySearch(int[] array, int target)
{
    int left = 0;
    int right = array.Length - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;

        // Проверяем, является ли средний элемент искомым
        if (array[mid] == target)
            return mid;

        // Если искомый элемент больше, игнорируем левую половину
        if (array[mid] < target)
            left = mid + 1;
        // Иначе игнорируем правую половину
        else
            right = mid - 1;
    }

    // Если элемент не найден
    return -1;
}

// Пример использования в Unity
public class BinarySearchExample : MonoBehaviour
{
    public int[] numbers = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
    public int targetNumber = 23;
    
    private void Start()
    {
        int result = BinarySearch(numbers, targetNumber);
        if (result != -1)
            Debug.Log($"Число {targetNumber} найдено по индексу {result}");
        else
            Debug.Log($"Число {targetNumber} не найдено в массиве");
    }
}

Быстрая сортировка (Quick Sort)

Эффективный алгоритм сортировки с использованием стратегии "разделяй и властвуй".

Сложность: В среднем O(n log n), в худшем случае O(n²)

public static void QuickSort(int[] array, int low, int high)
{
    if (low < high)
    {
        // Получаем индекс опорного элемента
        int partitionIndex = Partition(array, low, high);

        // Рекурсивно сортируем элементы до и после раздела
        QuickSort(array, low, partitionIndex - 1);
        QuickSort(array, partitionIndex + 1, high);
    }
}

private static int Partition(int[] array, int low, int high)
{
    // Выбираем опорный элемент (в данном случае последний элемент)
    int pivot = array[high];
    
    // Индекс меньшего элемента
    int i = low - 1;

    for (int j = low; j < high; j++)
    {
        // Если текущий элемент меньше или равен опорному
        if (array[j] <= pivot)
        {
            i++;
            // Меняем элементы местами
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    // Меняем опорный элемент с элементом, который больше опорного
    int temp1 = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp1;

    return i + 1;
}

// Пример использования в Unity
public class QuickSortExample : MonoBehaviour
{
    public int[] numbersToSort = { 64, 34, 25, 12, 22, 11, 90 };
    
    private void Start()
    {
        Debug.Log("До сортировки: " + string.Join(", ", numbersToSort));
        
        QuickSort(numbersToSort, 0, numbersToSort.Length - 1);
        
        Debug.Log("После сортировки: " + string.Join(", ", numbersToSort));
    }
}

Представление графа и обход в ширину (BFS)

Реализация графа с использованием списка смежности и алгоритма обхода в ширину.

Сложность BFS: O(V + E), где V - количество вершин, E - количество рёбер

using System.Collections.Generic;
using UnityEngine;

public class Graph
{
    private Dictionary> adjacencyList;
    private int vertices;

    public Graph(int v)
    {
        vertices = v;
        adjacencyList = new Dictionary>();
        
        for (int i = 0; i < v; i++)
        {
            adjacencyList[i] = new List();
        }
    }

    // Добавление ребра в граф
    public void AddEdge(int v, int w)
    {
        adjacencyList[v].Add(w);
    }

    // Обход в ширину (BFS) начиная с вершины s
    public List BFS(int s)
    {
        // Массив для отслеживания посещённых вершин
        bool[] visited = new bool[vertices];
        Queue queue = new Queue();
        List result = new List();

        // Помечаем текущую вершину как посещённую и ставим в очередь
        visited[s] = true;
        queue.Enqueue(s);

        while (queue.Count > 0)
        {
            // Извлекаем вершину из очереди и добавляем в результат
            s = queue.Dequeue();
            result.Add(s);

            // Получаем все смежные вершины текущей вершины
            foreach (int neighbor in adjacencyList[s])
            {
                if (!visited[neighbor])
                {
                    visited[neighbor] = true;
                    queue.Enqueue(neighbor);
                }
            }
        }

        return result;
    }
}

// Пример использования в Unity
public class GraphExample : MonoBehaviour
{
    private void Start()
    {
        // Создаём граф с 4 вершинами
        Graph g = new Graph(4);

        // Добавляем рёбра
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(2, 3);
        g.AddEdge(3, 3);

        Debug.Log("Обход в ширину, начиная с вершины 2:");
        List bfsResult = g.BFS(2);
        Debug.Log("Порядок обхода: " + string.Join(" -> ", bfsResult));
    }
}

Алгоритм A* для поиска пути

Эффективный алгоритм поиска пути в графе с эвристической функцией.

Сложность: Зависит от эвристики, в худшем случае O(b^d), где b - коэффициент ветвления, d - глубина решения

using System.Collections.Generic;
using UnityEngine;

public class AStarPathfinding : MonoBehaviour
{
    public class Node
    {
        public Vector2Int Position { get; set; }
        public int GCost { get; set; } // Расстояние от старта
        public int HCost { get; set; } // Эвристическая оценка до цели
        public int FCost => GCost + HCost; // Общая стоимость
        public Node Parent { get; set; }
        public bool IsWalkable { get; set; } = true;
    }

    public static List FindPath(Node[,] grid, Vector2Int startPos, Vector2Int targetPos)
    {
        Node startNode = grid[startPos.x, startPos.y];
        Node targetNode = grid[targetPos.x, targetPos.y];

        List openSet = new List();
        HashSet closedSet = new HashSet();
        openSet.Add(startNode);

        while (openSet.Count > 0)
        {
            // Находим узел с наименьшей F-стоимостью
            Node currentNode = openSet[0];
            for (int i = 1; i < openSet.Count; i++)
            {
                if (openSet[i].FCost < currentNode.FCost || 
                   (openSet[i].FCost == currentNode.FCost && openSet[i].HCost < currentNode.HCost))
                {
                    currentNode = openSet[i];
                }
            }

            openSet.Remove(currentNode);
            closedSet.Add(currentNode);

            // Если достигли цели
            if (currentNode == targetNode)
            {
                return RetracePath(startNode, targetNode);
            }

            // Проверяем соседей
            foreach (Node neighbor in GetNeighbors(currentNode, grid))
            {
                if (!neighbor.IsWalkable || closedSet.Contains(neighbor))
                    continue;

                int newMovementCostToNeighbor = currentNode.GCost + GetDistance(currentNode, neighbor);
                if (newMovementCostToNeighbor < neighbor.GCost || !openSet.Contains(neighbor))
                {
                    neighbor.GCost = newMovementCostToNeighbor;
                    neighbor.HCost = GetDistance(neighbor, targetNode);
                    neighbor.Parent = currentNode;

                    if (!openSet.Contains(neighbor))
                        openSet.Add(neighbor);
                }
            }
        }

        return null; // Путь не найден
    }

    private static List RetracePath(Node startNode, Node endNode)
    {
        List path = new List();
        Node currentNode = endNode;

        while (currentNode != startNode)
        {
            path.Add(currentNode.Position);
            currentNode = currentNode.Parent;
        }

        path.Reverse();
        return path;
    }

    private static int GetDistance(Node nodeA, Node nodeB)
    {
        // Манхэттенское расстояние
        int dstX = Mathf.Abs(nodeA.Position.x - nodeB.Position.x);
        int dstY = Mathf.Abs(nodeA.Position.y - nodeB.Position.y);
        return 10 * (dstX + dstY);
    }

    private static List GetNeighbors(Node node, Node[,] grid)
    {
        List neighbors = new List();
        Vector2Int[] directions = {
            new Vector2Int(0, 1),   // Вверх
            new Vector2Int(1, 0),   // Вправо
            new Vector2Int(0, -1),  // Вниз
            new Vector2Int(-1, 0)   // Влево
        };

        foreach (Vector2Int dir in directions)
        {
            int checkX = node.Position.x + dir.x;
            int checkY = node.Position.y + dir.y;

            if (checkX >= 0 && checkX < grid.GetLength(0) && 
                checkY >= 0 && checkY < grid.GetLength(1))
            {
                neighbors.Add(grid[checkX, checkY]);
            }
        }

        return neighbors;
    }
}

// Пример использования в Unity
public class PathfindingExample : MonoBehaviour
{
    public Vector2Int gridSize = new Vector2Int(10, 10);
    public Vector2Int startPos = new Vector2Int(0, 0);
    public Vector2Int targetPos = new Vector2Int(9, 9);
    
    private void Start()
    {
        // Создаём сетку
        AStarPathfinding.Node[,] grid = new AStarPathfinding.Node[gridSize.x, gridSize.y];
        
        // Инициализируем узлы сетки
        for (int x = 0; x < gridSize.x; x++)
        {
            for (int y = 0; y < gridSize.y; y++)
            {
                grid[x, y] = new AStarPathfinding.Node
                {
                    Position = new Vector2Int(x, y),
                    GCost = int.MaxValue,
                    HCost = 0,
                    IsWalkable = true
                };
            }
        }
        
        // Добавляем несколько препятствий (для примера)
        for (int i = 2; i < 8; i++)
        {
            grid[i, 5].IsWalkable = false;
        }
        
        // Находим путь
        List path = AStarPathfinding.FindPath(grid, startPos, targetPos);
        
        if (path != null)
        {
            string pathString = "";
            foreach (Vector2Int pos in path)
            {
                pathString += $"({pos.x},{pos.y}) -> ";
            }
            pathString = pathString.TrimEnd("-> ".ToCharArray());
            
            Debug.Log("Найден путь: " + pathString);
        }
        else
        {
            Debug.Log("Путь не найден!");
        }
    }
}

Оптимизация с помощью мемоизации (на примере чисел Фибоначчи)

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

Сложность без мемоизации: O(2^n)
Сложность с мемоизацией: O(n)

using System.Collections.Generic;
using UnityEngine;

public class MemoizationExample : MonoBehaviour
{
    // Классическая рекурсивная реализация (очень неэффективная)
    public static int FibonacciRecursive(int n)
    {
        if (n <= 1)
            return n;
            
        return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
    }

    // Оптимизированная версия с мемоизацией
    private static Dictionary _memo = new Dictionary();
    
    public static long FibonacciMemoized(int n)
    {
        if (n <= 1)
            return n;
            
        // Если значение уже было вычислено, возвращаем его из кэша
        if (_memo.ContainsKey(n))
            return _memo[n];
            
        // Иначе вычисляем и сохраняем в кэш
        long result = FibonacciMemoized(n - 1) + FibonacciMemoized(n - 2);
        _memo[n] = result;
        
        return result;
    }
    
    // Итеративная версия (самая эффективная по памяти)
    public static long FibonacciIterative(int n)
    {
        if (n <= 1)
            return n;
            
        long a = 0, b = 1, result = 0;
        
        for (int i = 2; i <= n; i++)
        {
            result = a + b;
            a = b;
            b = result;
        }
        
        return result;
    }
    
    private void Start()
    {
        int n = 40; // Для больших значений разница будет очень заметна
        
        // Тестируем рекурсивную версию (очень медленно для n > 40)
        // long resultRecursive = FibonacciRecursive(n);
        // Debug.Log($"Рекурсивно: Fib({n}) = {resultRecursive}");
        
        // Тестируем версию с мемоизацией
        System.Diagnostics.Stopwatch stopwatch = System.Diagnostics.Stopwatch.StartNew();
        long resultMemoized = FibonacciMemoized(n);
        stopwatch.Stop();
        Debug.Log($"Мемоизация: Fib({n}) = {resultMemoized} (за {stopwatch.ElapsedMilliseconds} мс)");
        
        // Тестируем итеративную версию
        stopwatch.Restart();
        long resultIterative = FibonacciIterative(n);
        stopwatch.Stop();
        Debug.Log($"Итеративно: Fib({n}) = {resultIterative} (за {stopwatch.ElapsedMilliseconds} мс)");
    }
}

// Пример использования мемоизации для кэширования результатов тяжёлых вычислений
public class ExpensiveCalculation
{
    private Dictionary _cache = new Dictionary();
    
    public float CalculateExpensiveValue(float param1, float param2)
    {
        // Создаём ключ кэша на основе параметров
        string cacheKey = $"{param1}_{param2}";
        
        // Если результат уже есть в кэше, возвращаем его
        if (_cache.ContainsKey(cacheKey))
        {
            Debug.Log("Используем кэшированный результат");
            return _cache[cacheKey];
        }
        
        // Иначе выполняем тяжёлые вычисления
        Debug.Log("Выполняем тяжёлые вычисления...");
        
        // Имитация сложных вычислений
        float result = 0;
        for (int i = 0; i < 1000000; i++)
        {
            result = Mathf.Sin(param1) * Mathf.Cos(param2);
        }
        
        // Сохраняем результат в кэш
        _cache[cacheKey] = result;
        
        return result;
    }
}