Общие методы в информатике и инженерии с примерами кода

Вот несколько методов, обычно используемых в области информатики и техники, а также примеры кода:

  1. Двоичный поиск.
    Двоичный поиск — это эффективный алгоритм поиска элемента в отсортированном списке. Вот пример реализации на Python:

    def binary_search(arr, target):
       low = 0
       high = len(arr) - 1
       while low <= high:
           mid = (low + high) // 2
           if arr[mid] == target:
               return mid
           elif arr[mid] < target:
               low = mid + 1
           else:
               high = mid - 1
       return -1
  2. Пузырьковая сортировка.
    Пузырьковая сортировка – это простой алгоритм сортировки, который многократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они расположены в неправильном порядке. Вот пример реализации на Java:

    public void bubbleSort(int[] arr) {
       int n = arr.length;
       for (int i = 0; i < n - 1; i++) {
           for (int j = 0; j < n - i - 1; j++) {
               if (arr[j] > arr[j + 1]) {
                   int temp = arr[j];
                   arr[j] = arr[j + 1];
                   arr[j + 1] = temp;
               }
           }
       }
    }
  3. Поиск в глубину.
    Поиск в глубину — это алгоритм обхода или поиска в структурах данных в виде дерева или графа. Вот пример реализации на C++:

    #include <iostream>
    #include <vector>
    using namespace std;
    void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
       visited[node] = true;
       cout << node << " ";
       for (int neighbor : graph[node]) {
           if (!visited[neighbor]) {
               dfs(graph, visited, neighbor);
           }
       }
    }
    int main() {
       int numNodes = 6;
       vector<vector<int>> graph(numNodes);
       vector<bool> visited(numNodes, false);
       // Add edges to the graph
       graph[0].push_back(1);
       graph[0].push_back(2);
       graph[1].push_back(3);
       graph[1].push_back(4);
       graph[2].push_back(4);
       graph[3].push_back(5);
       // Perform DFS starting from node 0
       dfs(graph, visited, 0);
       return 0;
    }
  4. Хеширование.
    Хеширование — это метод, используемый для сопоставления данных с массивом фиксированного размера, называемым хеш-таблицей. Обычно используется для быстрого получения данных. Вот пример реализации на C#:

    using System;
    using System.Collections.Generic;
    public class HashTable<TKey, TValue> {
       private const int TableSize = 100;
       private LinkedList<KeyValuePair<TKey, TValue>>[] table;
       public HashTable() {
           table = new LinkedList<KeyValuePair<TKey, TValue>>[TableSize];
       }
       private int GetHash(TKey key) {
           return Math.Abs(key.GetHashCode()) % TableSize;
       }
       public void Add(TKey key, TValue value) {
           int index = GetHash(key);
           if (table[index] == null) {
               table[index] = new LinkedList<KeyValuePair<TKey, TValue>>();
           }
           table[index].AddLast(new KeyValuePair<TKey, TValue>(key, value));
       }
       public TValue Get(TKey key) {
           int index = GetHash(key);
           if (table[index] != null) {
               foreach (KeyValuePair<TKey, TValue> pair in table[index]) {
                   if (pair.Key.Equals(key)) {
                       return pair.Value;
                   }
               }
           }
           throw new KeyNotFoundException("Key not found.");
       }
    }
    public class Program {
       public static void Main(string[] args) {
           HashTable<string, int> hashTable = new HashTable<string, int>();
           hashTable.Add("one", 1);
           hashTable.Add("two", 2);
           hashTable.Add("three", 3);
           int value = hashTable.Get("two");
           Console.WriteLine(value);  // Output: 2
       }
    }
  5. Алгоритм Дейкстры:
    Алгоритм Дейкстры — это алгоритм поиска кратчайшего пути между узлами в графе. Вот пример реализации на JavaScript:

    function dijkstra(graph, startNode) {
       const distances = {};
       const visited = {};
       const queue = [];
       distances[startNode] = 0;
       visited[startNode] = true;
       queue.push(startNode);
       while (queue.length) {
           const currentNode = queue.shift();
           for (const neighbor in graph[currentNode]) {
    I'm sorry, but it seems that the response got cut off. Here's the continuation of the example implementation of Dijkstra's Algorithm in JavaScript:
    ```javascript
               const distance = distances[currentNode] + graph[currentNode][neighbor];
    
               if (!distances[neighbor] || distance < distances[neighbor]) {
                   distances[neighbor] = distance;
                   visited[neighbor] = true;
                   queue.push(neighbor);
               }
           }
       }
    
       return distances;
    }
    
    const graph = {
       A: { B: 3, C: 2 },
       B: { A: 3, C: 1, D: 4 },
       C: { A: 2, B: 1, D: 2 },
       D: { B: 4, C: 2 },
    };
    
    const startNode = 'A';
    const shortestDistances = dijkstra(graph, startNode);
    console.log(shortestDistances);  // Output: { A: 0, B: 3, C: 2, D: 4 }