В следующем цикле число не обрабатывается, если оно равно nil, то есть уже вычеркнуто (см. таблицу A.12 на стр. 49). Вычёркивание всех ему кратных осуществляет итератор min.step(limit,step){|i| block} класса Numeric, который выполняет block, начиная со значения i=min, увеличивая его после каждой итерации на step до тех пор, пока оно не станет больше, чем limit. Воспользуйтесь командой ri compact для выяснения того, что делает метод compact.
Учитесь находить нужную Вам информацию в книгах, справочных системах и сети Интернет.
Пример 11. Числами Фибоначчи называют последовательность, задаваемую следующими формулами: f0 = 0, f1 = 1, fn = fn-1 + fn-2 для n > 1. Напишите рекурсивный метод вычисления величины fn.
Числа Фибоначчи встречаются и в науке, и в природе чрезвычайно часто[10], а последовательность этих чисел занимает весьма почётное место в Интернет-энциклопедии целочисленных последовательностей[11], которая является очень интересной сама по себе.
def fib(n)
n < 2?n:fib(n-2)+fib(n-1)
end
p fib(40)
Рекурсивным называют метод, который вызывает сам себя, и написать его в данном случае очень легко, ибо он дословно повторяет определение последовательности чисел Фибоначчи. Отметим только, что тернарный оператор a ? b : с эквивалентен условному оператору if a then b; else с end (см. таблицу A.12).
Пример 12. С помощью написанного рекурсивного метода практически невозможно находить числа Фибоначчи fn для больших значений n, так как даже на вычисление сорокового числа на компьютере с тактовой частотой процессора 2.4 Ghz требуется почти 6 минут. Реализуйте метод, позволяющий найти миллионное число Фибоначчи за «разумное время».
def fib(n)
return n if n < 2
a,b = 0,1
for i in 2..n
a,b = b,a+b
end
b
end
pfib(1_000_000)
Требуемое решение можно получить, рассматривая преобразование F, определённое на парах чисел формулой F (a, b) = = (b, a + b). Если начать с пары чисел (0,1), то многократное применение F порождает последовательность чисел Фибоначчи. Такая программа (обратите внимание на множественное (параллельное) присваивание, см. стр. 49) имеет линейную сложность, ибо количество необходимых для нахождения fn итераций цикла не превосходит n. Миллионное число Фибоначчи на компьютере с заданными в постановке задачи характеристиками эта программа находит примерно за две минуты, а ведь в его десятичной записи содержится 86784 цифры!
Интересно, что если вместо пар чисел рассматривать четвёрки, записанные в виде таблицы 2 х х 2 – квадратной матрицы, то можно получить ещё более быструю программу. Заметим, что матрица 
возведённая в квадрат, равна 
, в куб – 
, в четвертую степень – 
.
require 'matrix'
deffib(n)
return n if n < 2
(Matrix[[1,1],[1,0]]**n)[0,1]
end
p fib(1_000_000)
Первая строка этих матриц содержит числа Фибоначчи, а так как возведение в степень (в том числе и матриц) выполняется быстро, то вычисление чисел Фибоначчи таким способом оказывается весьма эффективным.
Для работы с матрицами, которые не входят в число базовых типов языка Ruby, необходимо с помощью директивы require подключить библиотеку, в которой определен класс Matrix и методы для манипулирования с объектами этого класса. Миллионное число Фибоначчи последняя программа находит почти в два с половиной раза быстрее, чем предыдущая, и разница в скорости их работы увеличивается с ростом номера n числа fn.
[11]
<http://www.research.att.com/~njas/sequences">http://www.research.att.com/~njas/sequences.