Генерация случайных чисел на C/C++ с помощью rand()

Приветствую всех, кто заскочил. В это короткой заметке будет пара слов о генерации псевдослучайных чисел на C/C++. В частности о том, как работать с самой простой функцией генерации — rand().

Функция rand()

Находится в стандартной библиотеке С++(stdlib.h). Генерирует и возвращает псевдослучайное число в диапазоне от 0 до RAND_MAX. Эта константа может отличаться в зависимости от компилятора или архитектуры процессора, в основном, это максимальное значение типа данных unsigned int. Параметров не принимает и никогда не принимала.

Для того, чтобы генерация свершилась, нужно выставить семя(seed) с помощью вспомогательной функции из той же библиотеки — srand(). Она принимает число и ставит его в качестве отправной точки в генерации случайного числа. Если семя не выставить, то при каждом запуске программы, мы будет получать одинаковые случайные числа. Самым очевидным решением является отправить туда текущее системное время. Сделать это можно с помощью функции time(NULL). Эта функция находится в библиотеке time.h.

С теорией разобрались, нашли все функции для генерации случайных чисел, теперь давайте погенерируем.

Пример использования функции генерации случайных чисел rand()

#include <ctime>
#include <iostream>
#include <cstdlib>

using namespace std;

int main() {
    srand(time(NULL));

    for(int i = 0; i < 10; i++) {
        cout << rand() << endl;
    }

    return 0;
}

Ранд нагенерировал нам 10 случайных чисел. В том, что они случайные вы можете убедиться, запуская программу вновь и вновь. Но этого недостаточно, поэтому нужно поговорить о диапазоне.

Выставить границы диапазона для rand()

Чтобы сгенерировать число в диапазоне от A до B включительно, нужно написать так:

A + rand() % ((B + 1) - A);

Значения границ могут быть в том числе и отрицательными, что позволяет генерировать отрицательное случайное число, посмотрим пример.

#include <ctime>
#include <iostream>
#include <cstdlib>

using namespace std;

int main() {
    srand(time(NULL));

    int A = -2;
    int B = 8;

    for(int i = 0; i < 100; i++) {
        cout << A + rand() % ((B + 1) - A) << endl;
    }

    return 0;
}

Реализация и взлом шифра Цезаря

Лицо ЦезаряДоброго времени суток, дорогие читатели и посетители! Сегодня небольшое погружение в мир криптографии и шифрования. Для меня эта область представляет некоторый интерес. А в целом, знать об этом нужно!  В нашем цифровом веке без шифрования все уже давно бы рухнуло, ваша почта шифруется, ваши фото шифруются(в России вряд ли, но все же), ваши переписки тоже шифруются. В идеальном интернете шифроваться должно вообще все, особенно любая финансовая информация. Финансы защищены даже лучше, чем личная жизнь. В любом случае, сегодня полезно хотя бы примерно знать, как это все работает. Для начала, предлагаю посмотреть на мою реализацию самого простого из шифров. А там и до RSA доберемся, поехали!

 

Прежде чем продолжить чтение, обратите внимание на реализации других шифров

Шифр простого сдвига

Так же известен под названием «Шифр Цезаря». Это шифр простой подстановки, при шифровании каждый символ текста заменяется символом, находящимся на некотором постоянном расстоянии левее или правее в алфавите. Наглядно на картинке из вики:

Действие шифра Цезаря

читать далее «Реализация и взлом шифра Цезаря»

Реализация топологической сортировки и поиск компонент сильной связности графа

Приветствую вас, друзья мои. В прошлых статьях я поделился своей реализацией поиска в ширину и поиска в длину на графе. Рассмотрел задачи, решаемые с помощью поиска в ширину. Теперь пришло время реализовать две задачи на поиск в глубину: топологическая сортировка и поиск компонент сильной связности. Реализовывать будем по прежнему на C++.

Топологическая сортировка

Задача заключается в том, чтобы отсортировать вершины ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин. Это я переписал с википедии. А вообще теорией мне заниматься не интересно, давайте сразу перейдем к реализации.

Реализация топологической сортировки на c++ с использованием стека

читать далее «Реализация топологической сортировки и поиск компонент сильной связности графа»

Реализация алгоритма поиска в глубину на графе

Краткое описание алгоритма поиска в глубину

Алгоритм, как и при поиске в ширину, ищет кратчайший путь от заданной вершины до всех остальных. При этом обход осуществляется «в глубину» графа, то есть мы прыгаем на потомка, потом на следующего и так далее, пока есть куда углубляться. Как только достигнут «конец» возвращаемся на один уровень и опять углубляемся. Другими словами, мы не задерживаемся на одном уровне, а перемещаемся вверх и вниз.

В этой заметке я приведу реализацию самого обхода в глубину, но вся его прелесть в задачах, которые решаются с его помощью.

Моя реализация поиска в глубину на c++

читать далее «Реализация алгоритма поиска в глубину на графе»

Реализация алгоритма поиска в ширину на графе

Краткое описание алгоритма поиска в ширину

Алгоритм ищет кратчайший путь, и его длину от заданной вершины до всех остальных. При этом просматривается последовательно каждый уровень соседей стартовой вершины. То есть мы в прямом смысле ходим в ширину по всему уровню. Подробнее вы всегда можете почитать на википедии. А вообще, если вы ищете реализацию, то уже знаете сам алгоритм, так что погнали реализовывать поиск в ширину!

Моя реализация поиска в ширину на c++

Граф представлен следующим образом. Массив(vector c++) из n элементов, где n — число вершин в графе. Каждый элемент массива соответствует вершине графа и содержит вложенный массив — список вершин, смежных с данной.


typedef vector< vector<int> > graphNotWeighted;

Функция реализации принимает на вход сам граф и номер стартовой вершины, отрабатывает, и заполняет два массива: массив расстояний от каждой вершины до стартовой, и массив предков каждой вершины на пути к стартовой. С помощью второго массива восстанавливается полный путь от стартовой вершины до всех остальных.

Исходный код алгоритма поиска в ширину на c++

читать далее «Реализация алгоритма поиска в ширину на графе»