Реализация простого и быстрого возведения в степень на C/C++

Привет всем. Продолжаю потихоньку публиковать свои реализации известных всем и очень популярных алгоритмов, например, уже успел реализовать супер сложную быструю сортировку. На этот раз отклонюсь чуть ближе к математике и рассмотрю алгоритм быстрого возведения в степень, который часто(или даже скорее всегда) используется в стандартных библиотечных функциях возведениях.

Но прежде, чем начать, почему бы не реализовать обычное возведение? Правильно, нет причин себе в этом отказывать, поехали!

Функция возведения числа в степень

Методом «в лоб», пробежимся в цикле и перемножим число само на себя сколько нужно раз. Работает за O(deg) где deg степень.

читать далее «Реализация простого и быстрого возведения в степень на C/C++»

Реализация быстрой сортировки на C/C++

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

Я буду далеко не первым и не последним, кто скажет, что «быстрая» она только в названии и сейчас существует куча аналогов, и вообще для каждого типа данных нужна своя сортировка. Да, это все правда, но эта правда не отменяет простого факта, что собственноручная реализация быстрой сортировки оттачивает навыки программирования в общем, и она всегда будет в университетских курсах, я в этом уверен. Из этих же соображений был выбран язык программирования для реализации, ибо тут же можно попрактиковаться в использовании указателей в C/C++.

Предлагаю перейти к делу и для начала кратко рассмотреть суть алгоритма.

читать далее «Реализация быстрой сортировки на C/C++»

Пример простого клиент-серверного приложения на Java

«Клиент-сервер» это очень распространенная и логичная архитектура приложений. Мне кажется, что в наши дни редко можно встретить standalone-клиентское приложение. Поэтому я принял решение рассмотреть пример построения клиент-серверного приложения на Java без привязки к конкретной задаче. Сначала вкратце пробежимся по классовой структуре приложения, потом посмотрим на отдельную реализацию каждого класса. В самом конце статьи я дам ссылку на скачивание архива с готовой структурой приложения. Итак, начнем.

Основные компоненты приложения

Основными компонентами, естественно, являются непосредственно клиент и сервер. Однако, кроме них необходим еще пакет вспомогательных классов, которые, в простейшем случае, будут отвечать за обмен сообщениями между клиентом и сервером. В минимальной комплектации нужны такие классы: MessageReader/MessageWriter(считывает/записывает сообщение в поток на сокете), MessageFactory(содержит идентификаторы всех возможных сообщений), набор сообщений-запросов(Request) и набор сообщений-ответов(Response). Все они будут размещены в пакете «core», который должны иметь у себя и клиент и сервер.

Рассмотрим классовую структуру всего проекта, а потом перейдем к реализации.

Классовая структура клиент-серверного приложения

читать далее «Пример простого клиент-серверного приложения на Java»

Реализация больших чисел на C/C++ со сложением и вычитанием

Доброго времени суток и светлого неба над головой, дорогие друзья! Ни для кого из вас не секрет, что ограничение максимального и минимального значения целого числа, хоть и разнится на разных архитектурах, но существует. Например, для целого числа типа int диапазон его значений равен от –2147483647 – 1 до 2147483647. Казалось бы, 2 миллиарда в каждую сторону это целая гора, но как только вы займетесь настоящей криптографией, либо машинным обучением, теорией вероятностей или еще более крутой математикой, вы поймете, что это чертовски мало. Именно в таком случае на помощь приходят, так называемые, большие числа.

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

Например, как можно хранить число 123456789123456789, в int оно не поместится. тогда мы поместим его в массив int`ов, mas[0] = 123456, mas[1] = 789123, mas[2] = 456789, напишем специальные алгоритмы, которые будут корректно складывать, вычитать, умножать и делить такие числа.

Как раз о таких алгоритмах инициализации, сложения и вычитания больших чисел я сейчас расскажу, поехали!

читать далее «Реализация больших чисел на C/C++ со сложением и вычитанием»

Реализация параллельного алгоритма Флойда-Уоршелла

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

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

В качестве инструмента будет использована уже знакомая библиотека MPICH(установка библиотеки).

Схема параллельного алгоритма Флойда-Уоршелла

В оригинальном линейном алгоритме единственная операция это нахождение минимума, как справедливо замечено в крохах источников, что я находил, ее нет смысла распараллеливать. Вся сложность алгоритма(О^3) заключается в полном переборе «матрицы смежности». Напомню, что я так называю матрицу размера NxN, в которой на пересечении i-й строки и j-го столбца стоит вес ребра из i-ой вершины в j-ую.

читать далее «Реализация параллельного алгоритма Флойда-Уоршелла»