Программирование на языке Ruby

Более двух тысяч лет назад греческий математик Эратосфен придумал алгоритм, называемый сейчас «решетом Эратосфена» [8]. В простейшем варианте он выглядит так. Выпишем сначала все числа от 2 до n. Затем отметим первое простое число 2 и вычеркнем все числа, кратные ему. Далее отметим первое из ещё не отмеченных и не вычеркнутых чисел (это будет число 3), и вычеркнем все числа, кратные ему (включая и те, которые уже вычеркнуты). Будем продолжать данный процесс, пока это возможно. В итоге останутся только простые числа. Слегка модифицированный алгоритм приводит к программе, которая через несколько секунд после её запуска командой ruby sieve.rb 1000000 печатает список всех простых чисел, меньших миллиона. Первая инструкция программы содержит вызов метода Integer модуля Kernel, который делает почти то же самое[9], что используемый нами ранее метод to_i класса String, – преобразует строку в число. В созданный далее пустой массив sieve заносятся числа от 2 до n с помощью цикла for. Массив при этом растёт: после первого присваивания он содержит три элемента ([nil,nil,2]), после второго – уже четыре и т.д. Цикл for является лишь удобным сокращением для известного нам итератора each: запись for i in 2.. m неявно преобразуется в (2.. m).each do |i|.

В следующем цикле число не обрабатывается, если оно равно nil, то есть уже вычеркнуто (см. таблицу A.12 на стр. 49). Вычёркивание всех ему кратных осуществляет итератор min.step(limit,step){|i| block} класса Numeric, который выполняет block, начиная со значения i=min, увеличивая его после каждой итерации на step до тех пор, пока оно не станет больше, чем limit. Воспользуйтесь командой ri compact для выяснения того, что делает метод compact.

Учитесь находить нужную Вам информацию в книгах, справочных системах и сети Интернет.

Пример 11. Числами Фибоначчи называют последовательность, задаваемую следующими формулами: f₀ = 0, f₁ = 1, f_n = f_n-1 + f_n-2 для n > 1. Напишите рекурсивный метод вычисления величины f_n.

Числа Фибоначчи встречаются и в науке, и в природе чрезвычайно часто[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. С помощью написанного рекурсивного метода практически невозможно находить числа Фибоначчи f_n для больших значений 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) имеет линейную сложность, ибо количество необходимых для нахождения f_n итераций цикла не превосходит 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 числа f_n.

1.4 Упражнения