Зона кода

А давайте немного попрограммируем...

Задача о временном ключе. Часть 2

C99Решение задач

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

Последовательность {an}, члены которой являются натуральными числами, задана с помощью рекуррентной формулы an+1 = an + S(an), справедливой при n ≥ 1, где S(n) — это количество единиц в двоичной записи натурального числа n, называемое "контрольной суммой" данного числа (первый член последовательности считается известным). Заданы натуральные числа N и K. Требуется написать программу, вычисляющую aK+1, при условии, что a1 = N.

В первой части уже приведены 3 версии программы, решающие поставленную задачу. Однако производительность этих программ нас не устроила: самая "быстрая" из данных версий обрабатывала максимально возможные (в соответствии с условием задачи) значения N и K в течение примерно 15 секунд, в то время, как программа не должна работать дольше одной секунды. В данной, заключительной части, мы обсудим способы повышения производительности и приведём код соответствующих новых версий программы.

Будем предполагать, в дальнейшем, что читатель ознакомился с первой частью статьи.

Задача о временном ключе. Часть 1

C99Решение задач

Рассмотрим задачу, условие которой размещено на сайте "Школа программиста". На данном сайте она названа "Временной ключ-2". Ниже приводится условие этой задачи с сохранением орфографии оригинала.

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

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

Знаменитая компания "Gold&Silver Soft" решилась на революционный шаг – было решено разработать принципиально новый способ динамической генерации активационного ключа. В данном алгоритме ключ зависит от времени и меняется каждую минуту, что существенно затрудняет взлом.

Переходы между датами и номерами дней в григорианском календаре

C99Решение задач

Захотелось мне узнать, сколько дней я прожил на свете. И решил не считать, а написать программку. Об этой программе я и собираюсь рассказать.

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

Вторая функция будет обратной по отношению к первой. Она будет заниматься преобразованием номера дня в дату. Данная функция, используемая совместно с первой, позволит нам получать дату, отстоящую от заданной на указанное количество дней в ту или иную строну. Кстати, сразу же скажу, что в этой статье слово "день" мы будем понимать как синоним слова "сутки".

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

Программу напишем на языке C99. Однако формулы и приёмы для работы с датами, которые мы получим, могут быть реализованы на любом языке программирования.

Задача о двенадцати монетах и трёх взвешиваниях

C99Решение задач

Рассмотрим следующую задачу.

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

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

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

О построении корректных текстовых сообщений, содержащих числа

C99Решение задач

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

В этом случае в тексте после числа оставшихся дней нужно поставить слово "день" в корректной форме, а именно, в требуемом числе и требуемом падеже. Например: "21 день", "35 дней", "44 дня". В этой статье мы поговорим о том, как верным способом сформировать требуемую форму существительного.

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

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

Весь программный код, приведённый в статье, написан на языке C99.

Построение броуновских мостов

C99Графические программы

В своё время мною была написана статья, в которой рассказывалось о моделировании броуновского движения. На очереди — ещё одно явление, связанное с британским ботаником Броуном. На этот раз мы будем рассматривать кривые, называемые броуновскими мостами.

Принцип построения броуновских мостов я взял из книги Седжвика, Уэйна и Дондеро "Программирование на языке Python: учебный курс". Эта книга уже служила ранее источником материалов для написания статей данного сайта; речь идёт об этой и этой статьях.

Статья адресована в первую очередь новичкам в программировании. Мы напишем на языке C99 простую программу, создающую изображения броуновских мостов, в основе которой будет лежать рекурсия. Для построения изображений будем использовать графическую библиотеку pgraph, предполагая, что читатель знаком с ней в общих чертах.

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

Генерация нормально распределённых псевдослучайных чисел

C99Решение задач

Просматривая книгу Седжвика, Уэйна и Дондеро "Программирование на языке Python: учебный курс" (я уже упоминал её на страницах данного сайта здесь и здесь), я наткнулся на код программы "Броуновский мост". В ней вызывалась функция gaussian(), входящая в стандартный модуль stdrandom языка Python.

Эта функция каждый раз при её вызове возвращает число из генерируемой ею последовательности псевдослучайных чисел, распределённых по нормальному закону. И тут я задумался о том, как создать аналог данной функции на языке C99.

Ведь все стандартные функции языка C99, каким-либо образом связанные с генерацией псевдослучайных чисел, исчерпываются всего лишь двумя функциями, входящими в библиотеку stdlib.h. Одна из них — это rand(). Данная функция генерирует псевдослучайные целые числа, равномерно распределённые в диапазоне от 0 до RAND_MAX включительно (в нашем случае значение макроса RAND_MAX равно 32767).

Другая функция — это srand(), которая "вынуждает" функцию rand() генерировать последовательность, "жёстко связанную" с аргументом, передаваемым srand() (каждому такому аргументу соответствует своя последовательность).

Об одной глупой ошибке и её неожиданных последствиях

C99Полезное

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

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

Оказалось, что ответить на этот вопрос не очень-то и просто. Я провёл небольшое расследование и кое-что стало понятно, однако, не могу сказать, что сумел расставить все точки над i.

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

Но сначала — небольшая разминка.

Построение изображения треугольника Серпиньского

C99Графические программы

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

Программу напишем на языке программирования C99. Для создания изображений будем использовать графическую библиотеку pgraph, так что читателю крайне желательно быть знакомым, хотя бы в общих чертах, с этой библиотекой. Нами также будут созданы 2 анимации с участием в них треугольников Серпиньского. Для построения видеороликов из статичных изображений будет задействован видеоредактор VirtualDub. Видеоролики после их создания загрузим на Ютьюб.

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

Итак, начнём.

Графическая библиотека pgraph: копирование прямоугольных областей

C99Библиотека pgraph

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11