Раз пошло такое дело и я опубликовал свою реализацию быстрой сортировки, с которой вы можете ознакомиться, то как можно обойти стороной самую популярную сортировку? Вообще, спроси у любого студента: «Какую сортировку ты знаешь?», и получишь ответ: «Пузырьком!». Нельзя просто взять и пройти мимо этого факта, мой святой долг стать одним из тысячи человек, которые опубликуют реализацию сортировки пузырьком. Поэтому усаживайтесь поудобнее, мы начинаем!
Суть пузырьковой сортировки
Алгоритм представляет собой проходы по сортируемому массиву, в которых сравниваются два соседних элемента, и, если порядок в них нарушен, то они меняются местами. За каждый проход минимум один элемент встает на свое место — «всплывает» в массиве.
Проход осуществляется двумя циклами: по i и по j. Внешний цикл по i идет от 0 до size-1, где size — размер массива. Важно заметить, что внутренний цикл достаточно прогнать от 0 до size-i-1 так как на i-ом шаге элементы после i-го индекса уже гарантированно отсортированы.
читать далее «Пузырьковая сортировка — реализация на C/C++» →
Привет всем. Продолжаю потихоньку публиковать свои реализации известных всем и очень популярных алгоритмов, например, уже успел реализовать супер сложную быструю сортировку. На этот раз отклонюсь чуть ближе к математике и рассмотрю алгоритм быстрого возведения в степень, который часто(или даже скорее всегда) используется в стандартных библиотечных функциях возведениях.
Но прежде, чем начать, почему бы не реализовать обычное возведение? Правильно, нет причин себе в этом отказывать, поехали!
Функция возведения числа в степень
Методом «в лоб», пробежимся в цикле и перемножим число само на себя сколько нужно раз. Работает за O(deg) где deg степень.
читать далее «Реализация простого и быстрого возведения в степень на C/C++» →
До текущего момента единственной публикацией о сортировке в моем блоге была статья про реализацию топологической сортировки вершин графа. Пора это исправлять! Строить грандиозных планов о покорении всех видов сортировки я не стану, а начну с одной из самых популярных — быстрая сортировка.
Я буду далеко не первым и не последним, кто скажет, что «быстрая» она только в названии и сейчас существует куча аналогов, и вообще для каждого типа данных нужна своя сортировка. Да, это все правда, но эта правда не отменяет простого факта, что собственноручная реализация быстрой сортировки оттачивает навыки программирования в общем, и она всегда будет в университетских курсах, я в этом уверен. Из этих же соображений был выбран язык программирования для реализации, ибо тут же можно попрактиковаться в использовании указателей в C/C++.
Предлагаю перейти к делу и для начала кратко рассмотреть суть алгоритма.
читать далее «Реализация быстрой сортировки на C/C++» →
«Клиент-сервер» это очень распространенная и логичная архитектура приложений. Мне кажется, что в наши дни редко можно встретить standalone-клиентское приложение. Поэтому я принял решение рассмотреть пример построения клиент-серверного приложения на Java без привязки к конкретной задаче. Сначала вкратце пробежимся по классовой структуре приложения, потом посмотрим на отдельную реализацию каждого класса. В самом конце статьи я дам ссылку на скачивание архива с готовой структурой приложения. Итак, начнем.
Основные компоненты приложения
Основными компонентами, естественно, являются непосредственно клиент и сервер. Однако, кроме них необходим еще пакет вспомогательных классов, которые, в простейшем случае, будут отвечать за обмен сообщениями между клиентом и сервером. В минимальной комплектации нужны такие классы: MessageReader/MessageWriter(считывает/записывает сообщение в поток на сокете), MessageFactory(содержит идентификаторы всех возможных сообщений), набор сообщений-запросов(Request) и набор сообщений-ответов(Response). Все они будут размещены в пакете «core», который должны иметь у себя и клиент и сервер.
Рассмотрим классовую структуру всего проекта, а потом перейдем к реализации.
Классовая структура клиент-серверного приложения
читать далее «Пример простого клиент-серверного приложения на Java» →
Доброго времени суток и светлого неба над головой, дорогие друзья! Ни для кого из вас не секрет, что ограничение максимального и минимального значения целого числа, хоть и разнится на разных архитектурах, но существует. Например, для целого числа типа int диапазон его значений равен от –2147483647 – 1 до 2147483647. Казалось бы, 2 миллиарда в каждую сторону это целая гора, но как только вы займетесь настоящей криптографией, либо машинным обучением, теорией вероятностей или еще более крутой математикой, вы поймете, что это чертовски мало. Именно в таком случае на помощь приходят, так называемые, большие числа.
Идея большого числа в том, чтобы вылезти за рамки ограничений стандартных типов данных, оперировать бесконечно большими числами, размер которых будет ограничен только вычислительной мощностью «машины». Как этого достичь? Самый логичный способ заключается в том, чтобы записывать число в строку и конвертировать специальным образом в согласованный массив чисел стандартного типа.
Например, как можно хранить число 123456789123456789, в int оно не поместится. тогда мы поместим его в массив int`ов, mas[0] = 123456, mas[1] = 789123, mas[2] = 456789, напишем специальные алгоритмы, которые будут корректно складывать, вычитать, умножать и делить такие числа.
Как раз о таких алгоритмах инициализации, сложения и вычитания больших чисел я сейчас расскажу, поехали!
читать далее «Реализация больших чисел на C/C++ со сложением и вычитанием» →
