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


         

Для определения очередного элемента массива


Для определения очередного элемента массива достаточно сложить два предыдущих.

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

Пример 1.12.

(html, txt)

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

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

Пример 1.13.

(html, txt)

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


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