Помощь студентам

И решето Эратосфена, и решето для средневековой головоломки являются специальными случаями обобщенного модульного решета. Пусть m₁, т₂, т₃, ..., m_t—множество из t целых чисел (называемых модулями). Для каждого m_i рассмотрим п_i арифметических прогрессий

m_ik+а_ij, j=1,2, .... n_i.

Задача состоит в отыскании всех целых чисел, заключенных в пределах между A и B, которые для каждого m_i, одновременно принадлежат одной из n_iпрогрессий. В решете Эратосфена мы имеем m₁=2, m₂=3, m₃=5,..., m_i=р (наибольшее простое число, меньшее или равное N), n_i=m_i-1 и а_ij=j. В задаче о женщине и яйцах m_i=i+1, n_i=l, 1
Если модули попарно взаимно просты, то мы можем объединить все прогрессии и получить одно множество из Пn₁; прогрессий с модулем Пmi. Это осуществляется повторным применением следующей техники объединения прогрессий m₁k+a₁ и m₂k+а₂ в одну прогрессию т₁m₂k+а. Поскольку по предположению наибольший общий делитель т₁ и m₂ равен единице, алгоритм Евклида гарантирует существование целых чисел и и v, таких, что m₁u+m₂v=1. Выбирая a=m₁ua₂-m₂va₁, мы находим, что x
Пользу обобщенного модульного решета можно ощутить, рассматривая задачу проверки первого миллиона чисел Фибоначчи с целью отыскания полных квадратов. Поскольку

мы получаем, что

F_1000000 < 10²⁰⁰⁰⁰⁰

т. е. F_1000000имеет более 200000 десятичных знаков. Очевидно, «лобовой» метод порождения первого миллиона чисел Фибоначчи и проверки каждого из них, не является ли оно полным квадратом, не осуществим, но методом решета вычисление можно легко провести за несколько минут.

Вычисление начинается с установления в памяти миллиона разрядов для характеристического вектора, i-й разряд представляет целое число F_i; если этот разряд равен единице, то F, может быть квадратом, если он равен нулю, то F_i квадратом быть не может. Сначала все разряды будут единицами, и в процессе отсеивания на каждом шаге некоторые из этих разрядов становятся нулями. После окончания просеивания, если окажется, что какой-либо из разрядов равен единице, то соответствующее число Фибоначчи нужно исследовать на предмет, не является ли оно полным квадратом. Миллион разрядов памяти, требующихся для характеристического вектора,— это много, но не чрезмерно; например, в машине с 32-разрядными словами потребуется только 31250 слов памяти.

Рассмотрим последовательность Фибоначчи по модулю р, где р — простое число. Пусть это будет последовательность P₁, P₂, P₃, …, определяемая следующим образом:

Р₁ =Р₂ = 1, P_i₊₁=P_i_-1+P_i(mod p).

Эта последовательность периодическая, причем период начинается с P₁=l. Для доказательства этого утверждения рассмотрим p²+l упорядоченных пар целых чисел

(Р_1, Р₂), (Р₂ , Р_з), .... (P_p², P_p²₊₁), (P_p²_+1,P_p²₊₂).

Поскольку по модулю р существует только р² различных упорядоченных пар целых чисел, две из этих пар должны совпадать. Пусть (Р_r, P_r₊₁) и (P_s, P_s₊₁) будут самыми левыми совпадающими парами

(Р_r, Р_r₊₁) = (Р_s, Р_s₊₁), r<s.

Если r>1, то мы имеем

(Р_r_-1, P_r) = (P_s_-1, P_s),

что противоречит предположению о том, что (P_r, Р_r₊₁) и (P_s, P_s₊₁) — самые левые совпадающие пары. Таким образом, числа Фибоначчи образуют по модулю р периодическую последовательность, начинающуюся с P₁ и такую, что Р_i=Р_i+_n_Tp для некоторого T_p и всех n
По модулю любого числа п существует несколько квадратов (обычно называемых квадратичными вычетами по модулю п¹) и несколько неквадратов. Например, 0, 1, 2 и 4 являются квадратичными вычетами по модулю 7, в то время как 3, 5 и 6 являютса квадратичными невычетами. Таким образом, любое из чисел m=3, 5-или 6 (mod 7) не может быть квадратом, потому что оно является квадратичным невычетом по модулю 7. Поскольку для каждого простого р числа Фибоначчи по модулю р образуют периодическую последовательность с периодом Т_p, мы производим отсеивание, используя арифметические прогрессии T_pk+i для каждого i, такого, что Р_i является квадратичным невычетом по модулю р. Для иллюстрации процесса отсеивания рассмотрим случай р=7. Ряд Фибоначчи по модулю 7 представляет собой последовательность из 16 элементов

