В приведенном ниже коде предполагается^™ функция randint(l, n)
4. Смотрите главу 12, в особенности задачу 8. В приведенном ниже коде предполагается^™ функция randint(l, и) возвращает случайное целое число в диапазоне [L.u].
for i = [0, п) x[i] = 1 for 1 = [0. к)
swap(i , randint(i , n-1)) print x[i]
Функция swap меняет местами два элемента массива х. Функция randint подробно обсуждается в разделе 12.1 главы 12.
5. Представление всех десяти миллионов чисел в битовом массиве потребует такого же количества битов, то есть 1,25 миллиона байтов. Если учесть, что телефонные номера (в США) не начинаются с нуля и единицы, можно уменьшить этот объем до одного миллиона байтов. Можно исиользовать и двухпроходный алгоритм, который будет сортировать числа от 0 до 4 999 999 за первый проход, используя 5 ООО 000/8=652 ООО слов памяти, а затем обработает числа от 5 ООО ООО до 9 999 999. k-проходный алгоритм сортирует п не повторяющихся натуральных чисел, не превосходящих п за время, пропорциональное к*п, и требует объема памяти, пропорционального п/к,
6. Если каждое число появляется не больше десяти раз, то количество его повторов можно сосчитать, имея четыре бита (половину байта). Используя решение задачи 5, можно отсортировать весь файл за один проход, используя 10 000 000/2 байт памяти или за к проходов, используя 10 000 000/(2хк) байт памяти.
Опубликовал vovan666
April 17 2013 00:06:15 ·
0 Комментариев ·
2905 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
