Для решения задачи достаточно применить метод 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. Многочлен можно задать массивом его коэффициентов. Например, многочлену x3+2x – 3 соответствует массив [1,0,2, – 3], а массив [1,2] задаёт многочлен x + 2. Реализуйте метод, позволяющий перемножать два многочлена, заданные их коэффициентами.
На самом деле для написания программы эта формула совершенно не нужна. Достаточно заметить, что степень итогового многочлена на единицу меньше суммы степеней исходных, перемножать необходимо каждый из коэффициентов первого многочлена ai на каждый из коэффициентов второго 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
Более двух тысяч лет назад греческий математик Эратосфен придумал алгоритм, называемый сейчас «решетом Эратосфена» [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|.