1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0,

повторяющихся периодически с периодом Т₇==16. Поскольку 3, 5 и 6 — квадратичные невычеты, мы знаем теперь, что F₄₊₁₆_n_, F₅₊₁₆_n, F₇₊₁₆_n_, F₉₊₁₆_n , F₁₀₊₁₆_n, F₁₁₊₁₆_n и F₁₄₊₁₆_n не являются квадратами для. n
После отсеивания квадратичных невычетов первых 32 простых чисел мы обнаруживаем, что все значения разрядов, кроме первого, второго и двенадцатого, изменены на нули. Не изменившие значений разряды соответствуют трем числам F₁=F₂= 1 и F₁₂=144; поэтому можно заключить, что среди первого миллиона чисел Фибоначчи только они являются квадратами. На самом деле доказано, что только они являются квадратами среди чисел Фибоначчи.

Рекурсивное решето

Существует много решет, в которых модули m₁, т₂, ... заранее не заданы; значение т_i будет зависеть от чисел, не удаленных после просеивания по модулю m_i-1. Многие решета строятся рекурсивным образом. Фактически, решето Эратосфена обычно так и строится: после выписывания чисел 2, 3, ..., N мы вычеркиваем все числа, кратные 2, кроме самой двойки. Затем, поскольку наименьшее оставшееся число, чьи кратные остались неудаленными, равно трем, удаляются все числа, кратные трем, кроме самой тройки, и т. д.

Заметим, что на каждом шаге первое удаленное число является квадратом числа, с которого начинается просеивание; например, первым числом, исключаемым двойкой, будет 4, тройкой — 9 и т. д. Когда число, относительно которого производится просеивание, становится больше
Обычно мы удваиваем размер ячеек решета Эратосфена, осуществляя предпросеивание для двойки; другими словами, мы начинаем только с нечетных чисел, отсеивая кратные 3, 5, 7, 11 и т. д. Пусть Х — двоичный набор; тогда рекурсивный вариант решета Эратосфена (с предпросеиванием для двойки) для нечетных простых чисел до 2N+1 показан в алгоритме 4.5.

Х ¬ (1, 1, .... 1)

for k=3 to
[X_(k_-1)/2 представляет нечетное число k]

if X_(k-1)/2=1 then for i =k² to 2N+1 by 2k do X_(i-1)/2¬0

for k=1 to N do if X_k=1 then вывести 2k+1

Алгоритм 4.5. Решето Эратосфена для нечетных простых чисел.

Другое хорошо известное рекурсивное решето порождает счастливые числа. Из списка чисел 1, 2, 3, 4, 5, ... удаляется каждое второе число, в результате чего получается список 1, 3, 5, 7, 9. Поскольку тройка является первым числом (исключая единицу), которое не использовано в качестве просеивающего, из оставшихся чисел мы удаляем каждое третье число, получая в результате список 1, 3, 7, 9, 13, 15, 19, 21,... .Теперь удаляется каждое седьмое число, в результате чего получается список 1, 3, 7, 9,13, 15, 21, ... . Числа, которые никогда не удаляются из списка, называются «счастливыми».

