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

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

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

Задача
Напишите программу, вычисляющую НОД(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"

Аргументы командной строки

=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}" 

Задача
Числами Фибоначчи называется последовательность целых чисел, задаваемая соотношениями: а₀ = 0, a₁ = 1, a_n = a_n-1+a_n-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)}"

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}"

Работа с файлами

Ввод данных с клавиатуры в процессе выполнения программы удобен только в случае небольших объемов. В других ситуациях необходимо чтение информации из заранее подготовленного файла.

Для работы с файлом при помощи метода new создается экземпляр класса File. Обязательным аргументом этого метода является строка, содержащая имя файла, например,

f = File.new("myfile.txt")

f1 = File.new("newfile.txt", "w")

Метод readlines считывает весь файл, создает массив и размещает каждую прочитанную строку в отдельном элементе массива При дальнейшей обработке полученного массива удобно использовать метод each.

Для вывода строки в выходной поток (в файл или на экран монитора) используется метод write, например,

a = "Hello, world!"
f1.write(a)

Задача
Имеется текстовый файл fio.txt, содержащий список фамилий, имен и отчеств учащихся. При этом каждая строка файла содержит данные только об одном человеке, например,

Петров Сергей Васильевич
Сидорова Ольга Петровна
Иванова Марья Даниловна

Решение 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

Задания

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).