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

Пример 6. Напечатайте квадраты всех натуральных чисел, не больших тысячи, десятичная запись которых заканчивается на 396.

p(1..1000).map{|t|t*t}.select{|x|x%1000==396}

Для решения задачи достаточно применить метод map (или collect), возвращающий массив, содержащий результаты применения заданного блока к элементам коллекции, а затем выбрать из него нужные числа. Метод p печатает массив (как и иные объекты) в более удобном виде, чем puts.

Пример 7. Выясните, является ли заданная в командной строке последовательность символов палиндромом. Напомним, что палиндром – это последовательность, которая не изменяется после её инвертирования (переворачивания). Ограничимся в этой задаче только малыми русскими буквами и пробелами, которые должны игнорироваться. Вот примеры палиндромов: «поп», «шалаш», «аргентина манит негра», «а роза упала на лапу азора». Если программа, решающая эту задачу, содержится в файле palindrome.rb, то команда ruby palindrome.rb аргентина манит негра должна напечатать true.

defprime?(n)

     not(2...n).any?{|i|n%i==0}

end

(15_485_800..15_485_863).eachdo|x|

     puts x if prime?(x)

end

Как мы уже знаем, объект ARGV содержит массив аргументов командной строки. Метод join класса Array «склеивает» в одну строку все его элементы, а метод reverse класса String инвертирует строку.

p ARGV.join==ARGV.join.reverse

   Время, потраченное на знакомство с библиотеками Ruby, многократно окупится в дальнейшем.

Пока мы использовали только методы, определённые для классов и модулей стандартной библиотеки, но часто при написании программ полезно создавать свои методы. Например, при решении задачи о простоте числа естественно определить метод prime? с одним параметром (числом), возвращающий true или false. Затем его можно использовать для того, чтобы найти и напечатать все простые числа из диапазона 15_485_800..15_485_863. Подробнее про определение методов рассказано далее.

Пример 8. Реализованный выше метод prime? работает достаточно медленно. Говорят, что его сложность линейна[6], ибо для простых чисел выполняется почти n итераций. Реализуйте метод prime?, работающий быстрее.

Заметим, что если n = pq, то одно из чисел p и q заведомо не превосходит √n. До этой величины и достаточно выполнять проверку[7]. Для вычисления квадратного корня используем метод sqrt модуля Math.

def prime?(n) not (2.. Math.sqrt(n)).any?{|i| n%i == 0} end (15_485_800.. 15_485_863).each{ |x| puts x if prime?(x) }

   Без знания математики хорошей программы не напишешь.

Пример 9. Многочлен можно задать массивом его коэффициентов. Например, многочлену x³+2x – 3 соответствует массив [1,0,2, – 3], а массив [1,2] задаёт многочлен x + 2. Реализуйте метод, позволяющий перемножать два многочлена, заданные их коэффициентами.

На самом деле для написания программы эта формула совершенно не нужна. Достаточно заметить, что степень итогового многочлена на единицу меньше суммы степеней исходных, перемножать необходимо каждый из коэффициентов первого многочлена a_i на каждый из коэффициентов второго b j, а получающееся произведение aibj следует добавлять к коэффициенту итогового многочлена при степени i + j. Реализовать данную идею проще всего с помощью метода each_with_index модуля Enumerable, который последовательно выполняет заданный блок для всех элементов коллекции, передавая в него сам элемент и его индекс. Метод size класса Array используется для определения количества элементов в нём, а метод new с двумя параметрами этого же класса создаёт новый массив указанного размера, заполненный нулями. Массивы в Ruby применяют очень часто, так как их можно использовать в качестве стеков, очередей, деков, списков и других структур данных.

def mul(p,q)

     r=Array.new(p.size+q.size-1,0)

     p.each_with_indexdo|u,i|

      q.each_with_indexdo|v,j|

           r[i+j] += u*v

      end

     end

     r

     end

p mul([1,0,2,-3],[1,2])

Пример 10. Реализованный в примере 8 метод prime? является слишком медленным для получения списка всех простых чисел от 2 до миллиона.

Напишите программу, решающую эту задачу за «разумное время».

n=Integer(ARGV[0])

sieve=[]

for i in 2..n

     sieve[i] = i

end

for i in2..Math.sqrt(n)

     next unlesssieve[i]

     (i*i).step(n,i){|j|sieve[j]=nil}

end

psieve.compact