Анализ рекурсивных алгоритмов

Рекурсия – это подражание объекта самому себе. Объект является рекурсивным если его части выглядят также как весь объект. Рекурсия очень широко применяются в математике и программировании:

  • структуры данных:
    • граф (в частности деревья и списки) можно рассматривать как совокупность отдельного узла и подграфа (меньшего графа);
    • строка состоит из первого символа и подстроки (меньшей строки);
  • шаблоны проектирования, например декоратор[1]. Объект декоратора может включать в себя другие объекты, также являющиеся декораторами. Детально рекурсивные шаблоны изучил Мак-Колм Смит, выделив в своей книге общий шаблон проектирования – Recursion [2];
  • рекурсивные функции (алгоритмы) выполняют вызов самих себя.

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

Читать далее

Рубрика: алгоритмы | Комментарии (3)

Анализ сложности алгоритмов. Примеры

Алгоритм – это точное предписание, однозначно определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату [1].

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

Читать далее

Рубрика: алгоритмы | Комментарии (4)

Юнит-тестирование. Пример. Boost Unit Test

Разработка и поддержка программ невозможна без внесения изменений в существующий код. Однако, всякое изменение сопряжено с возможным внесением ошибок. Чем больше и сложнее проект – тем более нетривиальным образом изменения могут сказываться на работе подсистем. В связи с этим, любое изменение кода требует проведения тестирования. В статье описываются:

  • теория unit-тестирования;
  • Unit Test Framework библиотеки Boost;
  • пример разработки программы с использованием unit-тестирования.

Читать далее

Рубрика: C++, библиотеки, программирование | Комментарии (5)

Фотографии с охоты в Бирилюсском районе

Эта галерея содержит 12 фотографий.

В середине сентября ездил на охоту. Находились мы в этих координатах 57.595091 широты, 90.553788 долготы. Координаты примерные – взял с карт Google, но находится это на 15км севернее пос. Полевое.  

Другие галереи | 1 комментарий

Теория чистого кода. Стиль кодирования

Чистый код должен быть эффективным, простым для восприятия и сопровождения, гибким и надежным. Приведенные требования зачастую противоречат друг другу, поэтому для написания чистого кода в каждом конкретном случае надо идти на некоторый компромисс. Нередко опытные программисты пытаются сформулировать советы по написанию чистого кода [1, 2, 3, 4, 5], которые зависят от используемого языка программирования, но во многом сходятся.

Эта статья изначально планировалась как своеобразная критика книги “Чистый код. Создание, анализ и рефакторинг” Роберта Мартина [1], поэтому я часто буду на него ссылаться. Мартин писал наиболее общие советы безотносительно конкретного языка программирования – этим его книга в корне отличается от других [2, 3, 4].

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

Читать далее

Рубрика: программирование | Комментарии (4)

Блог. Эксперименты. Монетизация

С момента публикации предыдущей статьи о блоге прошел почти год – за это время выросла посещаемость и вовлечённость пользователей. Кроме того, блог начал приносить хоть какой-то доход с рекламы (в районе 1000р в месяц), изначально я не ставил целью извлечение дохода, но немного поигрался с биржами.

Я проводил с блогом эксперименты (покупал ссылки, баннеры, продавал их, пробовал партнерские программы и т.п.) – в статье описано – что принесло положительный результат, а что – только убытки.

Читать далее

Рубрика: о блоге | Комментарии (21)

Паттерн Singleton. Описание. Пример использования

В статье описывается паттерн Singleton (Одиночка), рассмотрены 2 реализации и некоторые возможные модификации. Проанализированы сильные и слабые стороны шаблона. Приведен пример использования.

Статья состоит из двух частей:

  1. описание шаблона, варианты реализации, проблемы. Часть должна быть понятна программистам на любых языках, хотя примеры приведены на С++;
  2. более сложный пример – решается следующая задача:

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

Читать далее

Рубрика: C++, Qt, паттерны | Добавить комментарий

Публикация Qt-приложения для Android

Я немножко доработал игрушку на Qt из предыдущей статьи, выложил ее на google play и решил описать всё, что мне показалось интересным в этом процессе: получение аккаунта разработчика, сборка приложения для google play, проблемы с файлами дополнений и отладка приложения.

Читать далее

Рубрика: C++, Qt, программирование | Комментарии (4)

Разработка игры на С++, Qt

Написал ремейк небольшой логической игрушки – “Полный квадрат”. Код показался мне достаточно интересным чтобы описать на блоге.

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

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

  • класс QMovie для отображения gif-анимации тучек и ежа;
  • класс QPropertyAnimation – ежик перемещается плавно, при этом меняются его координаты (свойства);
  • QMediaPlayer из модуля Qt Multimedia. При перемещении наш ёжик топает;
  • Qt Style Sheets (QSS) используется для украшения элементов управления.
game_screens

снимки игровых экранов

Читать далее

Рубрика: C++, Qt | Комментарии (6)

Блок-схемы алгоритмов. ГОСТ. Примеры

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

На территории Российской Федерации действует единая система программной документации (ЕСПД), частью которой является Государственный стандарт – ГОСТ 19.701-90 “Схемы алгоритмов программ, данных и систем” [1]. Не смотря на то, что описанные в стандарте обозначения могут использоваться для изображения схем ресурсов системы, схем взаимодействия программ и т.п., в настоящей статье описана лишь разработка схем алгоритмов программ.

Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985.

Читать далее

Рубрика: алгоритмы | Комментарии (18)

Способы обработки XML в Qt – Stream, SAX, DOM

Многие сталкивались с XML-документами и знают что это такое, ведь стандарт рассматриваемого языка разметки опубликован в далеком 1998 году. Язык XML используется во многих областях, но чаще всего для передачи информации через Internet – не случайно стандарт разработан Консорциумом Всемирной паутины (W3C) [1].

Очень много информации в этом мире записано и передается в формате XML, например ленты новостей RSS и Atom. В связи с этим не будут лишними навыки использования библиотек для обработки XML-файлов.

В статье рассмотрены три варианта разбора файлов в формате XML средствами библиотеки Qt. В качестве примера используется файл, возвращаемый Центральным банком Российской Федерации на запрос курса доллара в заданный период [2].

Для получения файла с курсом валюты на сайт Центрального банка высылается запрос. Используется QNetworkAccessManager, подробно описанный в статье “Получение данных с сайта. Шаблон Producer/Consumer” [3]. Данные, извлеченные из файла, выводятся на график средствами библиотеки Qwt [4].

Screenshot_of_the_schedule_currency

рис. 1 Снимок окна с графиком курсов валют

Читать далее

Рубрика: C++, Qt | Добавить комментарий

Фотографии заповедника Столбы в апреле

Эта галерея содержит 10 фотографий.

В апреле на столбы сходил 3 раза, но фотографии выложу пачкой. Фотографий получилось мало. Один раз вообще не фотографировал, т.к. меня постоянно материл попутчик. Первые 2 фотографии сделаны 13 апреля. Мы ходили на столб “Каин и Авель”, но фотографировал я … Читать далее

Другие галереи | Комментарии (2)