Зона кода

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

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

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

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

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

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

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

Будем считать, что активационным ключом является обычное целое положительное число. В данной версии алгоритма значение ключа на следующей минуте целиком и полностью зависит от значения ключа в текущий момент. Если в данный момент ключ равен N, то через минуту он будет равен N + S(N), где S(N) – это число, называемое контрольной суммой числа N и равняется количеству единиц в двоичной записи числа N. То есть если N = 6, то в следующую минуту значение ключа будет равно 8, если быть точнее, то N’ = N + S(N) = 6 + S(6) = 610 + 1102 = 8.

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

Входные данные
В первой и единственной строке входного файла
INPUT.TXT находятся два натуральных числа – N (1 ≤ N ≤ 2×109) и K (1 ≤ K ≤ 2×109).

Выходные данные
В выходной файл
OUTPUT.TXT выведите одно число – значение активационного ключа через K минут, учитывая, что на данный момент времени значение ключа равно N.

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

Не очень хорошо, с точки зрения русского языка, сформулировано предложение, начинающееся с "Если в данный момент...": вместо "и равняется" стоило написать "равное" или "которое равно". И ещё в одном месте допущена очевидная опечатка: вместо 1102 должно быть S(1102). Но условие понятно, и это главное.

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

Предварительные замечания

Если отбросить из условия ненужную "шелуху", то оно сведётся к предложению по заданному первому члену a1 некоторой натуральной последовательности {an} и заданному числу k найти член последовательности с номером k + 1, при условии, что известна рекуррентная формула an+1 = an + S(an), справедливая при n ≥ 1. Здесь S(n) — это количество единиц в двоичной записи натурального числа n, называемое "контрольной суммой" данного числа.

"Повозившись" некоторое время с задачей, я сделал вывод о том, что, скорее всего, из рекуррентной формулы явную (т. е. выражающую an через n) получить не удастся. Таким образом, задача, вероятно, является задачей на оптимизацию вычислений. Говоря иначе, мы должны построить основанный на рекуррентной формуле алгоритм, вычисляющий ak+1 достаточно быстро.

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

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

Предположим, что числа будут храниться в переменных типа unsigned int. Компилятор MinGW64, который я использую, отводит под каждую переменную такого типа 4 байта. Найдём заранее контрольные суммы всех чисел, "помещающихся" в один байт, т. е. чисел от 0 до 255. Тогда нахождение контрольной суммы 32-битного числа очевидным образом сведётся к суммированию уже известных четырёх контрольных сумм 8-битных чисел.

Давайте напишем вспомогательную программу, выводящую на консоль контрольные суммы чисел от 0 до 255. Она может выглядеть, например, так:

#include <stdio.h>

int main()
{
    int k = 0;
    for (int i = 0; i < 16; i++)
    {
        for (int j = 0; j < 16; j++)
        {
            int s = 0, m = k;
            while (m)
            {
                s += m % 2;
                m >>= 1;
            }
            printf("%d, ", s);
            k++;
        }
        putchar('\n');
    }
    return 0;
}

Код программы достаточно прост. Переменная k в ходе выполнения двух циклов for, один из которых вложен в другой, пробегает значения от 0 до 255. Каждый раз значение, хранящееся в k, копируется в переменную m, после чего в рамках цикла while сдвигается на 1 бит вправо до тех пор, пока не обнулится. Перед каждым таким сдвигом переменная s, содержащая 0 до выполнения цикла while, увеличивается на значение последнего бита переменной m. В итоге, после завершения цикла в s оказывается контрольная сумма числа, хранящегося в k, которая и выводится на консоль.

В результате выполнения программы получаем следующий консольный вывод:

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,

Этот текст нам потребуется в дальнейшем: мы вставим его в код нашей программы.

