Теория графов

Теория графов (англ. graph theory) — это раздел дискретной математики, изучающий свойства графов. Граф представляет собой совокупность вершин (узлов) и рёбер (связей между вершинами).
Графы являются мощным инструментом для моделирования отношений в различных областях: от компьютерных сетей и социальных связей до транспортных систем и молекулярных структур.

Основные понятия:

Вершина (узел) - фундаментальная единица графа.
Ребро - связь между двумя вершинами.
Степень вершины - количество рёбер, инцидентных вершине (рёбра, которые крепятся к вершине).
Путь - последовательность вершин, соединённых рёбрами.
Цикл - путь, который начинается и заканчивается в одной вершине.

Умник

Отдельная история - хранение вещественных чисел.
Вещественные числа - это числа с дробной частью после запятой.

В математике вещественные числа могут бесконечными, а в компьютере мы не можем сохранить бесконечное число, т.к. ни одной оперативки не хватит.
А, кстати, как сохранить саму бесконечность?
Отрицательную бесконечность, положительную бесконечность?
Если вы уже проходили основы математического анализа, пределы и производные (а если нет, то узнаете, когда будете проходить), то ведь есть ещё и неопределенные операции, когда мы получаем "не число".
В простой арифметике младших классов школы (1 / 0) (один делить на ноль) - это "не число", в старших классах вы узнаете, что это можно считать бесконечностью. А вот если поделить бесконечность на бесконечность - опять получим "не число".

Ученые ломали голову над этими вопросами и в итоге придумали специальный формат хранения вещественных чисел с плавающей точкой (англ. floating point numbers). Этот формат описан в международном стандарте IEEE-754. А вы пока можете посмотреть в калькуляторе:

Представление графов в языках программирования

Графы можно представить несколькими способами: матрица смежности и список смежности. Ниже приведены примеры реализации для разных языков программирования.

Python

Матрица смежности

adjacency_matrix.py

# Граф с 4 вершинами (0, 1, 2, 3)
# Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # Инициализация матрицы смежности нулями
        self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]
    
    def add_edge(self, u, v, weight=1):
        # Добавление ребра между вершинами u и v с весом
        self.adj_matrix[u][v] = weight
        self.adj_matrix[v][u] = weight  # Для неориентированного графа
    
    def display(self):
        # Вывод матрицы смежности
        for row in self.adj_matrix:
            print(row)

# Создание графа
g = Graph(4)
g.add_edge(0, 1, 2)
g.add_edge(0, 2, 5)
g.add_edge(1, 2, 1)
g.add_edge(2, 3, 3)

# Вывод матрицы смежности
print("Матрица смежности:")
g.display()

Пояснение

Матрица смежности представляет собой двумерный список, где adj_matrix[i][j] содержит вес ребра между вершинами i и j. Если ребра нет, значение равно 0.

Список смежности

adjacency_list.py

# Граф с 4 вершинами (0, 1, 2, 3)
# Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # Инициализация списка смежности пустыми словарями
        self.adj_list = [{} for _ in range(num_vertices)]
    
    def add_edge(self, u, v, weight=1):
        # Добавление ребра между вершинами u и v с весом
        self.adj_list[u][v] = weight
        self.adj_list[v][u] = weight  # Для неориентированного графа
    
    def display(self):
        # Вывод списка смежности
        for i, neighbors in enumerate(self.adj_list):
            print(f"{i}: {neighbors}")

# Создание графа
g = Graph(4)
g.add_edge(0, 1, 2)
g.add_edge(0, 2, 5)
g.add_edge(1, 2, 1)
g.add_edge(2, 3, 3)

# Вывод списка смежности
print("Список смежности:")
g.display()

Пояснение

Список смежности представляет собой список словарей, где adj_list[i] содержит словарь с ключами - смежными вершинами, и значениями - весами соответствующих ребер.

C++

Матрица смежности

adjacency_matrix.cpp

#include <iostream>
#include <vector>

using namespace std;

class Graph {
private:
    int numVertices;
    vector<vector<int>> adjMatrix;

public:
    Graph(int vertices) : numVertices(vertices) {
        // Инициализация матрицы смежности нулями
        adjMatrix.resize(numVertices, vector<int>(numVertices, 0));
    }
    