Несмотря на большую схожесть решета Эратосфена и решета для получения счастливых чисел, последнее реализуется труднее. Трудность возникает потому, что числа, отсеиваемые на k-м шаге, позиционно зависят от еще неисключенных элементов, а не от элементов первоначального множества. В предположении, что для представления чисел используется двоичная последовательность в решете для счастливых чисел нужно будет считать, скажем, каждый седьмой единичный разряд вместо вообще седьмого разряда. Эта задача существенно облегчается, если использовать бирки. Вместо использования полного машинного слова для представления возможных решений, которые мы должны просеять, мы используем часть этого слова для хранения счетчика числа единиц в остальной части слова. Например, в ЭВМ со словом, состоящим из четырех байтов, каждый из которых состоит из восьми разрядов, мы можем использовать слово так, как это показано на рис. 4.13. Правый байт содержит счетчик числа единичных разрядов в трех левых байтах. С использованием бирок отыскание t-го невычеркнутого элемента (t-гo единичного разряда) легко осуществляется путем суммирования бирок до тех пор, пока сумма S не станет большей или равной t; соответствующий элемент будет (S—t+1)-м единичным разрядом справа в левых байтах последнего слова, чья бирка суммировалась.

Очевидно, навешивание бирок не приводит к экономии времени, если из каждого слова исключается один или более разрядов. По этой причине имеет смысл осуществить просеивание для нескольких шагов без бирок и начинать их использовать, когда подлежащие отсеиванию элементы становятся достаточно редкими. Точное число шагов, прогоняемых без бирок, зависит от типа решета и размера слова. Например, для решета счастливых чисел с 32-разрядными словами и 8-разрядной биркой лучше сделать первые три-четыре шага без бирки.

Навешивание бирок можно расширить до бирок более высокого порядка, выбирая целое т
Рекурсивное решето несколько другого характера можно использовать для вычисления следующей последовательности U. Вначале U=(1, 2). Если вопрос о вхождении в U решен для всех целых чисел, меньших п, то пÎU тогда и только тогда, когда п является суммой единственной пары различных элементов из U. Таким образом U=(1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26,...). Эту последовательность можно вычислить с помощью двух параллельных просеиваний; целое должно быть просеяно (должно быть суммой, получаемой не менее чем одним способом) и не должно быть отсеяно (должно быть суммой, получаемой не более, чем одним способом). Используем два двоичных вектора. Для i>2

Х_i=1, если и только если i представимо в виде суммы не менее чем одним способом.

У_i=1, если и только если i представимо в виде суммы не более чем одним способом.

«Двойное решето» для вычисления элементов U до некоторого числа N приводится в алгоритме 4.6. Значение счетчика k увеличивается до тех пор, пока оно не достигнет первого целого числа, большего предыдущего элемента из U, представимого точно одним способом. Это целое принадлежит U, и поэтому разряды, соответствующие всем целым k+i для i<.k, должны быть обновлены.

X ¬ (1, 1, 0, 0, ....,0)

У ¬ (1, 1, 1, 1, ..., 1)

k ¬ 1

for i=1 to N do if X_i
Алгоритм 4.6. Двойное решето для последовательности U.
Литература

Рейнгольд Э. и др. Комбинаторные алгоритмы: теория и практика.

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.

Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.

Вирт Н. Алгоритмы + структуры данных = программы.

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.

Niemann, Tomas. Сортировка и поиск: Рецептурный справочник Перевод с английского П.Н.Дубнер (infoscope@glasnet.ru).

Сибуя М., Ямамото Е. Алгоритмы обработки данных.

Aho, Alfred V. and Jeffrey D. Ullman [1983]. Data Structures and Algorithms
Cormen, Thomas H., Charles E. Leiserson and Ronald L. Rivest [1990]. Introduction to Algorithms
Knuth, Donald E. [1998]. The Art of Computer Programming, Volume 3, Sorting and Searching. Addison-Wesley, Reading, Massachusetts.

Pearson, Peter K. [1990]. Fast Hashing of Variable-Length Text Strings
Pugh, William [1990]. Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications of the ACM, 33(6):668-676, June 1990.

Глоссарий

Term

Термин

sort by insertion

сортировка вставками

replacement selection

выбор с замещением

polyphase merge sort

многофазное слияние

array

массив

linked list

линейный список

comparison

сравнение

in-place

на месте (без дополнительных массивов)

stable sort

устойчивая сортировка

external sort

внешняя сортировка

underflow

вырождение

overflow

переполнение

red-black tree

красно-черное дерево

B-tree

Б-дерево

skip list

слоёный список

rotation

Форма входа

Наша реклама

Поиск

Календарь

Архив записей

Наш опрос

Друзья сайта

Статистика