Первая версия программы

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

 1.#include <stdio.h>
 2.
 3.const int ar[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
 4.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 5.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 6.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 7.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 8.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 9.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
10.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
11.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
12.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
13.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
14.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
15.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
16.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
17.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
18.                  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
19.
20.int main()
21.{
22.    unsigned int n, k;
23.    FILE *f = fopen("INPUT.TXT", "r");
24.    fscanf(f, "%u %u", &n, &k);
25.    fclose(f);
26.    unsigned char *p = (unsigned char *) &n, *p1 = p + 1, *p2 = p + 2, *p3 = p + 3;
27.    for (int i = 0; i < k; i++)
28.        n += ar[*p] + ar[*p1] + ar[*p2] + ar[*p3];
29.    f = fopen("OUTPUT.TXT", "w");
30.    fprintf(f, "%u", n);
31.    fclose(f);
32.    return 0;
33.}

Создаём массив с незатейливым именем ar (стр. 3-18), в который помещаем контрольные суммы чисел от 0 до 255 таким образом, чтобы каждый его элемент содержал контрольную сумму своего индекса. Считываем из файла INPUT.TXT числа N и K, сохраняя их в переменных n и k соответственно (см. стр. 22-25). Сразу же отмечу, что, выполняя файловый ввод и вывод в наших программах, мы не будем проверять наличие доступа к файлам и корректность входных данных, чтобы не загромождать код. Будем предполагать, что с файлами всегда всё "в порядке".

Создаём 4 указателя на unsigned char (этот тип компилятором MinGW64 реализован как однобайтовый), присваивая им адреса четырёх байтов, в которых хранится переменная n (стр. 26).

Рекуррентное вычисление членов последовательности выполняется в цикле for. В этом цикле мы k раз увеличиваем значение переменной n на контрольную сумму этого значения, вычисляемую как сумму четырёх контрольных сумм значений, содержащихся в отдельный байтах переменной n (стр. 27-28). В качестве контрольной суммы каждого значения, находящегося в отдельном байте переменной n, берётся содержимое элемента массива ar с индексом, равным этому значению, которое, в свою очередь, получается посредством разыменования указателя на данный байт.

После окончания цикла искомый результат, т. е. член последовательности с индексом K + 1, содержится в переменной n. Остаётся лишь вывести её значение в файл OUTPUT.TXT (стр. 29-31).

Теперь можно скомпилировать программу и запустить её на выполнение, предварительно сформировав файл INPUT.TXT. Давайте, для начала, внесём в этот файл значения N и K, каждое из которых равно миллиону:

1000000 1000000

После выполнения программы получаем следующее содержимое файла OUTPUT.TXT:

12480957

На выполнение программы ушли доли секунды.

Что ж, а теперь возьмём, в качестве N и K максимально возможные значения. Эти значения совпадают и равны двум миллиардам:

2000000000 2000000000

Запускаем программу и получаем в файле OUTPUT.TXT вот что:

3226000845

Выполнение программы заняло чуть более 13-ти секунд. Разумеется, такое время выполнения нас устроить не может.

А устраивает ли нас результат? Даже если бы на каждой итерации к n добавлялась единица, то результат был бы равен 4×109. А мы получили число, меньшее четырёх миллиардов. Таким образом, полученный нами ответ неверен.

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

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

Вторая и третья версии программы

Очевидным решением проблемы с переполнением представляется использование для хранения генерируемых членов последовательности переменной типа unsigned long long вместо unsigned int. Но сможем ли мы уложиться в 8 байт, отводимых компилятором MinGW64 двойному длинному целому?

Разумеется, да. Действительно, при максимальных значениях N и K, даже, если бы мы на каждой итерации прибавляли к переменной n в качестве контрольной суммы содержащегося в ней значения число 40, то в итоге получили бы

2×109+ 40 · 2×109 = 82×109.

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

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

Поступим следующим образом. Для каждого числа, не превышающего 28u − 1, где u — целое, такое, что 1 ≤ u ≤ 5, в качестве количества единиц, содержащихся в его двоичной записи, будем брать сумму контрольных сумм чисел, хранящихся в младших u байтах переменной, содержащей данное число. Таким образом, заведомо нулевые старшие байты использоваться не будут.

Вот новая версия программы:

 1.#include <stdio.h>
 2.
 3.const int ar[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
 4.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 5.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 6.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 7.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 8.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 9.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
10.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
11.                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
12.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
13.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
14.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
15.                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
16.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
17.                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
18.                  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
19.
20.const unsigned long long units[] = {0xFFull, 0xFFFFull, 0xFFFFFFull,
21.                                    0xFFFFFFFFull, 0xFFFFFFFFFFull};
22.
23.int main()
24.{
25.    unsigned long long n;
26.    unsigned int k;
27.    FILE *f = fopen("INPUT.TXT", "r");
28.    fscanf(f, "%llu %u", &n, &k);
29.    fclose(f);
30.    int count = 0;
31.    unsigned char *p = (unsigned char *) &n;
32.    for (int i = 0; i < 5; i++)
33.    {
34.        while (n <= units[i])
35.        {
36.            int s = 0;
37.            for (int j = 0; j <= i; j++)
38.                s += ar[p[j]];
39.            n += s;
40.            if (++count == k)
41.            {
42.                f = fopen("OUTPUT.TXT", "w");
43.                fprintf(f, "%llu", n);
44.                fclose(f);
45.                return 0;
46.            }
47.        }
48.    }
49.    return 0;
50.}

Остановимся на основных отличиях данной программы от предыдущей.

Числа вида 28u − 1, которые потребуются нам для сравнений, мы поместили в массив units (стр. 20, 21). Переменная n теперь уже имеет тип unsigned long long (см. стр. 25).

Каждый из пяти видов суммирования осуществляется в рамках отдельной итерации цикла for (см. стр.32). Для каждого значения i счётчика данного цикла контрольные суммы вычисляются как суммы i + 1 слагаемых до тех пор, пока, либо не будет достигнут результат, либо не возникнет переполнения, за возникновением которого "следит" цикл while. (см. стр. 34). Условием его продолжения является непревышение значения переменной n содержимого соответствующего элемента массива units.

При возникновении переполнения происходит переход к следующей итерации цикла for, в результате чего количество слагаемых, задействованных при вычислении контрольной суммы значения переменной n, увеличивается на единицу. Само суммирование реализовано с помощью цикла for (стр. 37-38). Контрольная сумма значения n "накапливается" в переменной s, которой перед выполнением цикла присваивается 0 (стр. 36). После вычисления контрольной суммы её значение добавляется к n (стр. 39).

Роль счётчика итераций выполняет переменная count (см. стр. 30). Как только значение count достигает значения переменной k, совпадающего с числом K, так сразу же значение n записывается в файл OUTPUT.TXT, после чего работа программы завершается (стр. 40-46).

Отметим, что, если входные данные лежат в диапазонах, установленных условием, то работа самого внешнего цикла for будет прервана инструкцией return (стр. 45), а аналогичная инструкция, внешняя по отношению к телу цикла (стр. 49) выполнена никогда не будет.

Компилируем программу и запускаем её на выполнение, не изменяя предыдущую версию файла INPUT.TXT. Получаем следующее содержимое файла OUTPUT.TXT:

36359345582

Это и есть ответ, соответствующий начальным данным N = K = 2×109. Время выполнения программы — примерно 25 секунд. Это очень много! Не годится!

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

Давайте немного переделаем предыдущую версию программы таким образом, чтобы упомянутые адреса вычислялись заранее. Но тогда нам придётся отказаться от внешнего цикла for и каждую из его пяти итераций реализовывать отдельно. Таким образом, новая версия программы будет содержать 5 циклов while. А вот и её код:

#include <stdio.h>
#define IN                                     \
            FILE *f = fopen("INPUT.TXT", "r"); \
            fscanf(f, "%llu %u", &n, &k);      \
            fclose(f);

#define OUT {                                       \
                f = fopen("OUTPUT.TXT", "w");       \
                fprintf(f,"%llu", n);               \
                fclose(f);                          \
                return 0;                           \
            }

const int ar[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
                  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
                  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
                  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
                  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};

int main()
{
    unsigned long long n;
    unsigned int k;
    IN;
    int count = 0;
    unsigned char *p = (unsigned char *) &n;
    unsigned char *p1 = p + 1, *p2 = p + 2, *p3 = p + 3, *p4 = p + 4;

    while (n <= 0xFFull)
    {
        n += ar[*p];
        if (++count == k)
            OUT;
    }

    while (n <= 0xFFFFull)
    {
        n += ar[*p] + ar[*p1];
        if (++count == k)
            OUT;
    }

    while (n <= 0xFFFFFFull)
    {
        n += ar[*p] + ar[*p1] + ar[*p2];
        if (++count == k)
            OUT;
    }

    while (n <= 0xFFFFFFFFull)
    {
        n += ar[*p] + ar[*p1] + ar[*p2] + ar[*p3];
        if (++count == k)
            OUT;
    }

    while (1)
    {
        n += ar[*p] + ar[*p1] + ar[*p2] + ar[*p3] + ar[*p4];
        if (++count == k)
            OUT;
    }

    return 0;
}

Я решил оформить код, отвечающий за считывание данных из входного файла, в виде макроса IN, а код, записывающий информацию в выходной файл и завершающий работу программы, — в виде макроса OUT. Теперь уже значения указателей (p, p1, p2, p3, p4) вычисляются заранее, "раз и навсегда".

Массив units я уже не использую, а вместо этого значения его элементов непосредственно заношу в условия циклов while. Обратите внимание на то, что в последнем цикле while условие его продолжения всегда истинно, поскольку мы знаем, что, если входные данные удовлетворяют условию задачи, то значение переменной n никогда не выйдет за пределы пяти байтов.

Как и в предыдущем случае, инструкция return, завершающая код функции main(), никогда не будет выполнена. Она присутствует лишь для "красоты"; её можно опустить.

На входных данных N = K = 2×109 программа работает в течение примерно 15-ти секунд. Таким образом, по сравнению с предыдущей версией мы получили очень неплохой выигрыш в 10 секунд. Но всё равно время работы очень далеко от идеала.

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