    void addEdge(int u, int v, int weight = 1) {
        // Добавление ребра между вершинами u и v с весом
        adjMatrix[u][v] = weight;
        adjMatrix[v][u] = weight; // Для неориентированного графа
    }
    
    void display() {
        // Вывод матрицы смежности
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    // Граф с 4 вершинами (0, 1, 2, 3)
    // Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
    Graph g(4);
    g.addEdge(0, 1, 2);
    g.addEdge(0, 2, 5);
    g.addEdge(1, 2, 1);
    g.addEdge(2, 3, 3);
    
    // Вывод матрицы смежности
    cout << "Матрица смежности:" << endl;
    g.display();
    
    return 0;
}

Пояснение

Матрица смежности реализована как вектор векторов. adjMatrix[i][j] содержит вес ребра между вершинами i и j. Если ребра нет, значение равно 0.

Список смежности

adjacency_list.cpp

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Graph {
private:
    int numVertices;
    vector<unordered_map<int, int>> adjList;

public:
    Graph(int vertices) : numVertices(vertices) {
        // Инициализация списка смежности
        adjList.resize(numVertices);
    }
    
    void addEdge(int u, int v, int weight = 1) {
        // Добавление ребра между вершинами u и v с весом
        adjList[u][v] = weight;
        adjList[v][u] = weight; // Для неориентированного графа
    }
    
    void display() {
        // Вывод списка смежности
        for (int i = 0; i < numVertices; i++) {
            cout << i << ": ";
            for (auto& neighbor : adjList[i]) {
                cout << "(" << neighbor.first << ", " << neighbor.second << ") ";
            }
            cout << endl;
        }
    }
};

int main() {
    // Граф с 4 вершинами (0, 1, 2, 3)
    // Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
    Graph g(4);
    g.addEdge(0, 1, 2);
    g.addEdge(0, 2, 5);
    g.addEdge(1, 2, 1);
    g.addEdge(2, 3, 3);
    
    // Вывод списка смежности
    cout << "Список смежности:" << endl;
    g.display();
    
    return 0;
}

Пояснение

Список смежности реализован как вектор unordered_map, где adjList[i] содержит пары ключ-значение: ключ - смежная вершина, значение - вес ребра.

Java

Матрица смежности

AdjacencyMatrix.java

public class AdjacencyMatrix {
    private int numVertices;
    private int[][] adjMatrix;
    
    public AdjacencyMatrix(int vertices) {
        this.numVertices = vertices;
        // Инициализация матрицы смежности нулями
        this.adjMatrix = new int[numVertices][numVertices];
    }
    
    public void addEdge(int u, int v, int weight) {
        // Добавление ребра между вершинами u и v с весом
        adjMatrix[u][v] = weight;
        adjMatrix[v][u] = weight; // Для неориентированного графа
    }
    
    public void display() {
        // Вывод матрицы смежности
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        // Граф с 4 вершинами (0, 1, 2, 3)
        // Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
        AdjacencyMatrix g = new AdjacencyMatrix(4);
        g.addEdge(0, 1, 2);
        g.addEdge(0, 2, 5);
        g.addEdge(1, 2, 1);
        g.addEdge(2, 3, 3);
        
        // Вывод матрицы смежности
        System.out.println("Матрица смежности:");
        g.display();
    }
}

Пояснение

Матрица смежности реализована как двумерный массив. adjMatrix[i][j] содержит вес ребра между вершинами i и j. Если ребра нет, значение равно 0.

Список смежности

AdjacencyList.java

import java.util.*;

public class AdjacencyList {
    private int numVertices;
    private Map<Integer, Integer>[] adjList;
    
    @SuppressWarnings("unchecked")
    public AdjacencyList(int vertices) {
        this.numVertices = vertices;
        // Инициализация списка смежности
        this.adjList = new HashMap[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjList[i] = new HashMap<>();
        }
    }
    
    public void addEdge(int u, int v, int weight) {
        // Добавление ребра между вершинами u и v с весом
        adjList[u].put(v, weight);
        adjList[v].put(u, weight); // Для неориентированного графа
    }
    
