За один проход

За один проход.

Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:

Задача 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. Для простоты считаем, что числа неотрицательные.

А если сделать ещё один шаг?
Задача 4. В последовательности записаны целые числа. Число X встречается 1,2 или 3 раза, остальные числа — по 4 раза. Найти число X.

        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-битных символов.

        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;
        }

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

Следующие две очень похожие задачи за один проход решить вряд ли получится. Но для них есть интересное решение за log(M) проходов.
Задача 7. В последовательности записаны целые неотрицательные числа, меньшие M, причём известно, что каждое число встречается не более одного раза. Найти наименьшее число, которое в этой последовательности не встречается.
Задача 8. В последовательности записано M+1 целое неотрицательное число, все числа меньше M. Найти какое-нибудь число, которое встречается хотя бы дважды.

Есть ещё задачка, которая меня давно интересует, но решения которой я не знаю.
Задача 9. В последовательности записаны числа от 1 до N в каком-то порядке. Каждое число встречается один раз. N заранее известно. Требуется за один просмотр последовательности определить чётность записанной в ней перестановки. Какой минимальный объём памяти для этого требуется?
Парадокс заключается в том, что в любой заранее выбранный момент нам достаточно помнить 1 бит информации. Но после этого будет необходимо иметь N+1 бит — чтобы запомнить, какие элементы идут в последовательности после этого момента.

Автор: Mrrl

Источник