Примеры программ

НОД и алгоритм Евклида

При рассмотрении задач, связанных с обработкой целых чисел, часто приходится сталкиваться с понятием НОД - наибольшего общего делителя чисел. Известно много алгоритмов вычисления НОД, мы рассмотрим лишь два из них.


Задача
Напишите программу, вычисляющую НОД(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. Напишите программу, запрашивающую с клавиатуры натуральное число, большее 1, и печатающую список всех простых несократимых дробей, заключенных в интервале между 0 и 1, знаменатели которых не превышают введенное число. Например, если ввести число 4, то должна быть напечатана последовательность 1/2, 1/3, 2/3, 1/4, 3/4. Подсказка: используйте функцию нахождения НОД.
  2. Создайте текстовый файл, в котором разместите фамилии учащихся и их рост в сантиметрах. Напишите программу
    а) печатающую фамилию и рост самых высоких учеников;
    б) по введенному числу - росту с сантиметрах - печатающую список всех учащихся, чей рост не превышает введенного числа.
  3. Напишите программу, вычисляющую методом Монте-Карло площадь криволинейной трапеции, ограниченной графиками функций y=sin(x) и y=0 (x изменяется в интервале от 0 до PI).