Классические алгоритмы с примерами на C++

#include <iostream>
#include <vector>

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                std::swap(arr[j], arr[j+1]);
            }
        }
    }
}

int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

#include <iostream>
#include <vector>

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i+1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, arr.size()-1);
    
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;
    
    int result = binarySearch(arr, target);
    if (result != -1) {
        std::cout << "Элемент найден на позиции: " << result << std::endl;
    } else {
        std::cout << "Элемент не найден" << std::endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>

void BFS(const std::vector<std::vector<int>>& graph, int start) {
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> q;
    
    visited[start] = true;
    q.push(start);
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        std::cout << current << " ";
        
        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // Граф в виде списка смежности
    std::vector<std::vector<int>> graph = {
        {1, 2},     // 0
        {0, 3, 4},  // 1
        {0, 4},     // 2
        {1, 5},     // 3
        {1, 2},     // 4
        {3}         // 5
    };
    
    std::cout << "BFS обход: ";
    BFS(graph, 0);
    return 0;
}

#include <iostream>
#include <vector>
#include <stack>

class Graph {
    int V; // количество вершин
    std::vector<std::vector<int>> adj;
    
public:
    Graph(int V) : V(V), adj(V) {}
    
    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }
    
    void DFS(int start) {
        std::vector<bool> visited(V, false);
        std::stack<int> stack;
        
        stack.push(start);
        
        while (!stack.empty()) {
            int current = stack.top();
            stack.pop();
            
            if (!visited[current]) {
                std::cout << current << " ";
                visited[current] = true;
            }
            
            for (auto it = adj[current].rbegin(); it != adj[current].rend(); ++it) {
                if (!visited[*it]) {
                    stack.push(*it);
                }
            }
        }
    }
};

// Пример использования
int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    
    std::cout << "DFS обход: ";
    g.DFS(0);
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

void dijkstra(const std::vector<std::vector<std::pair<int, int>>>& graph, int start) {
    int n = graph.size();
    std::vector<int> dist(n, INT_MAX);
    std::priority_queue<std::pair<int, int>, 
                       std::vector<std::pair<int, int>>, 
                       std::greater<std::pair<int, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        int current_dist = pq.top().first;
        pq.pop();
        
        if (current_dist > dist[u]) continue;
        
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    std::cout << "Кратчайшие расстояния от вершины " << start << ":\n";
    for (int i = 0; i < n; i++) {
        std::cout << "До " << i << ": " << dist[i] << std::endl;
    }
}

int main() {
    // Граф: список смежности (вершина, вес)
    std::vector<std::vector<std::pair<int, int>>> graph = {
        {{1, 4}, {2, 1}},          // 0
        {{3, 2}},                   // 1
        {{1, 2}, {3, 5}},           // 2
        {{4, 3}},                   // 3
        {}                          // 4
    };
    
    dijkstra(graph, 0);
    return 0;
}

#include <iostream>
#include <vector>

// Рекурсивный подход (медленный)
int fibonacciRecursive(int n) {
    if (n <= 1) return n;
    return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);
}

// Динамическое программирование (быстрый)
int fibonacciDP(int n) {
    if (n <= 1) return n;
    
    std::vector<int> dp(n+1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}

int main() {
    int n = 10;
    std::cout << "F(" << n << ") = " << fibonacciDP(n) << std::endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

struct Item {
    int weight;
    int value;
    double ratio; // value/weight
};

bool compare(Item a, Item b) {
    return a.ratio > b.ratio;
}

double fractionalKnapsack(int capacity, std::vector<Item>& items) {
    // Сортируем предметы по убыванию value/weight
    for (auto& item : items) {
        item.ratio = (double)item.value / item.weight;
    }
    std::sort(items.begin(), items.end(), compare);
    
    double totalValue = 0.0;
    int currentWeight = 0;
    
    for (const auto& item : items) {
        if (currentWeight + item.weight <= capacity) {
            currentWeight += item.weight;
            totalValue += item.value;
        } else {
            int remaining = capacity - currentWeight;
            totalValue += item.value * ((double)remaining / item.weight);
            break;
        }
    }
    
    return totalValue;
}

int main() {
    std::vector<Item> items = {
        {10, 60}, // weight, value
        {20, 100},
        {30, 120}
    };
    int capacity = 50;
    
    double maxValue = fractionalKnapsack(capacity, items);
    std::cout << "Максимальная стоимость: " << maxValue << std::endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9, 3};
    
    // Сортировка
    std::sort(numbers.begin(), numbers.end());
    
    // Поиск
    auto it = std::find(numbers.begin(), numbers.end(), 8);
    if (it != numbers.end()) {
        std::cout << "Найдено: " << *it << std::endl;
    }
    
    // Сумма элементов
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
    std::cout << "Сумма: " << sum << std::endl;
    
    // Максимальный элемент
    int max = *std::max_element(numbers.begin(), numbers.end());
    std::cout << "Максимум: " << max << std::endl;
    
    return 0;
}

#include <iostream>
#include <vector>
#include <string>

std::vector<int> computeLPS(const std::string& pattern) {
    int m = pattern.length();
    std::vector<int> lps(m, 0);
    int len = 0;
    int i = 1;
    
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len-1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    return lps;
}

void KMPSearch(const std::string& text, const std::string& pattern) {
    int n = text.length();
    int m = pattern.length();
    
    std::vector<int> lps = computeLPS(pattern);
    
    int i = 0; // индекс для text
    int j = 0; // индекс для pattern
    
    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        
        if (j == m) {
            std::cout << "Найдено вхождение на позиции " << i - j << std::endl;
            j = lps[j-1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j-1];
            } else {
                i++;
            }
        }
    }
}

// Пример использования
int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    KMPSearch(text, pattern);
    return 0;
}