http://habrahabr.ru/post/243819/
Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:
Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число
Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.
Задача 2. В последовательности записаны целые числа. Одно из чисел встречается ровно один раз, остальные — по два раза. Найти число, которое встречается один раз.
Здесь тоже всё просто: найдем XOR всех чисел — он и будет ответом. В самом деле, если какой-то бит в искомом числе равен нулю, то во всей последовательности он будет равен 1 в чётном числе элементов, и его значение в XOR равно нулю. В противном случае, аналогично, его значение в XOR равно 1. Или, проще говоря, одинаковые элементы при суммировании взаимоуничтожатся.
Слегка усложним задачу:
Задача 3. В последовательности записаны целые числа. Число X встречается один или два раза, остальные числа — по три раза. Найти число X. Для простоты считаем, что числа неотрицательные.Скрытый текстПоступим аналогично предыдущей задаче: переведём каждое из чисел в троичную систему: b=b[0]+3*b[1]+32*b[2]+… Для каждого разряда найдём сумму его значений по модулю 3 (обозначим суммы s[0],s[1],s[2],...). Кроме того, посчитаем сами числа.
Если чисел в последовательности было 3*k+1, то X встретился один раз, и его значение равно s[0]+3*s[1]+32*s[2]+… Если же чисел было 3*k+2, то в наборе s[i] единицы придётся заменить на двойки и наоборот: x[i]=(3-s[i])%3, и X=x[0]+3*x[1]+32*x[2]+…
А если сделать ещё один шаг?
Задача 4. В последовательности записаны целые числа. Число X встречается 1,2 или 3 раза, остальные числа — по 4 раза. Найти число X.Скрытый текстПредыдущий подход здесь уже не сработает: если мы возьмём систему счисления с основанием 4, и найдём поразрядные суммы, то для случаев, когда X встретился один или три раза, всё будет хорошо. Но если X встретился дважды, мы уже не сможем узнать, была ли очередная цифра равна 0 или 2 — значение суммы si для этого разряда в обоих случаях будет равно нулю. Что делать?
На самом деле, в прошлый раз я вас обманул. Совершенно незачем возиться с троичной системой — достаточно было посчитать сумму битов в каждом двоичном разряде, и если она делилась на 3, то в числе X соответствующий бит равнялся нулю. Если нет — то единице.
В этой задаче делаем точно так же, но проверяем делимость на 4. Например, эти задачи можно решить так:
static int FindNotThree(IEnumerable<int> seq) {
int a=0,b=0;
foreach(int c in seq) {
a^=~b&c;
b^=~a&c;
}
return a|b;
}
static int FindNotFour(IEnumerable<int> seq) {
int a=0,b=0;
foreach(int c in seq) {
a^=b&c;
b^=c;
}
return a|b;
}
Задача 5. В длинной очереди стоят люди. Для каждого из них, кроме последнего, записали его имя и имя того, кто стоит за ним. Полученные записи перемешали и записали в файл. Требуется за один просмотр файла определить имена первого и последнего человека. Известно, что эти имена различны (иначе задача неразрешима), но, в общем, имена могут повторяться. Имя каждого человека состоит из шестнадцати 8-битных символов.Скрытый текстБудем рассматривать каждое имя, как битовую строчку из 128 элементов. В каждой записи у нас две таких строчки — b[i] и c[i].
Cначала посмотрим, что получится, если для каждого i мы найдём сумму s[i] разностей b[i]-c[i] для всех записей.
Поскольку все имена, кроме первого и последнего, встречаются в строчках b и c однаковое число раз, то при суммировании они взаимоуничтожатся, и в сумме останется поразрядная разность первого и последнего имени. Значение s[i], таким образом, может принимать значения -1, 0 или 1.
Если s[i]=-1, то значение b[i] для первого имени равно 0, а для второго 1. Если s[i]=1, то значения будут равны 1 и 0 соответственно. Но если s[i]=0, то мы можем сказать только, что значения этого бита в первом и последнем имени одинаковы. Как бы нам их найти?
Предположим, что мы знаем, что для какого-то k у нас s[k] ненулевое. Что будет, если мы найдём XOR значений (b[i]&b[k])^(c[i]&c[k])?
Для всех имён n, кроме первого и последнего, выражение n[i]&n[k] войдёт в сумму дважды (один раз как b, второй раз, как c) и даст нулевой вклад. Если f — первое имя, а p — последнее, то в сумме останется (f[i]&f[k])^(p[i]&p[k]). Нас интересуют только те биты, для которых f[i]=p[i] (значения остальных мы уже нашли). Поэтому, (f[i]&f[k])^(p[i]&p[k])=f[i]&(f[k]^p[k]), а поскольку s[k]!=0, то f[k]^p[k]=1, и итоговая сумма равна f[i].
К сожалению, сказать заранее, в каком бите будут различаться имена, мы не можем. Поэтому, на всякий случай, будем считать суммы
(b[i]&b[k])^(c[i]&c[k]) для всех пар i,k. Всего нам понадобится 128*127/2=8128 однобитных счётчиков и 128 двухбитных (для подсчёта s[i]).
Например, можно написать обработку так (мы предполагаем, что оба имени в записи передаются в одном байтовом массиве, записанные подряд):
static byte[] FindDiffNames(IEnumerable<byte[]> seq) {
const int LName=16;
byte[,] pairs=new byte[LName*8,LName];
byte[] res=new byte[2*LName];
foreach(byte[] name in seq) {
for(int i=0;i<LName;i++) {
res[i+LName]^=(byte)(name[i]&res[i]);
res[i]^=(byte)(name[i]^name[i+LName]);
res[i+LName]^=(byte)(name[i+LName]&res[i]);
for(int k=0;k<LName*8;k++) {
byte mask=(byte)(1<<(k&7));
if((name[k>>3]&mask)!=0) pairs[k,i]^=name[i];
if((name[LName+(k>>3)]&mask)!=0) pairs[k,i]^=name[i+LName];
}
}
}
for(int i=0;i<LName;i++) {
int b0=res[i],b1=res[i+LName],s=0;
for(int j=0;j<LName*8;j++) s|=pairs[j,i];
s&=~b0;
res[i]=(byte)((b0&~b1)|s); res[i+LName]=(byte)((b0&b1)|s);
}
return res;
}
С помощью этого приёма можно, также, найти разность множеств, одно из которых получается из другого добавлением двух или даже трёх элементов (или добавлением двух и удалением одного). Если различия более сильные, приходится хранить суммы конъюнкций не только пар, но и троек битов. И XOR там уже недостаточно — приходится считать хотя бы трёхбитные знакопеременные суммы.
Задача 6. В последовательности записаны целые числа, больше половины из которых равны одному и тому же числу X. За один просмотр последовательности найти это число.Скрытый текстЗаметим, что если мы вычеркнем из последовательности два различных числа, то условие задачи останется верным. Поэтому мы можем вычёркивать пары различных чисел до тех пор, пока все элементы не станут равными одному и тому же числу. Это число и будет X.
Чтобы реализовать этот метод, заведём ячейку, в которой будет храниться какой-то элемент последовательности, и счётчик — сколько копий этого элемента у нас просмотрено и пока не вычеркнуто.
Когда мы читаем очередной элемент, у нас есть три варианта:
— Счётчик равен нулю. Кладём прочитанный элемент в ячейку, увеличиваем счётчик на 1.
— Элемент равен значению ячейки. Увеличиваем счётчик на 1.
— Элемент не равен значению ячейки. Уменьшаем счётчик на 1.
После того, как мы просмотрим всю последовательность, в ячейке окажется искомое число.
К сожалению, обобщить это решение на случай, когда число X встречается больше, чем в 1/k случаев (k известно), не удаётся. Мы можем так же завести k-1 ячейку со счётчиком, удалять за один раз по k различных элементов, получим в конце k-1 кандидата на роль X, но опознать его нам не удастся — даже значение счётчика у него будет не самым большим. Зато если нам разрешат сделать второй проход, мы можем посчитать, сколько раз каждый из кандидатов встретился в последовательности, и выдать гарантированно самого частого.
У исходной задачи есть ещё одно решение. Для каждого бита считаем, сколько раз он равнялся 0, а сколько — 1, и выдаём более частое значение. Возможно, его удастся обобщить на случай, когда X встречается больше, чем в 1/3 случаев — посчитаем статистику для каждой пары битов… вдруг поможет?
Следующие две очень похожие задачи за один проход решить вряд ли получится. Но для них есть интересное решение за log(M) проходов.
Задача 7. В последовательности записаны целые неотрицательные числа, меньшие M, причём известно, что каждое число встречается не более одного раза. Найти наименьшее число, которое в этой последовательности не встречается.Задача 8. В последовательности записано M+1 целое неотрицательное число, все числа меньше M. Найти какое-нибудь число, которое встречается хотя бы дважды.Скрытый текстРешения практически одинаковы. Делим диапазон 0..M-1 на две или более частей. Для каждой части подсчитываем, сколько чисел в неё попало. В первой задаче оставляем самый ранний поддиапазон, в который попало меньше чисел, чем его длина, во второй — любой из поддиапазонов, в который попало больше чисел, чем его длина. Процесс повторяем, пока не останется диапазон из одного числа. Оно и будет ответом.
Есть ещё задачка, которая меня давно интересует, но решения которой я не знаю.
Задача 9. В последовательности записаны числа от 1 до N в каком-то порядке. Каждое число встречается один раз. N заранее известно. Требуется за один просмотр последовательности определить чётность записанной в ней перестановки. Какой минимальный объём памяти для этого требуется?
Парадокс заключается в том, что в любой заранее выбранный момент нам достаточно помнить 1 бит информации. Но после этого будет необходимо иметь N+1 бит — чтобы запомнить, какие элементы идут в последовательности после этого момента.