дХОКНЛМШЕ ПЮАНРШ, ЙСПЯНБШЕ ОПНЕЙРШ МЮ ГЮЙЮГ, ЙНМРПНКЭМШЕ ПЮАНРШ МЮ ГЮЙЮГ

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

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

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

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