    public void display() {
        // Вывод списка смежности
        for (int i = 0; i < numVertices; i++) {
            System.out.print(i + ": ");
            for (Map.Entry<Integer, Integer> entry : adjList[i].entrySet()) {
                System.out.print("(" + entry.getKey() + ", " + entry.getValue() + ") ");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        // Граф с 4 вершинами (0, 1, 2, 3)
        // Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
        AdjacencyList g = new AdjacencyList(4);
        g.addEdge(0, 1, 2);
        g.addEdge(0, 2, 5);
        g.addEdge(1, 2, 1);
        g.addEdge(2, 3, 3);
        
        // Вывод списка смежности
        System.out.println("Список смежности:");
        g.display();
    }
}

Пояснение

Список смежности реализован как массив HashMap, где adjList[i] содержит пары ключ-значение: ключ - смежная вершина, значение - вес ребра.

JavaScript

Матрица смежности

adjacency_matrix.js

class Graph {
    constructor(numVertices) {
        this.numVertices = numVertices;
        // Инициализация матрицы смежности нулями
        this.adjMatrix = Array.from({ length: numVertices }, () => 
            Array(numVertices).fill(0)
        );
    }
    
    addEdge(u, v, weight = 1) {
        // Добавление ребра между вершинами u и v с весом
        this.adjMatrix[u][v] = weight;
        this.adjMatrix[v][u] = weight; // Для неориентированного графа
    }
    
    display() {
        // Вывод матрицы смежности
        console.log("Матрица смежности:");
        for (let i = 0; i < this.numVertices; i++) {
            console.log(this.adjMatrix[i].join(' '));
        }
    }
}

// Граф с 4 вершинами (0, 1, 2, 3)
// Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
const g = new Graph(4);
g.addEdge(0, 1, 2);
g.addEdge(0, 2, 5);
g.addEdge(1, 2, 1);
g.addEdge(2, 3, 3);

// Вывод матрицы смежности
g.display();

Пояснение

Список смежности

adjacency_list.js

class Graph {
    constructor(numVertices) {
        this.numVertices = numVertices;
        // Инициализация списка смежности
        this.adjList = Array.from({ length: numVertices }, () => ({}));
    }
    
    addEdge(u, v, weight = 1) {
        // Добавление ребра между вершинами u и v с весом
        this.adjList[u][v] = weight;
        this.adjList[v][u] = weight; // Для неориентированного графа
    }
    
    display() {
        // Вывод списка смежности
        console.log("Список смежности:");
        for (let i = 0; i < this.numVertices; i++) {
            const neighbors = Object.entries(this.adjList[i])
                .map(([vertex, weight]) => `(${vertex}, ${weight})`)
                .join(' ');
            console.log(`${i}: ${neighbors}`);
        }
    }
}

// Граф с 4 вершинами (0, 1, 2, 3)
// Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
const g = new Graph(4);
g.addEdge(0, 1, 2);
g.addEdge(0, 2, 5);
g.addEdge(1, 2, 1);
g.addEdge(2, 3, 3);

// Вывод списка смежности
g.display();

Пояснение

Список смежности реализован как массив объектов, где adjList[i] содержит свойства с именами - смежными вершинами, и значениями - весами соответствующих ребер.

Rust

Матрица смежности

adjacency_matrix.rs

struct Graph {
    num_vertices: usize,
    adj_matrix: Vec<Vec<i32>>,
}

impl Graph {
    fn new(num_vertices: usize) -> Self {
        // Инициализация матрицы смежности нулями
        let adj_matrix = vec![vec![0; num_vertices]; num_vertices];
        Graph {
            num_vertices,
            adj_matrix,
        }
    }
    
    fn add_edge(&mut self, u: usize, v: usize, weight: i32) {
        // Добавление ребра между вершинами u и v с весом
        self.adj_matrix[u][v] = weight;
        self.adj_matrix[v][u] = weight; // Для неориентированного графа
    }
    
    fn display(&self) {
        // Вывод матрицы смежности
        println!("Матрица смежности:");
        for i in 0..self.num_vertices {
            for j in 0..self.num_vertices {
                print!("{} ", self.adj_matrix[i][j]);
            }
            println!();
        }
    }
}

fn main() {
    // Граф с 4 вершинами (0, 1, 2, 3)
    // Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
    let mut g = Graph::new(4);
    g.add_edge(0, 1, 2);
    g.add_edge(0, 2, 5);
    g.add_edge(1, 2, 1);
    g.add_edge(2, 3, 3);
    
    // Вывод матрицы смежности
    g.display();
}

Пояснение

Матрица смежности реализована как вектор векторов. adj_matrix[i][j] содержит вес ребра между вершинами i и j. Если ребра нет, значение равно 0.

Список смежности

adjacency_list.rs

use std::collections::HashMap;

struct Graph {
    num_vertices: usize,
    adj_list: Vec<HashMap<usize, i32>>,
}

impl Graph {
    fn new(num_vertices: usize) -> Self {
        // Инициализация списка смежности
        let mut adj_list = Vec::with_capacity(num_vertices);
        for _ in 0..num_vertices {
            adj_list.push(HashMap::new());
        }
        Graph {
            num_vertices,
            adj_list,
        }
    }
    
    fn add_edge(&mut self, u: usize, v: usize, weight: i32) {
        // Добавление ребра между вершинами u и v с весом
        self.adj_list[u].insert(v, weight);
        self.adj_list[v].insert(u, weight); // Для неориентированного графа
    }
    
    fn display(&self) {
        // Вывод списка смежности
        println!("Список смежности:");
        for (i, neighbors) in self.adj_list.iter().enumerate() {
            print!("{}: ", i);
            for (vertex, weight) in neighbors {
                print!("({}, {}) ", vertex, weight);
            }
            println!();
        }
    }
}

fn main() {
    // Граф с 4 вершинами (0, 1, 2, 3)
    // Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
    let mut g = Graph::new(4);
    g.add_edge(0, 1, 2);
    g.add_edge(0, 2, 5);
    g.add_edge(1, 2, 1);
    g.add_edge(2, 3, 3);
    
    // Вывод списка смежности
    g.display();
}

Пояснение

Список смежности реализован как вектор HashMap, где adj_list[i] содержит пары ключ-значение: ключ - смежная вершина, значение - вес ребра.

Go

Матрица смежности

adjacency_matrix.go

package main

import "fmt"

type Graph struct {
    numVertices int
    adjMatrix   [][]int
}

func NewGraph(numVertices int) *Graph {
    // Инициализация матрицы смежности нулями
    adjMatrix := make([][]int, numVertices)
    for i := range adjMatrix {
        adjMatrix[i] = make([]int, numVertices)
    }
    return &Graph{
        numVertices: numVertices,
        adjMatrix:   adjMatrix,
    }
}

func (g *Graph) AddEdge(u, v, weight int) {
    // Добавление ребра между вершинами u и v с весом
    g.adjMatrix[u][v] = weight
    g.adjMatrix[v][u] = weight // Для неориентированного графа
}

func (g *Graph) Display() {
    // Вывод матрицы смежности
    fmt.Println("Матрица смежности:")
    for i := 0; i < g.numVertices; i++ {
        for j := 0; j < g.numVertices; j++ {
            fmt.Printf("%d ", g.adjMatrix[i][j])
        }
        fmt.Println()
    }
}

func main() {
    // Граф с 4 вершинами (0, 1, 2, 3)
    // Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
    g := NewGraph(4)
    g.AddEdge(0, 1, 2)
    g.AddEdge(0, 2, 5)
    g.AddEdge(1, 2, 1)
    g.AddEdge(2, 3, 3)
    
    // Вывод матрицы смежности
    g.Display()
}

Пояснение

Матрица смежности реализована как срез срезов. adjMatrix[i][j] содержит вес ребра между вершинами i и j. Если ребра нет, значение равно 0.

Список смежности

adjacency_list.go

package main

import "fmt"

type Graph struct {
    numVertices int
    adjList     []map[int]int
}

func NewGraph(numVertices int) *Graph {
    // Инициализация списка смежности
    adjList := make([]map[int]int, numVertices)
    for i := range adjList {
        adjList[i] = make(map[int]int)
    }
    return &Graph{
        numVertices: numVertices,
        adjList:     adjList,
    }
}

func (g *Graph) AddEdge(u, v, weight int) {
    // Добавление ребра между вершинами u и v с весом
    g.adjList[u][v] = weight
    g.adjList[v][u] = weight // Для неориентированного графа
}

func (g *Graph) Display() {
    // Вывод списка смежности
    fmt.Println("Список смежности:")
    for i := 0; i < g.numVertices; i++ {
        fmt.Printf("%d: ", i)
        for vertex, weight := range g.adjList[i] {
            fmt.Printf("(%d, %d) ", vertex, weight)
        }
        fmt.Println()
    }
}

func main() {
    // Граф с 4 вершинами (0, 1, 2, 3)
    // Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
    g := NewGraph(4)
    g.AddEdge(0, 1, 2)
    g.AddEdge(0, 2, 5)
    g.AddEdge(1, 2, 1)
    g.AddEdge(2, 3, 3)
    
    // Вывод списка смежности
    g.Display()
}

Пояснение

Список смежности реализован как срез map, где adjList[i] содержит пары ключ-значение: ключ - смежная вершина, значение - вес ребра.

C#

Матрица смежности

AdjacencyMatrix.cs

using System;

public class Graph {
    private int numVertices;
    private int[,] adjMatrix;
    
    public Graph(int vertices) {
        this.numVertices = vertices;
        // Инициализация матрицы смежности нулями
        this.adjMatrix = new int[numVertices, numVertices];
    }
    
    public void AddEdge(int u, int v, int weight) {
        // Добавление ребра между вершинами u и v с весом
        adjMatrix[u, v] = weight;
        adjMatrix[v, u] = weight; // Для неориентированного графа
    }
    
    public void Display() {
        // Вывод матрицы смежности
        Console.WriteLine("Матрица смежности:");
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                Console.Write(adjMatrix[i, j] + " ");
            }
            Console.WriteLine();
        }
    }
}

public class Program {
    public static void Main() {
        // Граф с 4 вершинами (0, 1, 2, 3)
        // Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
        Graph g = new Graph(4);
        g.AddEdge(0, 1, 2);
        g.AddEdge(0, 2, 5);
        g.AddEdge(1, 2, 1);
        g.AddEdge(2, 3, 3);
        
        // Вывод матрицы смежности
        g.Display();
    }
}

Пояснение

Матрица смежности реализована как двумерный массив. adjMatrix[i, j] содержит вес ребра между вершинами i и j. Если ребра нет, значение равно 0.

Список смежности

AdjacencyList.cs

using System;
using System.Collections.Generic;

public class Graph {
    private int numVertices;
    private Dictionary<int, int>[] adjList;
    
