НОД и алгоритм Евклида
При рассмотрении задач, связанных с обработкой целых чисел, часто приходится сталкиваться с понятием НОД - наибольшего общего делителя чисел. Известно много алгоритмов вычисления НОД, мы рассмотрим лишь два из них.
Задача
Напишите программу, вычисляющую НОД(a,b) - наибольший общий делитель двух введенных с клавиатуры неотрицательных целых чисел a и b, не равных нулю одновременно.
Вариант 1
Определим максимум из этих чисел и, последовательно уменьшая его, будем искать число, на которое делятся и a и b. Программа обязательно завершит свою работу, так как в самом неудачном случае, когда эти числа взаимно просты, k станет равно 1, а на 1 делятся все числа, следовательно выполнение цикла прекратится.
print "Введите первое число: "; a = gets.to_i
print "Введите второе число: "; b = gets.to_i
k = a >= b ? a : b # теперь k - максимум
until (a % k == 0) and (b % k == 0)
k -= 1
end
print "НОД(#{a},#{b}) = #{k}\n"
Вариант 2 - алгоритм Евклида
Алгоритм Евклида основан на следующих свойствах НОД: для всех a и b, больших или равных 0, выполнены равенства
НОД(a, b) = НОД(a - b, b)= НОД(a, b - a); НОД(a, 0) = НОД(0, a) = a
Ниже приведен текст программы, реализующей алгоритм Евклида.
print "Введите первое число: "; a = gets.to_i
print "Введите второе число: "; b = gets.to_i
m, n = a, b
while !((m == 0) || (n == 0))
if m >= n
m = m - n
else
n = n - m
end
end
k = m == 0 ? n : m
print "НОД(#{a},#{b}) = #{k}\n"
Аргументы командной строки
Как и другие языки программирования, Ruby позволяет передавать данные в программу, использую аргументы командной строки. Все, что при старте программы указывается после ее имени, интерпретатор помещает в специальный массив ARGV, работа с элементами которого нечем не отличается от работы с другими массивами. Можно, например, проверить, с правильным ли количеством аргументов командной строки была вызвана программа. Далее приводится программа, прерывающий свое выполнение, если число аргументов меньше 2:
=begin
Напишите программу подсчета суммы всех нечетных
чисел, заключенных в интервале от K до L,
где K и L - аргументы командной строки
=end
if ARGV.length < 2
puts "Слишком мало входных данных"
exit(1)
end
s = 0
k = ARGV[0].to_i
l = ARGV[1].to_i
for i in k .. l
s += i if i%2 != 0
end
puts "Сумма нечетных чисел в интервале " +
"от #{k} до #{l} равна #{s}"
Для экстренного прерывания процесса выполнения программы здесь использован встроенный метод exit.
Задача
Числами Фибоначчи называется последовательность целых чисел, задаваемая соотношениями: а0 = 0, a1 = 1, an = an-1+an-2. Напишите программу, получающую с качестве аргумента командной строки целое число n, и печатающую n-е число Фибоначчи.
Вариант 1 - рекурсивная функция
В следующей программе первый элемент массива ARGV преобразовывается в целое число и передается в качестве аргумента рекурсивной функции fib.
def fib(n)
if n<2
n
else
fib(n-2)+fib(n-1)
end
end
n = ARGV[0].to_i
puts "#{n}-е число Фибоначчи равно #{fib(n)}"
Для вычисления с помощью этой программы, размещенной в файлe fib.rb, например, 30-го числа Фибоначчи достаточно выполнить команду
ruby fib.rb 30
Данная программа использует двойную рекурсию, поэтому процесс вычисления займет достаточно заметное время.
Вариант 2 - использование массива
В следующем варианте решения этой задачи каждое число Фибоначчи вычисляется лишь один раз и сразу заносится в массив. Для определения очередного элемента массива достаточно сложить два предыдущих.
n =ARGV[0].to_i
f= [0, 1]
fib = case n
when 0
f[0]
when 1
f[1]
else
for i in 2 .. n
f[i] = f[i-1] + f[i-2]
end
f[n]
end
puts "#{n}-е число Фибоначчи равно #{fib}"
Однако и у этой программы есть существенный недостаток - она хранит все промежуточные результаты, в то время как каждое предыдущее значение используется лишь дважды. Изменим программу так, чтобы она использовала только три переменных: вычисляемое значение и два предшествующих ему:
n =ARGV[0].to_i
if n > 1
prev, beforePrev = 1, 0
for i in 2 .. n
fib = prev + beforePrev
prev, beforePrev = fib, prev
end
else
fib = n
end
puts "#{n}-е число Фибоначчи равно #{fib}"
Включите в рассмотренные программы операторы, информирующие о продолжительности вычислений, и сравните их эффективность. Для этого найдите с помощью первой из рассмотренных программ 30, 31 и 32 числа Фибоначчи. Пользуясь второй и, тем более, третьей вы сможете вычислить достаточно большое число Фибоначчи, например, для вычисления 60000-го числа Фибоначчи, содержащего 12539 цифр на компьютере с процессором Celeron-500, программе, размещающей промежуточные результаты в массиве, потребовалось около 19 секунд, в то время как последняя программа вычислила его за 2 секунды.
Работа с файлами
Ввод данных с клавиатуры в процессе выполнения программы удобен только в случае небольших объемов. В других ситуациях необходимо чтение информации из заранее подготовленного файла.
Для работы с файлом при помощи метода new создается экземпляр класса File. Обязательным аргументом этого метода является строка, содержащая имя файла, например,
f = File.new("myfile.txt")
Другим (необязательным) аргументом является задание режима работы с файлом. По умолчанию этот параметр имеет значение "r", что соответствует режиму "только чтение". Если требуется открыть файл с возможностью записи в него, то следует указать параметр "w", например,
f1 = File.new("newfile.txt", "w")
Метод readlines считывает весь файл, создает массив и размещает каждую прочитанную строку в отдельном элементе массива При дальнейшей обработке полученного массива удобно использовать метод each.
Для вывода строки в выходной поток (в файл или на экран монитора) используется метод write, например,
a = "Hello, world!" f1.write(a)
Задача
Имеется текстовый файл fio.txt, содержащий список фамилий, имен и отчеств учащихся. При этом каждая строка файла содержит данные только об одном человеке, например,
Петров Сергей Васильевич Сидорова Ольга Петровна Иванова Марья Даниловна
Напишите программу, которая читает информацию из файла и
1) печатает пронумерованный список учеников;
2) печатает пронумерованный список фамилий и инициалов.
Решение 1
f = File.new("fio.txt")
n = 1
student = f.readlines
student.each{ |i|
print n, ". ", i
n += 1
}
Отметим, что программа должна располагаться в той же директории, что и файл с данными. В противном случае необходимо указывать полный путь к этому файлу.
Для получения инициалов каждую строку полученного массива преобразуем в массив, элементами которого будут фамилия, имя и отчество. Затем фамилию печатаем полностью, а вместо следующих элементов массива - только их первый символ. Для преобразования строки в массив используется ранее рассмотренная функция split. Напомним, что параметром по умолчанию этой функции является пробел.
Решение 2
f = File.new("fio.txt")
n = 1
student = f.readlines
student.each{ |i|
i.chop!
fio = i.split
print n, ". ", fio[0], " ", fio[0][0].chr, ". ",
fio[1][0].chr, ".\n"
n += 1
}
Случайные числа
Моделирование случайных процессов на компьютере - достаточно распространенное явление. Как и в большинстве языков программирования в Ruby есть методы, генерирующие, так называемые, "псевдослучайные" числа (их нельзя считать чисто случайными, ведь создаются они при помощи некоторого алгоритма).
Для получения случайного целого числа в диапазоне от 0 до n используется метод rand(n). Случайное число в диапазоне от 0 до 1 получается с помощью этого же метода без указания параметра.
a1 = (1..10).collect { |j| rand(100)}
a2 = (1..4).collect { |j| rand()}
p a1, a2
Ниже представлен возможный вывод:
[64, 17, 21, 95, 58, 24, 29, 60, 47, 63] [0.2009671596, 0.8890923676, 0.3349569312, 0.8719313448]
Одним из применений случайных чисел является компьютерное моделирование метода Монте-Карло для определения площади некоторой фигуры, рассмотренный нами ранее. Напомним, что для применения этого метода фигуру вписывают в другую, известной площади, и случайным образом "бросают" точки, подсчитывая число попаданий в фигуру. При достаточно большом числе испытаний отношение числа точек, попавших внутрь фигуры, к общему числу точек, стремится к отношению их площадей.
Задача
Напишите программу, вычисляющее приближенное значение числа PI при помощи метода Монте-Карло.
Решение
Число PI равно отношению площади круга к квадрату его радиуса. Впишем круг единичного радиуса с центром в начале координат в квадрат и методом Монте-Карло найдем его площадь. Координаты случайных точек, бросаемых в круг, принадлежат интервалу (-1; 1). Величина, случайно распределенная в этом интервале, задается выражением 2*rand() - 1.
Для контроля за временем добавим два экземпляра класса Time: время начала и окончания расчета. Программа, реализующая этот алгоритм, представлена ниже. В ней используется оператор eval, чтобы количество точек можно было задавать в виде арифметического выражения.
puts "Введите количество точек:"
n1, n, t1 = 0, eval(gets.chop), Time.now
for i in 1 .. n
x = 2*rand() - 1
y = 2*rand() - 1
# проверяем попадание внутрь круга
n1 += 1 if (x**2 + y**2) < 1
end
puts "PI=#{4.0*n1/n}"
t2 = Time.now
puts "Число точек #{n}, время расчета " +
"около #{(t2 - t1).round} сек."
Возможные результаты работы программы будут похожи (случайность!) на следующие:
Введите количество точек: 10**5 PI=3.14028 Число точек 100000, время расчета около 2 сек. Введите количество точек: 10**6 PI=3.142204 Число точек 1000000, время расчета около 20 сек.
Разработка пользовательских классов
Пример программы на языке Ruby, демонстрирующий работу с классами, уже приводился в главе 9. Следующий пример демонстрирует использование так называемой переменной класса, которая не принадлежит ни одному из экземпляров данного класса, а используется для хранения информации, относящейся ко всему классу в целом.
Задача
Напишите программу, описывающую класс автомобиль и два его дочерних класса: спортивные машины и машины для семейного использования. В программе нужно предусмотреть возможность печати общего числа созданных автомобилей.
Решение
Поместите в файл с именем car.rb следующую программу:
class Car @@NUM_CARS = 0 def initialize @@NUM_CARS = @@NUM_CARS + 1 puts @@NUM_CARS end end class SportsCar < Car end class FamilyCar < Car end a = Car.new b = SportsCar.new c = FamilyCar.new
Для запуска программы выполните команду ruby car.rb. При создании каждого автомобиля, независимо от того, к какому (родительскому или дочернему) классу он принадлежит, значение переменной класса @@NUM_CARS увеличивается на единицу.
Задания
- Напишите программу, запрашивающую с клавиатуры натуральное число, большее 1, и печатающую список всех простых несократимых дробей, заключенных в интервале между 0 и 1, знаменатели которых не превышают введенное число. Например, если ввести число 4, то должна быть напечатана последовательность 1/2, 1/3, 2/3, 1/4, 3/4. Подсказка: используйте функцию нахождения НОД.
- Создайте текстовый файл, в котором разместите фамилии учащихся и их рост в сантиметрах. Напишите программу
а) печатающую фамилию и рост самых высоких учеников;
б) по введенному числу - росту с сантиметрах - печатающую список всех учащихся, чей рост не превышает введенного числа. - Напишите программу, вычисляющую методом Монте-Карло площадь криволинейной трапеции, ограниченной графиками функций y=sin(x) и y=0 (x изменяется в интервале от 0 до PI).