В свете вышеизложенного решенйе с использованием битового массива напрашивается само собой. Набор неотрицательных целых чисел, не превышающих, к примеру, 20, может быть представлен строкой из 20 битов. Возьмем, допустим, набор {1, 2, 3, 5, 8, 13}. Представление его в виде битового массива будет выглядеть так:
01110100100001000000
Биты, соответствующие имеющимся числам, установлены, а все прочие — сброшены.
В реальной задаче семь десятичных знаков задают число, не превышающее 10 миллионов. Представим файл как строку из десяти миллионов битов , в которой i-й бит равен единице тогда и только тогда, когда в файле присутствует число i. В этом представлении используются три особенности данной задачи, нехарактерные для сортировки в общем виде: диапазон входных данных не слишком широк, одинаковых чисел быть не может и, кроме них, в записях больше ничего нет.
При использовании битового массива для представления набора целых чисел программа естественным образом разбивается на три части.
1. Массив инициализируется нулями.
2. Считываются целые числа из файла, и соответствующие биты в массиве устанавливаются в 1.
3. Формируется упорядоченный выходной файл (путем последовательной проверки значения каждого бита и записи в файл целых чисел, соответствующих ненулевым битам).
Если п — количество битов в массиве (в данном случае — 10 ООО ООО), программа на псевдокоде будет выглядеть следующим образом:
/* Часть 1: инициализация массива нулями */ for i - [0. n) bi t[i ] = 0
/* Часть 2: помещение элементов в набор */ для каждого i во входном файле bit[i] = 1
/* Часть 3: формирование упорядоченного выходного файла */ for i - [0, п)
i f b1t[1] -= 1
записать 1 в выходной файл
Помните, что, согласно предисловию, обозначение for i-[0, п) соответствует перебору всех целых чисел от 0 до п-1.
Этого наброска оказалось достаточно, чтобы программист смог решить задачу. Некоторые проблемы, с которыми он столкнулся при реализации, описаны в задаг чах 2, 5 и 7 в конце главы. |
Главная
Каталог файлов