    public Graph(int vertices) {
        this.numVertices = vertices;
        // Инициализация списка смежности
        this.adjList = new Dictionary<int, int>[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjList[i] = new Dictionary<int, int>();
        }
    }
    
    public void AddEdge(int u, int v, int weight) {
        // Добавление ребра между вершинами u и v с весом
        adjList[u][v] = weight;
        adjList[v][u] = weight; // Для неориентированного графа
    }
    
    public void Display() {
        // Вывод списка смежности
        Console.WriteLine("Список смежности:");
        for (int i = 0; i < numVertices; i++) {
            Console.Write($"{i}: ");
            foreach (var pair in adjList[i]) {
                Console.Write($"({pair.Key}, {pair.Value}) ");
            }
            Console.WriteLine();
        }
    }
}

public class Program {
    public static void Main() {
        // Граф с 4 вершинами (0, 1, 2, 3)
        // Ребра: 0-1 (вес 2), 0-2 (вес 5), 1-2 (вес 1), 2-3 (вес 3)
        Graph g = new Graph(4);
        g.AddEdge(0, 1, 2);
        g.AddEdge(0, 2, 5);
        g.AddEdge(1, 2, 1);
        g.AddEdge(2, 3, 3);
        
        // Вывод списка смежности
        g.Display();
    }
}

Пояснение

Список смежности реализован как массив Dictionary, где adjList[i] содержит пары ключ-значение: ключ - смежная вершина, значение - вес ребра.

Идея в том, чтобы разделить целую и дробную часть и хранить их отдельно.
Так число

314 - целая часть называется мантисса.
-2 - степень, по которой смещаем число, называется экспонента.

Так как в компьютере данные хранятся в двоичной системе счисления, то раскладывать мы будем по степеням двойки, а не десятки, как в примере.

Мишаня

Это точно 3.14?
Умник
А что не узнаешь?

Шаг 1: Определяем знак
Число 3.14 положительное.
- Знаковый бит = 0
Шаг 2: Переводим число в двоичную систему
Нужно перевести отдельно целую и дробную части.
1. Целая часть (3):
- 3 в двоичной системе — это 11.
1. Дробная часть (0.14): Переводим путем последовательного умножения на 2.
- 0.14 × 2 = 0.28 → Целая часть: 0
- 0.28 × 2 = 0.56 → Целая часть: 0
- 0.56 × 2 = 1.12 → Целая часть: 1
- 0.12 × 2 = 0.24 → Целая часть: 0
- 0.24 × 2 = 0.48 → Целая часть: 0
- 0.48 × 2 = 0.96 → Целая часть: 0
- 0.96 × 2 = 1.92 → Целая часть: 1
- 0.92 × 2 = 1.84 → Целая часть: 1
- 0.84 × 2 = 1.68 → Целая часть: 1
- 0.68 × 2 = 1.36 → Целая часть: 1
- ... и так далее.
Процесс будет бесконечным. Возьмем первые 23 бита (длину мантиссы) с запасом для точности.
Двоичная дробная часть: .00100011110101110000101...
Собираем число:

Шаг 3: Нормализуем число
Нормализация — это представление числа в виде .
- Мы сдвинули точку на один разряд влево, поэтому экспонента стала равна 1.
Шаг 4: Определяем экспоненту и мантиссу
- Фактическая экспонента = 1
- Смещение (bias) для single-precision = 127
- Смещенная экспонента = 1 + 127 = 128
- Переведем 128 в двоичный вид:
- 128 в двоичной системе — это 10000000
Мантисса:
- После нормализации у нас есть 1.100100011110101110000101...
- Ведущая единица (1.) отбрасывается и не хранится в памяти. В памяти хранится только дробная часть.
- Дробная часть мантиссы: 10010001111010111000010 (мы берем ровно 23 бита. Так как биты продолжаются, происходит округление. В данном случае 24-й бит равен 1, поэтому мы округляем вверх).
- Для нашего расчета возьмем мантиссу: 10010001111010111000011 (уже округленную).
Шаг 5: Собираем двоичное представление (32 бита)
- Знак (1 бит): 0
- Экспонента (8 бит): 10000000
- Мантисса (23 бита): 10010001111010111000011
Полное 32-битное представление числа 3.14:

Шаг 6: Проверяем по формуле
Теперь подставим все в нашу формулу, чтобы убедиться, что мы получим примерно 3.14.

Переведем мантиссу 1.10010001111010111000011 в десятичную систему:
Это делается так же, как и обычное двоичное число, но после точки идут отрицательные степени двойки.
1 ->
- 1 × 2^0 = 1
.10010001111010111000011 ->
- 1×2^(-1) = 0.5
- 0×2^(-2) = 0
- 0×2^(-3) = 0
- 1×2^(-4) = 0.0625
- 0×2^(-5) = 0
- 0×2^(-6) = 0
- 0×2^(-7) = 0
- 1×2^(-8) = 0.00390625
- 1×2^(-9) = 0.001953125
- 1×2^(-10) = 0.0009765625
- 1×2^(-11) = 0.00048828125
- 0×2^(-12) = 0
- 1×2^(-13) = 0.0001220703125
- 0×2^(-14) = 0
- 1×2^(-15) = 0.000030517578125
- 1×2^(-16) = 0.0000152587890625
- 1×2^(-17) = 0.00000762939453125
- 0×2^(-18) = 0
- 0×2^(-19) = 0
- 0×2^(-20) = 0
- 0×2^(-21) = 0
- 1×2^(-22) = 0.0000002384185791015625
- 1×2^(-23) = 0.00000011920928955078125
Теперь сложим все эти дробные части. Результат будет примерно:

Прибавляем ведущую единицу:

Финальный расчет:
Умник

Получили 3.14!

Почти... Да, представление вещественных чисел с плавающей точкой не точно и даёт погрешность.

Типизация переменных является свойством языка программирования.
В Python указывать тип переменной необязательно. А в вот в Java обязательно. Поэтому языки программирования деляется по такому признаку:
Статическая типизация (C++, Java, Rust, Go, C#):

Тип проверяется на этапе компиляции.
Как пазл — детали должны точно подходить друг к другу.

Динамическая типизация (Python, JavaScript):

Тип определяется во время выполнения
Как пластилин — можно менять форму по ходу работы.

Визуализация работы с переменными

Визуализация работы с переменными в памяти

Попробуйте вводить разные типы переменных

Имя переменной

Значение

Для чтения

Оперативная память

Операции и вывод

                    // Код программы
 // Создайте переменную для просмотра кода 

// Вывод программы появится здесь

Создайте переменную, указав имя и значение. Переменная будет размещена в оперативной памяти по определенному адресу.

Заключение

Работы с переменными в языках программирования отличается по таким признакам:
Статическая vs динамическая типизация: Java, C++, C#, Rust и Go используют статическую типизацию, тогда как Python и JavaScript - динамическую
Изменяемость по умолчанию: Rust уникален тем, что переменные по умолчанию неизменяемые, в отличие от других языков.
Объявление констант: Каждый язык имеет свой синтаксис для создания неизменяемых переменных (const, final, val и т.д.)
Ключевые слова: Различные подходы к объявлению переменных (let, var, auto, := и другие).

Сравнение переменных в языках программирования

Python Примеры объявления переменных

# Динамическая типизация
x = 10                    # Целое число
name = "Анна"             # Строка
is_valid = True           # Логическое значение
price = 19.99             # Число с плавающей точкой

# Не требует явного указания типа
# Переменные могут менять тип
x = "теперь строка"       # Динамическое изменение типа

# Множественное присваивание
a, b, c = 1, 2, 3

// Статическая типизация - тип указывается явно
int age = 25;                    // Целое число
String name = "Анна";           // Строка
boolean isActive = true;         // Логическое значение
double price = 19.99;           // Число с плавающей точкой

// final создает константу (неизменяемую переменную)
final double PI = 3.14159;

// Разные целочисленные типы
byte smallNumber = 100;
long bigNumber = 1000000000L;

// Статическая типизация
int count = 10;                  // Целое число
std::string name = "Анна";      // Строка (требует #include <string>)
bool is_valid = true;            // Логическое значение
float price = 19.99f;           // Число с плавающей точкой

// Автовывод типа (C++11 и выше)
auto value = 42;                 // int
auto text = "Hello";            // const char*

// Указатели и ссылки
int number = 100;
int* ptr = &number;             // Указатель
int& ref = number;              // Ссылка

// Динамическая типизация
let age = 25;                   // Число
const name = "Анна";           // Константная строка
var isActive = true;            // Логическое значение (устаревший синтаксис)

// let и const (ES6+)
let counter = 0;                // Можно изменить
const MAX_SIZE = 100;           // Нельзя изменить

// Тип определяется значением
let value = 10;                 // number
value = "теперь строка";        // string - тип изменен
value = true;                   // boolean - тип изменен

// Статическая типизация
int age = 25;                   // Целое число
string name = "Анна";          // Строка
bool isActive = true;           // Логическое значение
double price = 19.99;          // Число с плавающей точкой

// var - вывод типа (статический)
var count = 10;                 // int
var text = "Hello";            // string

// Константы
const double PI = 3.14159;
const int MAX_USERS = 100;

// Nullable типы
int? nullableInt = null;        // Может содержать null

// Статическая типизация с выводом типа
let age = 25;                   // i32 (целое число 32 бита)
let name = "Анна";             // &str (строка)
let is_active = true;           // bool

// По умолчанию переменные неизменяемые
let x = 10;                     // Неизменяемая
let mut y = 20;                 // Изменяемая (ключевое слово mut)

// Аннотации типа (необязательны, когда тип можно вывести)
let price: f64 = 19.99;        // Число с плавающей точкой 64 бита

// Константы
const MAX_POINTS: u32 = 100_000;

// Статическая типизация
var age int = 25               // Явное объявление
var name = "Анна"             // Вывод типа
isActive := true               // Краткое объявление (только внутри функций)

// Краткая форма (только внутри функций)
count := 10                    // int
price := 19.99                 // float64
text := "Hello"               // string

// Множественное объявление
var a, b, c int = 1, 2, 3
x, y, z := 1, "two", true

// Константы
const Pi = 3.14159
const (
    StatusOK = 200
    StatusNotFound = 404
)

Сравнительная таблица характеристик

Типизация: Динамическая

Объявление констант: Через соглашение (UPPER_CASE)

Изменяемость по умолчанию: Изменяемые

Ключевые слова для переменных: (не требуется), global, nonlocal

Область видимости: Функциональная, модульная, глобальная

Инициализация по умолчанию: Нет (ошибка использования до присваивания)