Приложения

I. Системы счисления

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

 

Рис. I.1. Число 4321 в разных системах счисления

Архаичные системы счисления (например, римские цифры — I, II, III и т.д.) составляют числа из сумм цифр. Система счисления, которая используется сегодня, тоже опирается на суммы, но значение каждой цифры в позиции i умножается на d в степени i, где d — это некое число. Его называют основанием системы счисления. Мы обычно используем d = 10, потому что у нас десять пальцев, но система работает для любого основания d.

II. Метод Гаусса

Рассказывают, что как-то раз учитель в начальной школе в качестве наказания поставил Гауссу задачу: просуммировать все числа от 1 до 100. К изумлению учителя, Гаусс нашел ответ (5050) в течение нескольких минут. Его прием состоял в том, чтобы манипулировать порядком элементов удвоенной суммы:

 

 

 

= 10100

Разделив это на 2, мы получим 5050. Мы можем записать так:

.

Следовательно:

 

 

 

В последней строке i отсутствует, поэтому (n + 1) суммируется снова и снова n раз. Следовательно:

 

III. Множества

Мы используем слово множество для описания группы объектов. Например, мы можем назвать S множеством обезьянок-эмодзи:

S = {,  ,  ,  }.

 

Рис. III.1. S1 и S2 есть подмножества S

Подмножества. Множество объектов, содержащихся в другом множестве, называется подмножеством. Например, обезьянки, показывающие лапы и глаза, составляют подмножество S1 = {, }. Все обезьянки в S1 содержатся в S. Мы записываем это так: S1 S Мы можем сгруппировать обезьянок с лапками и ртами в другом подмножестве: S2 = {, }.

Объединение. Какие обезьянки принадлежат либо S1, либо S2? Ответ: обезьянки в S3 = {, , }. Новое множество — объединение двух предыдущих. Мы записываем это так: S3 = S1 S2.

Пересечение. Какие обезьянки принадлежат и S1, и S2? Ответ: обезьянки в S4 = {}. Новое множество получается путем пересечения двух предыдущих. Мы записываем это так: S4 = S1 S2.

Степенные множества. Обратите внимание, что S3 и S4 одновременно являются подмножествами S. Мы также полагаем, что S5 = S и пустое множество S6 = {} являются подмножествами S. Если подсчитать все подмножества S, то вы найдете 24 = 16 подмножеств. Если же рассматривать их все как объекты, то мы можем собрать их в множество. Множество всех подмножеств S называется его степенным множеством:

PS = {S1, S2, . . . , S16}.

IV. Алгоритм Кэдейна

В разделе «Полный перебор» главы 3 мы представили задачу «Лучшая сделка».

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

В разделе «Динамическое программирование» той же главы мы показали алгоритм, который решил эту задачу с временной сложностью O(n) и пространственной сложностью O(n). Когда в 1984 году Джей Кэдейн обнаружил эту задачу, он нашел способ решить ее с O(n) по времени и O(1) по пространству:

function trade_kadane(prices):

    sell_day ← 1

    buy_day ← 1

    best_profit ← 0

    for each s from 2 to prices.length

        if prices[s] < prices[buy_day]

            b ← s

        else

            b ← buy_day

        profit ← prices[s] - prices[b]

        if profit > best_profit

            sell_day ← s

            buy_day ← b

            best_profit ← profit

    return (sell_day, buy_day)

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