Mathematica, последовательность Фибоначчи с использованием команд While и Module

Question

Как мне написать программу, которая вычисляет f [n] (для чисел Фибоначчи: f [n] = f [n] -f [n-2], с f [0] = любое число) , используяModule и While петля ?

Answer 1

Если вы пытаетесь произвести впечатление на своего инструктора, я бы использовал подход кеша памяти.Это значительно быстрее, чем подход, описанный Sjoerd.

Рассмотрим эту реализацию

fib[0]:=1
fib[1]:=1
fib[n_]:= (fib[n]=fib[n-1]+fib[n-2])

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

slowfib[0]:=1
slowfib[1]:=1
slowfib[n_]:=slowfib[n-1]+slowfib[n-2]

Вотсравнение во время выполнения:

Map[fib, Range[30]] // AbsoluteTiming

{0.000158, {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 
  987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 
  121393, 196418, 317811, 514229, 832040, 1346269}}

Map[slowfib, Range[30]] // AbsoluteTiming

{6.582185, {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 
987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 
121393, 196418, 317811, 514229, 832040, 1346269}}

Время выполнения намного выше, потому что рекурсивная функция

fib[n_]:=fib[n-1]+fib[n-2]

генерирует n ^ 2 рекурсивных вызова (запишите это на бумаге, если этого не произойдетимеет смысл).С другой стороны, определение

fib[n_]:= fib[n]=fib[n-1]+fib[n-2]

использует преимущества кэширования памяти для вычисления терминов, что приводит к значительно более быстрому времени выполнения, поскольку каждый вызов генерирует кэшированное значение для fib [x].

Answer 2

Домашнее задание? Я надеюсь, что вы учитесь на примере. ; -)

В вашей теме написано рекурсия, но вы не указываете это в своем вопросе; скорее, вы указываете Module и While. Я пойду с последним.

fib[n_] := 
  Module[{x = 1, y = 0, i = 0},
    While[i++ < n, {x, y} = {y, x + y}];
    y
  ]

Array[fib, 7]

(*  Out[]= {1, 1, 2, 3, 5, 8, 13}  *)

Table[fib[m], {m, 1,10}] 

(*  Out[]= {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}  *)

Answer 3

Если исходить из первой части вашего заголовка, следующий подход будет примером того, как это сделать:

fib[1] = 1; 
fib[2] = 1; 
fib[n_] := fib[n - 1] + fib[n - 2]

fib[3]
fib[7]

Out[11]= 2

Out[12]= 13

fib /@ Range[20]

Out[10]= {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 
610, 987, 1597, 2584, 4181,  6765}