Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:
Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число.
Задача 2. В последовательности записаны целые числа. Одно из чисел встречается ровно один раз, остальные — по два раза. Найти число, которое встречается один раз.
Задача 3. В последовательности записаны целые числа. Число X встречается один или два раза, остальные числа — по три раза. Найти число X. Для простоты считаем, что числа неотрицательный.
Задача 4. В последовательности записаны целые числа. Число X встречается 1,2 или 3 раза, остальные числа — по 4 раза. Найти число X.
Задача 5. В длинной очереди стоят люди. Для каждого из них, кроме последнего, записали его имя и имя того, кто стоит за ним. Полученные записи перемешали и записали в файл. Требуется за один просмотр файла определить имена первого и последнего человека. Известно, что эти имена различны (иначе задача неразрешима), но, в общем, имена могут повторяться. Имя каждого человека состоит из шестнадцати 8-битных символов.
Задача 6. В последовательности записаны целые числа, больше половины из которых равны одному и тому же числу X. За один просмотр последовательности найти это число.
Задача 7. В последовательности записаны целые неотрицательные числа, меньшие M, причём известно, что каждое число встречается не более одного раза. Найти наименьшее число, которое в этой последовательности не встречается.
Задача 8. В последовательности записано M+1 целое неотрицательное число, все числа меньше M. Найти какое-нибудь число, которое встречается хотя бы дважды.
Задача 8. В последовательности записано M+1 целое неотрицательное число, все числа меньше M. Найти какое-нибудь число, которое встречается хотя бы дважды.
Задача 9. В последовательности записаны числа от 1 до N в каком-то порядке. Каждое число встречается один раз. N заранее известно. Требуется за один просмотр последовательности определить чётность записанной в ней перестановки. Какой минимальный объём памяти для этого требуется?
Коментарі
Дописати коментар