Числа Фибоначчи
Числа Фибоначчи — числовая последовательность, первые два элемента которой равны 1, а каждый последующий равен сумме двух предыдущих.
Вывод программы должен выглядеть следующим образом: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …
Отметим, что данный пример может быть реализован несколькими способами:
- непосредственно через рекурсивное определение: наименее эффективный способ, позволяющий в то же время продемонстрировать использование рекурсивных функций.
- с сохранением вычисленных чисел в массиве: более эффективный способ, позволяющий продемонстрировать работу с массивами.
- через формулу Бине : наиболее эффективный способ, позволяющий продемонстрировать работу с математическими функциями.
Пример для версий Free Pascal 2.2.4 Turbo Pascal 1.0 Turbo Pascal 2.0 Turbo Pascal 3.0 Turbo Pascal 4.0 Turbo Pascal 5.0 Turbo Pascal 5.5 Turbo Pascal 6.0 Turbo Pascal 7.0
Этот пример использует рекурсивное определение чисел Фибоначчи.
program fibonacci;
function fib(n:integer): integer;
begin
if (n <= 2) then
fib := 1
else
fib := fib(n-1) + fib(n-2);
end;
var
i:integer;
begin
for i := 1 to 16 do
write(fib(i), ', ');
writeln('...');
end.
Пример для версий Euphoria 3.1.1
function fib(integer n)
sequence f
if n = 1 then
return {1}
elsif n = 2 then
return {1,1}
else
f = fib(n-1)
f = append(f, f[$-1] + f[$])
return f
end if
end function
print(1,fib(16))
Пример для версий Corman Common Lisp 3.0
(defun fibonacci (n)
(if (< n 3)
1
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))
)
)
(loop for i from 1 to 16
do (format t "~D, " (fibonacci i))
finally (format t "...~%")
)
Пример для версий Borland C++ Builder 6 Microsoft Visual C++ 6
#include <iostream>
int fibonacci(int n)
{
return (n<=2 ? 1 : fibonacci(n-1) + fibonacci(n-2));
}
int main(void)
{
for (int n=1; n<=16; n++)
std::cout << fibonacci(n) << ", ";
std::cout << "..." << std::endl;
return 0;
}
Пример для версий gcj 3.4.5 Sun Java 6
Используется рекурсивное определение чисел Фибоначчи.
public class Fibonacci {
static int fibonacci(int n)
{
return (n<=2 ? 1 : fibonacci(n-1) + fibonacci(n-2));
}
public static void main(String[] args)
{
for (int n=1; n<=16; n++)
System.out.print(fibonacci(n)+", ");
System.out.println("...");
}
}
Пример для версий Microsoft Visual Basic 6
Используется рекурсивное определение чисел Фибоначчи.
Option Explicit
Declare Function AllocConsole Lib "kernel32" () As Long
Declare Function FreeConsole Lib "kernel32" () As Long
Declare Function CloseHandle Lib "kernel32" (ByVal hObject As Long) As Long
Declare Function GetStdHandle Lib "kernel32" (ByVal nStdHandle As Long) As Long
Declare Function WriteConsole Lib "kernel32" Alias "WriteConsoleA" _
(ByVal hConsoleOutput As Long, lpBuffer As Any, ByVal _
nNumberOfCharsToWrite As Long, lpNumberOfCharsWritten As Long, _
lpReserved As Any) As Long
Declare Function Sleep Lib "kernel32" (ByVal dwMilliseconds As Long) As Long
Public Function Fibonacci(ByVal n As Integer) As Integer
If (n <= 2) Then
Fibonacci = 1
Else
Fibonacci = Fibonacci(n - 1) + Fibonacci(n - 2)
End If
End Function
Private Sub Main()
'create a console instance
AllocConsole
'get handle of console output
Dim hOut As Long
hOut = GetStdHandle(-11&)
'output string to console output
Dim s As String
Dim i As Integer
For i = 1 To 16 Step 1
s = Fibonacci(i) & ", "
WriteConsole hOut, ByVal s, Len(s), vbNull
Next i
s = "..." & vbCrLf
WriteConsole hOut, ByVal s, Len(s), vbNull
'make a pause to look at the output
Sleep 2000
'close the handle and destroy the console
CloseHandle hOut
FreeConsole
End Sub
Пример для версий QBasic 1.1
Используется рекурсивное определение чисел Фибоначчи. Каждый вызов команды PRINT выводит аргументы в отдельную строку и добавляет пробел перед и после выводимого числа. В результате вывод программы имеет следующий вид:
1 ,
1 ,
2 ,
3 ,
5 ,
8 ,
13 ,
21 ,
34 ,
55 ,
89 ,
144 ,
233 ,
377 ,
610 ,
987 ,
…
DECLARE FUNCTION fibonacci (n)
FOR i = 1 TO 16:
PRINT fibonacci(i); ", "
NEXT i
PRINT "..."
FUNCTION fibonacci (n)
IF (n <= 2) THEN
fibonacci = 1
ELSE
fibonacci = fibonacci(n - 1) + fibonacci(n - 2)
END IF
END FUNCTION
Пример для версий QBasic 1.1
Уже вычисленные числа хранятся в массиве F и извлекаются оттуда для вычисления следующих. Для получения вывода программы в нужном формате числа в массиве конкатенируются в одну строку с нужными разделителями. Функция STR$ преобразует число в строку.
DIM F(16)
F(1) = 1
F(2) = 1
FOR i = 3 TO 16:
F(i) = F(i - 1) + F(i - 2)
NEXT i
DIM S AS STRING
S = ""
FOR i = 1 TO 16:
S = S + STR$(F(i)) + ", "
NEXT i
S = S + "..."
PRINT S
Пример для версий QBasic 1.1
Числа Фибоначчи вычисляются через формулу Бине. За счет погрешностей вычисления с плавающей точкой полученные числа могут незначительно отличаться от действительных; для устранения этого эффекта используется функция INT, отбрасывающая дробную часть числа.
DECLARE FUNCTION FIBONACCI (n)
DIM S AS STRING
S = ""
FOR i = 1 TO 16:
S = S + STR$(INT(FIBONACCI(i) + .1)) + ","
NEXT i
S = S + "..."
PRINT S
FUNCTION FIBONACCI (n)
p1 = ((1 + SQR(5)) * .5) ^ n
p2 = ((1 - SQR(5)) * .5) ^ n
FIBONACCI = (p1 - p2) / SQR(5)
END FUNCTION
Пример для версий Oracle 10g SQL
SQL не поддерживает циклы или рекурсии, кроме того, конкатенация полей из разных строк таблицы или запроса не является стандартной агрегатной функцией. Данный пример использует:
-
формулу Бине и математические функции
ROUND,POWERиSQRTдля вычисления n-ого числа Фибоначчи; -
псевдостолбец
levelдля создания псевдотаблицы t1, содержащей числа от 1 до 16; -
встроенную функцию
SYS_CONNECT_BY_PATHдля упорядоченной конкатенации полученных чисел.
SELECT REPLACE(MAX(SYS_CONNECT_BY_PATH(fib||', ', '/')),'/','')||'...' fiblist
FROM (
SELECT n, fib, ROW_NUMBER()
OVER (ORDER BY n) r
FROM (select n, round((power((1+sqrt(5))*0.5, n)-power((1-sqrt(5))*0.5, n))/sqrt(5)) fib
from (select level n
from dual
connect by level <= 16) t1) t2
)
START WITH r=1
CONNECT BY PRIOR r = r-1;
Пример для версий Müller's Brainfuck 2.0
В примере используется итеративное определение чисел Фибоначчи: два последних числа хранятся в ячейках-переменных c4 и c5 (в начале c4=0, c5=1), число c5 посимвольно выводится на печать (это действие занимает большую часть кода), затем вычисляется следующее число (c6 = c5+c4), и числовая пследовательность сдвигается на одно число вперед (c4 = c5, c5 = c6). Низкоуровневое описание приведено в комментариях к коду, запись “cXvY” означает, что после выволнения команд в строке указатель данных находится в ячейке X, и значение в этой ячейке равно Y.
Классический интерпретатор Brainfuck использует переменные типа byte для хранения значений в ячейках памяти, и 14-16 числа Фибоначчи вызовут ошибку переполнения. Написание длинной арифметики на Brainfuck — задача достаточно трудоемкая, поэтому в примере предполагается, что в ячейках памяти могут храниться числа типа integer.
++++++++++++++++++++++++++++++++++++++++++++ c1v44 : ASCII code of comma
>++++++++++++++++++++++++++++++++ c2v32 : ASCII code of space
>++++++++++++++++ c3v11 : quantity of numbers to be calculated
> c4v0 : zeroth Fibonacci number (will not be printed)
>+ c5v1 : first Fibonacci number
<< c3 : loop counter
[ block : loop to print (i)th number and calculate next one
>> c5 : the number to be printed
block : divide c5 by 10 (preserve c5)
> c6v0 : service zero
>++++++++++ c7v10 : divisor
<< c5 : back to dividend
[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<] c5v0 : divmod algo; results in 0 n d_n%d n%d n/d
>[<+>-] c5 : move dividend back to c5 and clear c6
>[-] c7v0 : clear c7
>> block : c9 can have two digits; divide it by ten again
>++++++++++ c10v10: divisor
< c9 : back to dividend
[->-[>+>>]>[+[-<+>]>+>>]<<<<<] c9v0 : another divmod algo; results in 0 d_n%d n%d n/d
>[-] c10v0 : clear c10
>>[++++++++++++++++++++++++++++++++++++++++++++++++.[-]]c12v0 : print nonzero n/d (first digit) and clear c12
<[++++++++++++++++++++++++++++++++++++++++++++++++.[-]] c11v0 : print nonzero n%d (second digit) and clear c11
<<<++++++++++++++++++++++++++++++++++++++++++++++++.[-] c8v0 : print any n%d (last digit) and clear c8
<<<<<<<.>. c1c2 : print comma and space
block : actually calculate next Fibonacci in c6
>>[>>+<<-] c4v0 : move c4 to c6 (don't need to preserve it)
>[>+<<+>-] c5v0 : move c5 to c6 and c4 (need to preserve it)
>[<+>-] c6v0 : move c6 with sum to c5
<<<- c3 : decrement loop counter
]
<<++... c1 : output three dots
Пример для версий Microsoft SQL Server 2005
Используется итеративное определение чисел Фибоначчи, реализованное через рекурсивный запрос. Каждая строка запроса содержит два соседних числа последовательности, и следующая строка вычисляется как (последнее число, сумма чисел) предыдущей строки. Таким образом все числа, кроме первого и последнего, встречаются дважды, поэтому в результат входят только первые числа каждой строки.
with fibonacci(a, b) as
(
select 1, 1
union all
select b, a+b from fibonacci where b < 1000
)
SELECT cast(a as varchar)+', ' AS [text()]
FROM fibonacci
FOR XML PATH ('')
Пример для версий Icon Version 9
вычисление чисел Фибоначчи с мемоизацией промежуточных результатов
global fib_memo
procedure fib (n)
if n >= 0 then
return ((/fib_memo [n] := fib (n - 2) + fib (n - 1)) | fib_memo [n])
end
procedure main ()
local first, i
fib_memo := table ()
fib_memo [0] := 0; fib_memo [1] := 1
every i := 1 to 20 do {
if \first then writes (", ")
writes (fib (i))
first := 1
}
end
Пример для версий Interactive FP
Этот пример работает так же, как пример факториала, но без добавления функций для читабельности.
{ seq ( = @ [id, %1] -> %<1> ; concat @ [ seq @ - @ [id, %1] , [id] ] ) }
{ fibonacci ( < @ [id, %3] -> %1 ; + @ [ fibonacci @ - @ [id, %1], fibonacci @ - @ [id, %2] ] ) }
&fibonacci @ seq:16
Пример для версий Corman Common Lisp 3.0
Этот пример использует итеративное определение чисел Фибоначчи без запоминания, выраженное через рекурсивный вызов функции fib-iter.
(defun fibonacci (n)
(defun fib-iter (a b count)
(if (zerop count)
b
(fib-iter (+ a b) a (- count 1))
)
)
(fib-iter 1 0 n)
)
(loop for i from 1 to 16
do (format t "~D, " (fibonacci i))
finally (format t "...~%")
)
Пример для версий Visual Prolog 7.2
В этом примере определяются два новых предиката — бинарный fibonacci(N,F) для вычисления N-ого числа Фибоначчи и loop(N) для его вывода на печать. Единожды вычисленные числа не сохраняются для позднейшего использования, поэтому эта реализация неэффективна.
Следует отметить отличие реализаций предикатов от примера для факториала: формулы, описывающие начальные условия, задаются для произвольного значения переменной, но вычисляются до конца только в том случае, если первое правило (N<3 или N=1, соответственно) оценивается как истинное. Кроме того, каждый предикат записан как одна формула, использующая конъюнкцию и дизъюнкцию, а не как набор отдельных формул, использующих только конъюнкцию.
% main.cl
class main
open core
predicates
classInfo : core::classInfo.
fibonacci : (integer N, integer F) procedure (i,o).
loop : (integer N) procedure (i).
predicates
run : core::runnable.
end class main
% main.pro
implement main
open core
constants
className = "main".
classVersion = "".
clauses
classInfo(className, classVersion).
fibonacci(N,F) :-
N < 3, !, F = 1;
fibonacci(N-1,F1), fibonacci(N-2,F2), F = F1 + F2.
loop(N) :-
( N = 1, !, fibonacci(1,F);
loop(N-1), fibonacci(N,F) ),
stdio::write(F, ", ").
clauses
run():-
console::init(),
loop(16),
stdio::write("..."),
programControl::sleep(1000),
succeed().
end implement main
goal
mainExe::run(main::run).
Пример для версий Oracle 10g SQL
Этот пример демонстрирует использование оператора model, доступного начиная с версии Oracle 10g и позволяющего обработку строк запроса как элементов массива. Каждая строка содержит два поля — само число Фибоначчи и конкатенация всех чисел, меньше или равных ему. Итеративная конкатенация чисел в том же запросе, в котором они генерируются, выполняется проще и быстрее, чем агрегация как отдельное действие.
select max(s) || ', ...'
from
(select s
from dual
model
return all rows
dimension by ( 0 d )
measures ( cast(' ' as varchar2(200)) s, 0 f)
rules iterate (16)
( f[iteration_number] = decode(iteration_number, 0, 1, 1, 1, f[iteration_number-1] + f[iteration_number-2]),
s[iteration_number] = decode(iteration_number, 0, to_char(f[iteration_number]), s[iteration_number-1] || ', ' || to_char(f[iteration_number]))
)
);
Пример для версий MySQL 5
Замените TABLE на любую таблицу, к которой есть доступ, например, mysql.help_topic.
select concat(group_concat(f separator ', '), ', ...')
from (select @f := @i + @j as f, @i := @j, @j := @f
from TABLE, (select @i := 1, @j := 0) sel1
limit 16) t
Пример для версий ARIBAS 1.53
Этот пример использует рекурсивное определение чисел Фибоначчи. В ARIBAS по умолчанию используется тип данных integer. group(0) при выводе служит для отмены использования знака подчеркивания для разделения групп цифр.
function fib(n);
begin
if (n < 3) then
return(1);
end;
return(fib(n-1)+fib(n-2));
end;
function fib1_16();
var n;
begin
for n := 1 to 16 do
write(fib(n): group(0), ", ");
end;
writeln("...");
end;
fib1_16().
Пример для версий VB.NET 9 (2008)
Используется рекурсивное определение чисел Фибоначчи.
Module Module1
Function Fibonacci(ByVal n As Integer) As Long
If n < 3 Then
Return 1
Else
Return Fibonacci(n - 1) + Fibonacci(n - 2)
End If
End Function
Sub Main()
For i As Integer = 1 To 16
Console.Write(Fibonacci(i) & ", ")
Next
Console.WriteLine("...")
End Sub
End Module
Пример для версий PHP 5.2.4
Используется рекурсивное определение чисел Фибоначчи.
<?php
function fibonacci($n)
{
if ($n < 3) {
return 1;
}
else {
return fibonacci($n-1) + fibonacci($n-2);
}
}
for ($n = 1; $n <= 16; $n++) {
echo(fibonacci($n) . ", ");
}
echo("...\n")
?>
Пример для версий Oracle 10g SQL
Этот пример использует итеративное определение чисел Фибоначчи. Уже вычисленные числа хранятся в структуре данных varray — аналоге массива.
declare
type vector is varray(16) of number;
fib vector := vector();
i number;
s varchar2(100);
begin
fib.extend(16);
fib(1) := 1;
fib(2) := 1;
s := fib(1) || ', ' || fib(2) || ', ';
for i in 3..16 loop
fib(i) := fib(i-1) + fib(i-2);
s := s || fib(i) || ', ';
end loop;
dbms_output.put_line(s || '...');
end;
Пример для версий gfortran 4.5.0 Intel Visual Fortran 11.1
Используется итеративное определение чисел Фибоначчи. Самое сложное в этом примере — вывод вычисленных значений в нужном формате, в одну строку и без лишних пробелов. Спецификация формата (I3, A, $) означает, что вначале выводится целое число в десятичном формате, шириной ровно три символа, затем выводится строка, и наконец, $ подавляет перевод строки, используемый командой print по умолчанию, так что все выводится в одну строку.
program Fibonacci
integer :: f1,f2,f3,i
i = 1
f1 = 0
f2 = 1
do
f3 = f2 + f1
f1 = f2
f2 = f3
i = i + 1
if (f1<10) then
print '(I1, A, $)', f1, ', '
elseif (f1<100) then
print '(I2, A, $)', f1, ', '
else
print '(I3, A, $)', f1, ', '
end if
if (i==17) then
exit
end if
end do
print *, '...'
end program Fibonacci
Пример для версий Poplog 15.5 (Prolog)
Простая рекурсивная реализация слишком неэффективна с точки зрения памяти, чтобы успешно выполняться в Poplog, поэтому этот пример демонстрирует более сложную технику — рекурсию с запоминанием. Дополнительный предикат memo(Goal) определяется так, что в первый раз, когда оценивается Goal, результат оценки добавляется в базу фактов, и при следующем запросе не переоценивается, а используется как известный факт.
После этого предикат fib(N,F) определяется рекурсивно, но каждый вызов fib “обернут” в предикат memo, поэтому для каждого значения N fib(N,F) оценивается только один раз. При таком подходе печать вычисленных чисел может производиться сразу после их вычисления, без дополнительного цикла.
% fibonacci.pl
:- dynamic(stored/1).
memo(Goal) :-
stored(Goal) -> true;
Goal, assertz(stored(Goal)).
fib(1,1) :- !, write('1, ').
fib(2,1) :- !, write('1, ').
fib(N,F) :-
N1 is N-1, memo(fib(N1,F1)),
N2 is N-2, memo(fib(N2,F2)),
F is F1 + F2,
write(F), write(', ').
% interactive
[-fibonacci].
fib(16,X), write('...'), nl.
Пример для версий Poplog 15.5 (POP-11)
Используется рекурсивное определение чисел Фибоначчи. Пример работает так же, как факториал, но loop возвращает строку, содержащую конкатенацию всех чисел Фибоначчи до n-ого включительно.
define fibonacci(n);
if n < 3
then 1
else fibonacci(n - 1) + fibonacci(n - 2)
endif
enddefine;
define loop(n);
if n>1
then loop(n-1) >< ', ' >< fibonacci(n)
else fibonacci(n)
endif;
enddefine;
loop(16) >< ', ...' =>
Пример для версий Lua 5.0
Используется рекурсивное определение чисел Фибоначчи.
function fibonacci(n)
if n<3 then
return 1
else
return fibonacci(n-1) + fibonacci(n-2)
end
end
for n = 1, 16 do
io.write(fibonacci(n), ", ")
end
io.write("...\n")
Пример для версий Lua 5.0
Вычисленные числа хранятся в ассоциативном массиве fib и извлекаются из него для вычисления следующих. По умолчанию ассоциативные массивы в Lua используют целочисленные ключи, начинающиеся с 1, поэтому команда fib = {1, 1} создает массив с индексами элементов 1 и 2.
fib = {1, 1}
for n = 3, 16 do
fib[n] = fib[n-1] + fib[n-2]
end
for n = 1, 16 do
io.write(fib[n], ", ")
end
io.write("...\n")
Пример для версий SpiderMonkey (Firefox 3.5)
Используется рекурсивное определение чисел Фибоначчи. Пример предназначен для запуска из веб-браузера.
function fibonacci(n)
{ if (n<3)
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}
var i;
document.clear();
for (i = 1; i <= 16; i++)
document.write(fibonacci(i) + ", ");
document.write("...<br />");
Пример для версий GHC 6.10.4
Этот пример использует одну из основных особенностей языка Haskell — возможность ленивых вычислений и использования бесконечных списков. Бесконечный список чисел Фибоначчи fibs определяется при помощи фунции zipWith, которая применяет первый аргумент (функцию двух переменных, в данном случае +) к парам соответствующих элементов второго и третьего аргументов (списков). tail fibs возвращает хвост списка fibs (т.е. все элементы, кроме первого). Таким образом первый элемент списка, возвращаемого zipWith, является суммой первого и второго элементов списка fibs и становится третьим его элементом.
module Main where
import Text.Printf
fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
line n = printf "%d, " $ fibs !! n
main = do
sequence_ $ map line [1..16]
putStrLn "..."
Пример для версий GHC 6.10.4
Этот пример использует рекурсивное определение чисел Фибоначчи через пары соседних чисел в последовательности. На печать выводятся только первые элементы пар.
module Main where
import Text.Printf
fibNextPair :: (Int, Int) -> (Int, Int)
fibNextPair (x, y) = (y, x+y)
fibPair :: Int -> (Int, Int)
fibPair n
| n == 1 = (1, 1)
| otherwise = fibNextPair (fibPair (n-1))
line n = printf "%d, " $ (fst.fibPair) n
main = do
sequence_ $ map line [1..16]
putStrLn "..."
Пример для версий Furry Paws
one = eq.[id, ~1]
dec = sub.[id, ~1]
seq = one -> [~1] ; cat.[seq.dec, [id]]
fibonacci = lt.[id, ~3] -> ~1 ; add.[fibonacci.sub.[id, ~1], fibonacci.sub.[id, ~2]]
main = show.(return @fibonacci.(seq.~16))
Пример для версий gnat 3.4.5
В этом примере используется рекурсивное определение чисел Фибоначчи.
with Ada.Text_IO, Ada.Integer_Text_IO;
procedure Fibonacci is
begin
declare
function Fib (N: Integer) return Integer is
begin
if N<3 then
return 1;
else
return Fib(N-1) + Fib(N-2);
end if;
end Fib;
i: Integer := 1;
begin
loop
Ada.Integer_Text_IO.Put (Item => Fib(i), Width => 1);
Ada.Text_IO.Put (", ");
i := i + 1;
exit when i=17;
end loop;
Ada.Text_IO.Put ("...");
end;
end Fibonacci;
Пример для версий UCBLogo 6.0
Используется рекурсивное определение чисел Фибоначчи. В примере определяются две функции — fibonacci для вычисления значения N-ого числа Фибоначчи и print_fibonacci, которая накапливает числа в строке и выводит их на печать.
to fibonacci :N
ifelse :N < 3 [output 1] [output sum fibonacci :N - 1 fibonacci :N - 2]
end
to print_fibonacci :i :N
make "str fibonacci :i
make "i sum :i 1
make "comma ",
repeat :N - :i + 1 [make "str (word :str :comma fibonacci :i)
make "i sum :i 1]
make "str word str ",...
print str
end
print_fibonacci 1 16
Пример для версий Scala 2.7.7-final
Используется рекурсивное определение чисел Фибоначчи.
object Fibonacci {
def fibonacci(n: Int): Int =
if (n < 3) 1
else fibonacci(n - 1) + fibonacci(n - 2)
def main(args: Array[String]) {
for {i <- List.range(1, 17)}
yield { print(fibonacci(i) + ", ") }
println("...")
}
}
Пример для версий Scala 2.7.7-final
Этот пример демонстрирует возможности использования ленивых вычислений и бесконечных списков в Scala. Бесконечный список чисел Фибоначчи fibs определяется при помощи фунций .zip и .tail по аналогии с примером на Haskell. Пример предназначен для интерактивной интерпретации.
lazy val fib: Stream[Int] = Stream.cons(1, Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)))
fib.take(16).print
Пример для версий gawk 3.1.6 mawk 1.3.3
Используется итеративное определение чисел Фибоначчи. fib — ассоциативный массив, pr — строка.
BEGIN {
fib[1] = 1
fib[2] = 1
for (i=3; i<17; i++)
fib[i] = fib[i-1]+fib[i-2]
pr = ""
for (i=1; i<17; i++)
pr = pr fib[i] ", "
print pr "..."
}
Пример для версий S-lang 2.2.2
В примере используется итеративное определение чисел Фибоначчи. Переменная f явно определена как массив 16 целых чисел. Элементы 0 и 1 массива устанавливаются в 1: для этого операцией [0:1] создается список индексов, к которым следует применить операцию. Встроенная функция string преобразует свой аргумент в его строковое представление.
f = Integer_Type [16];
f[[0:1]] = 1;
for (i=2; i<16; i++)
f[i] = f[i-1] + f[i-2];
s = "...";
for (i=15; i>=0; i--)
s = string(f[i]) + ", " + s;
message (s);
Пример для версий Hanoi Love
В примере используется итеративное определение чисел Фибоначчи.
Стек A большую часть времени пуст и используется для получения константы 1; иногда используется для временного хранения значений (по тому же принципу, что и в оригинальной задаче о Ханойских башнях). Стек B содержит символы, выводимые на печать (запятую и пробел) и два последних числа Фибоначчи из вычисленных программой. Стек C содержит значение 1 для каждого числа Фибоначчи, которое нужно напечатать (в данном случае шесть единиц для печати 6 чисел).
На каждой итерации одно число извлекается из стека C. Если оно положительно (т.е. нужно вычислить и напечатать еще одно число Фибоначчи), верхнее число f2 из стека B извлекается, преобразуется в ASCII-код соответствующей цифры и выводится на печать вместе с запятой и пробелом. После этого следующее число f1 извлекается из стека B и прибавляется к числу f2. Наконец, числа f2 и f1+f2 возвращаются в стек B. Низкоуровневое описание примера приводится в комментариях.
Интерпретатор Hanoi Love использует переменные типа byte для хранения значений в регистре и стеках, поэтому принципиально возможно вычислить только первые 13 чисел Фибоначчи. В действительности пример выводит только первые 6 чисел Фибоначчи, чтобы не усложнять программу печатью двух- и трехзначных чисел (которая выполняется по тому же принципу, что и в Brainfuck, но сложнее).
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; .' B (space) regr = ASCII for space
...;;;;;;;;;;;;.' B (space comma) reg = ASCII for comma
..., A (empty) reg = 1
..'''''' C (6 ones for 6 numbers to print) reg = 1
..`.'...;.' B (space comma 0 1) reg = 1
., C (pop number to reg) reg = 1
.'... D (remembered this place)
: if this number is positive print top number in B and move to next Fibonacci number
..., B (space comma f1) reg = f2
.' C (f2) reg = f2
..;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; "' A (empty) reg = f2 in ASCII (printed)
., B (space comma) reg = f1
.' C (f2 f1) reg = f2
..., "' B (space) reg = comma (printed)
.' C (f2 f1 comma) reg = comma
..., "' ' B (space) reg = space (printed)
.,...' B (space comma) reg = comma
., C (f2) reg = f1
..' A (f1) reg = f1
.., C (empty) reg = f2
...' B (space comma f2) reg = f2
...; A (empty) reg = f1+f2
.' B (space comma f2 f1+f2)
., C (pop number to reg)
., D (get previous command location)
!
...,,,...;; "' "' "' pop everything from B and convert comma to point (printed three times)
Пример для версий j602
В этом примере используется формула Бине.
Запись g =: -: >: %:5 эквивалентна g =: 0.5 * (1 + 5 ^ 0.5) и присваивает имя g значению золотого сечения. Для этого используются следующие функции: %: извлекает квадратный корень из числа, >: увеличивает число на единицу, -: делит число на два. Если в формуле нет скобок, то действия выполняются справа налево.
Запись fibb=: (%:5) %~ g&^ -- (1-g)&^ эквивалентна fibb =: (0.2 ^ 0.5) * (g &^ -- (1-g) &^); таким образом определяется формула для n-ого числа Фибоначчи при заданном n. Функция %~ выполняет операцию деления, но делимое и делитель имеют порядок, обратный традиционному.
i.16 генерирует числа от 0 до 15, включительно.
load 'printf'
g=: -: >: %:5
fibb=: (%:5) %~ g&^ - (1-g)&^
fstr=: '...' ,~ ,~^:4 '%d, '
fstr printf fibb 1+i.16
Пример для версий j602
В этом примере используется рекурсивное определение чисел Фибоначчи. Оператор @. — селектор, выбирающий 1, если аргумент функции меньше или равен 2, и рекурсивное определение в противном случае.
load 'printf'
fibr=: 1:`(-&2 + &fibr -&1) @.(2&<)"0
fstr=: '...' ,~ ,~^:4 '%d, '
fstr printf fibr 1+i.16
Пример для версий Wolfram Mathematica 7.0.1.0
Прогамма выводит первые 20 чисел ряда Фибоначчи. Функция Fibonacci возвращает значение n-го числа ряда. Table[…, {n, 20}]-создать таблицу из 20 элементов (цикл, где инкрементируемая переменная-n)
Table[Fibonacci[n], {n, 20}]
Пример для версий Mercury 10.04
Вычисление и вывод на экран десятого числа последовательности Фибоначчи.
:- module fib.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module int.
:-func fib(int) = int.
fib(N) = (if N =< 2 then 1 else fib(N - 1) + fib(N - 2)).
main(!IO) :-
io.write_string("fib(10) = ", !IO),
io.write_int(fib(10), !IO),
io.nl(!IO).
% Could instead use io.format("fib(10) = %d\n", [i(fib(10))], !IO).
