Практическая информатика


         

Данная программа использует двойную рекурсию,


ruby fib.rb 30

Данная программа использует двойную рекурсию, поэтому процесс вычисления займет достаточно заметное время.

#!/usr/bin/env ruby

=begin Напишите программу, получающую с качестве аргумента командной строки целое число n, и печатающую n-е число Фибоначчи. =end

def fib(n) if n<2 n else fib(n-2)+fib(n-1) end end t1 = Time.now n = ARGV[0].to_i puts "#{n}-е число Фибоначчи равно #{fib(n)}" t2 = Time.now puts "Время расчета около #{(t2-t1).round} сек."

Пример 1.11.

Вариант 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}"#!/usr/bin/env ruby

=begin Напишите программу, получающую с качестве аргумента командной строки целое число n, и печатающую n-е число Фибоначчи. =end t1 = Time.now 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}" t2 = Time.now puts "Время расчета около #{(t2-t1).round} сек." a = fib.to_s.split('") puts "Количество цифр в #{n}-м числе Фибоначчи равно #{a.size}."

Пример 1.12.

Однако и у этой программы есть существенный недостаток - она хранит все промежуточные результаты, в то время как каждое предыдущее значение используется лишь дважды. Изменим программу так, чтобы она использовала только три переменных: вычисляемое значение и два предшествующих ему:

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}"#!/usr/bin/env ruby

=begin Напишите программу, получающую с качестве аргумента командной строки целое число n, и печатающую n-е число Фибоначчи. =end t1 = Time.now 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}" t2 = Time.now puts "Время расчета около #{(t2-t1).round} сек." a = fib.to_s.split("') puts "Количество цифр в #{n}-м числе Фибоначчи равно #{a.size}."

Пример 1.13.

Включите в рассмотренные программы операторы, информирующие о продолжительности вычислений, и сравните их эффективность. Для этого найдите с помощью первой из рассмотренных программ 30, 31 и 32 числа Фибоначчи. Пользуясь второй и, тем более, третьей вы сможете вычислить достаточно большое число Фибоначчи, например, для вычисления 60000-го числа Фибоначчи, содержащего 12539 цифр на компьютере с процессором Celeron-500, программе, размещающей промежуточные результаты в массиве, потребовалось около 19 секунд, в то время как последняя программа вычислила его за 2 секунды.


Содержание  Назад  Вперед