Код Фибоначчи Гольф
https://stackoverflow.com/questions/232861
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Сгенерируйте последовательность Фибоначчи, используя наименьшее количество символов.Подойдет любой язык, за исключением того, который вы определяете с помощью одного оператора, f, который печатает числа Фибоначчи.
Отправная точка: 25 14 символов в Хаскелл:
f=0:1:zipWith(+)f(tail f)
f=0:scanl(+)1f
Решение
ОТВЕТИТЬ, 9 , 8 символов
1↓[2?+1]
Или 10 символов с печатью:
1↓[2?+↓£1]
Запустить с помощью:
RePeNt "1↓[2?+1]"
RePeNt - это основанный на стеке игрушечный язык, который я написал (и продолжаю совершенствовать), в котором все операторы / функции / блоки / циклы используют обратную польскую нотацию (RPN).
Command Explanation Stack
------- ----------- -----
1 Push a 1 onto the stack 1
↓ Push last stack value 1 1
[ Start a do-while loop 1 1
2? Push a two, then pop the 2 and copy the last 2 stack 1 1 1 1
items onto the stack
+ Add on the stack 1 1 2
↓£ Push last stack value then print it 1 1 2
1 Push a 1 onto the stack 1 1 2 1
] Pop value (1 in this case), if it is a 0 exit the loop 1 1 2
otherwise go back to the loop start.
Ответ на стек, который строит себя как:
1 1
1 1 2
1 1 2 3
1 1 2 3 5
Он никогда не завершается (он имеет эквивалент цикла C # / JAVA do { } while(true)), потому что последовательность никогда не завершится, но завершающее решение можно записать так:
N_1↓nI{2?+}
что составляет 12 символов.
Интересно, кто-нибудь когда-нибудь прочтет это? (
Другие советы
18 символов английского языка.
" последовательность Фибоначчи "
хорошо, я терплю неудачу. :)
13 символов Golfscript :
2,~{..p@+.}do
Обновление для объяснения работы скрипта:
<Ол>2, создает массив из [0 1] ~ помещает этот массив в стек do мы начинаем стек с 0 1 (1 сверху стека) Цикл .:
0 1 1 1 дублирует верхний элемент стека; здесь мы делаем это дважды (оставляя нас с p при первом запуске) 0 1 1 печатает самое верхнее значение (оставляя нас с @) 1 1 0 вращает верхние 3 элемента в стеке, так что третий самый верхний находится сверху (+) 1 1 добавляет 2 верхних элемента в стек (оставляя <=>) С помощью умственного отслеживания пары циклов будет достаточно, чтобы сказать вам, что это делает необходимое дополнение для генерации значений последовательности Фибоначчи.
Поскольку в GolfScript есть bignums, переполнение целых чисел никогда не произойдет, поэтому значение вершины стека в конце цикла <=> никогда не будет равно 0. Таким образом, скрипт будет работать вечно.
Язык: ошибки компилятора C ++
Персонажи: 205
#define t template <int n> struct
#define u template <> struct f
t g { int v[0]; };
t f { enum { v = f<n-1>::v + f<n-2>::v }; g<v> x;};
u<1> { enum { v = 1 }; };
u<0> { enum { v = 0 }; };
int main() { f<10> x; }
Perl 6 - 22 символа:
sub f{1,1...{$^a+$^b}}
x86 (C-callable) реальный режим, 14 байтов.
Ввод & Nbsp; & Nbsp; n & Nbsp; & Nbsp; в стеке возвращает & Nbsp; & Nbsp; F n & Nbsp ; & nbsp; в AX.
59 31 C0 E3 08 89 C3 40 93 01 D8 E2 FB C3
Brainfuck , 33 символа:
+.>+.[<[>+>+<<-]>.[<+>-]>[<+>-]<]
22 символа с постоянным током:
1[pdd5**v1++2/lxx]dsxx
Вызовите с помощью:
dc -e'1[pdd5**v1++2/lxx]dsxx'
Или:
echo '1[pdd5**v1++2/lxx]dsxx' | dc
Примечание:не моя работа, браконьерство Перлмонкс.
J , 27 символов для нерекурсивной функции:
f=:3 :'{:}.@(,+/)^:y(0 1x)'
+/ суммы по списку.
(,+/) добавляет сумму списка к своему хвосту.
}.@(,+/) суммирует список, добавляет элемент к его хвосту и удаляет первый элемент.
}.@(,+/)^:y повторяет вышеуказанную функцию y раз.
}.@(,+/)^:y(0 1x) применяет вышеуказанную функцию к списку (0,1) (x делает его целым числом).
{:}.@(,+/)^:y(0 1x) занимает последний элемент списка вывода из приведенного выше.
f=:3 :'{:}.@(,+/)^:y(0 1x)' определяет f как функцию для одной переменной <=>.
Для записи:
- Луа (66 символов):
function f(n)if n<2 then return n else return f(n-1)+f(n-2)end end - JavaScript (41 символ):
function f(n){return n<2?n:f(n-1)+f(n-2)} - Java (41 символ):
int f(int n){return n<2?n:f(n-1)+f(n-2);}
Я не очень разбираюсь в сверхкратких языках...:-П
Крис прав, я просто взял простой рекурсивный алгоритм.На самом деле, в Lua линейный еще короче (благодаря множественному присваиванию)!JavaScript не так удачлив, а Java еще хуже, поскольку приходится объявлять переменные...
- Луа (60 символов):
function f(n)a=1;b=0;for i=1,n do a,b=b,a+b end return b end - JavaScript (60 символов):
function f(n){a=1;b=i=0;for(;i++<n;){x=a+b;a=b;b=x}return b} - Java (71 символ):
int f(int n){int a=1,b=0,i=0;for(;i++<n;){int x=a+b;a=b;b=x;}return b;}
Я бы написал код Lua с помощью local a,b=1,0 но оно длиннее, так что давайте загрязнять _G!;-) То же самое для JS.
Для полноты вот терминальные рекурсивные версии.Lua, использующий хвостовой вызов, так же быстр, как и линейный (но 69 символов, он самый длинный!) - их нужно вызывать с тремя параметрами, n,1,0.
- Lua (69 символов, длиннее!):
function f(n,a,b)if n<1 then return b else return f(n-1,b,a+b)end end - JavaScript (44 символа):
function f(n,a,b){return n<1?b:f(n-1,b,a+b)} - Java (52 символа):
int f(int n,int a,int b){return n<1?b:f(n-1,b,a+b);}
Исправлено после комментариев (спасибо Себастьяну), это не было решением последовательности, поэтому здесь мы используем 42 символа (включая ):
def f(a=0,b=1):
while 1:yield a;a,b=b,a+b
СТАРЫЙ пост ниже
Питон, 38 символов.
f=lambda n:n if n<2 else f(n-1)+f(n-2)
Не такой короткий, но, на мой взгляд, самый читабельный :P
РЕДАКТИРОВАТЬ:Вот аналитический способ (если кому-то нужно увидеть это в Python :-)
f=lambda n:int(.5+(.5+5**.5/2)**n/5**.5)
Пакетный скрипт Windows XP (и более поздние версии). Эта пакетная функция, когда ей присваивается единственный аргумент - количество, генерируется число + 1 чисел Фибоначчи и возвращает их в виде строки (в действительности пакет не имеет наборов) в переменной% r% (369 символов или 347 символов - если мы удалили отступ)
:f
set i=0
set r=1
set n=1
set f=0
:l
if %n% GTR %~1 goto e
set f=%f% %r%
set /A s=%i%+%r%
set i=%r%
set r=%s%
set /A n+=1
goto l
:e
set r=%f%
exit /B 0
А вот полный сценарий, чтобы увидеть его в действии (просто скопируйте его в файл CMD или BAT и запустите его):
@echo off
call :ff 0
call :ff 1
call :ff 2
call :ff 3
call :ff 5
call :ff 10
call :ff 15
call :ff 20
exit /B 0
:ff
call :f "%~1"
echo %~1: %r%
exit /B 0
:f
set i=0
set r=1
set n=1
set f=0
:l
if %n% GTR %~1 goto e
set f=%f% %r%
set /A s=%i%+%r%
set i=%r%
set r=%s%
set /A n+=1
goto l
:e
set r=%f%
exit /B 0
Пакет Microsoft - 15 символов
Старый вызов, но мир должен знать, что это возможно:
%1
%0 %1%2 %1 #
Выводить в stderr в унарном виде, считая только # символов. В зависимости от ограничения пространства в хост-системе, она может выдавать только первые 14 цифр или около того.
Язык: dc, Количество символов: 20
Сокращенное решение для постоянного тока.
dc -e'1df[dsa+plarlbx]dsbx'
Ф#:
(0,1)|>Seq.unfold(fun(a,b)->Some(a,(b,a+b)))
44 символа
Вот моя лучшая схема из 45 символов:
(let f((a 0)(b 1))(printf"~a,"b)(f b(+ a b)))
MS Excel:11 символов:
=SUM(A1:A2)
Тип 1 в двух верхних ячейках, затем поместите приведенную выше формулу в ячейку A3.Скопируйте формулу в таблицу.
Начинает терять точность из-за округления с плавающей запятой в строке 74.
Превышает 10^307 и переполняется до #NUM! ошибка в строке 1477.
Генерация последовательности Фибоначчи. последовательность ПОСЛЕДОВАТЕЛЬНОСТЬ!
С#
Я вижу много ответов, которые на самом деле не генерируют последовательность, а вместо этого дают вам только число Фибоначчи в позиции *n с использованием рекурсии, которая при зацикливании для генерации последовательности становится все медленнее при более высоких значениях н.
using System;
static void Main()
{
var x = Math.Sqrt(5);
for (int n = 0; n < 10; n++)
Console.WriteLine((Math.Pow((1 + x) / 2, n) - Math.Pow((1 - x) / 2, n)) / p) ;
}
let rec f l a b =function 0->a::l|1->b::l|n->f (a::l) b (a+b) (n-1) in f [] 1 1;;
80 символов, но действительно генерирует последовательность в линейном времени.
Ruby (30 символов):
def f(n)n<2?n:f(n-1)+f(n-2)end
@ Андреа Амбу
Версия итеративного питона fibonacci() должна выглядеть примерно так:
def fibonacci(a=0, b=1):
while True:
yield b
a, b = b, a+b
Lua - 49 символов
function f(n)return n<2 and n or f(n-1)+f(n-2)end
Befunge-93
31 символ
Выводит бесконечный список чисел Фибоначчи от 0 и выше, разделенных табуляцией (можно уменьшить до 29 символов, удалив 9, в первой строке, за счет отсутствия пробелов между числами).
К сожалению, все интерпретаторы Befunge-93, которые я пробовал, переполняются после 65 тыс., поэтому выходные данные верны только до 46368 включительно (что составляет F 24 ). ).
#v::1p1>01g:.\:01p+9,# > ^
Подтверждено работа (с оговоркой выше) с интерпретатором Befunge-93 в Javascript и Полный апплет Visual Befunge .
Я с гордостью могу сказать, что это совершенно оригинальная работа (то есть я никому не копировал этот код), и она намного короче, чем решение Befunge, которое в настоящее время используется в Rosetta Code .
Мозговой Блядь:
>+++++>+>+<[[>]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[>+>+<<-]>>[<<+>>-]<[<]>-]
Это сгенерирует первые 5.Чтобы генерировать больше, замените 5+ в начале на more:например:
>++++++++++++++++++++++>+>+<[[>]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[>+>+<<-]>>[<<+>>-]<[<]>-]
Не самый короткий, но самый быстрый на момент публикации. : -)
float f(float n) {
return (pow(1+sqrt(5.0))/2.0),n) - pow(1+sqrt(5.0))/2.0),n)/sqrt(n));
}
33 символа в C:
F(n){return n<2?n:F(n-1)+F(n-2);}Delphi Prism (Delphi для .net)
f:func<int32,int32>:=n->iif(n>1,f(n-1)+f(n-2),n)
49 символов
Предыдущий пример Ruby не будет работать без точек с запятой или новой строки, поэтому на самом деле он содержит 32 символа.Вот первый пример, который фактически выводит последовательность, а не просто возвращает значение указанного индекса.
Рубин:
53 символа, включая символы новой строки:
def f(n);n<2?1:f(n-1)+f(n-2);end
0.upto 20 {|n|p f n}
или если вам нужна функция, которая выводит полезную структуру данных, 71 символ:
def f(n);n<2?1:f(n-1)+f(n-2);end
def s(n);(0..n).to_a.map {|n| f(n)};end
или принимая аргументы командной строки, 70 символов:
def f(n);n<2?1:f(n-1)+f(n-2);end
p (0..$*[0].to_i).to_a.map {|n| f(n)}
Ассемблер PDP-11 ( источник )
.globl start
.text
start:
mov $0,(sp)
mov $27,-(sp)
jsr pc, lambda
print_r1:
mov $outbyte,r3
div_loop:
sxt r0
div $12,r0
add $60,r1
movb r1,-(r3)
mov r0,r1
tst r1
jne div_loop
mov $1,r0
sys 4; outtext; 37
mov $1,r0
sys 1
lambda:
mov 2(sp),r1
cmp $2,r1
beq gottwo
bgt gotone
sxt r0
div $2,r0
tst r1
beq even
odd:
mov 2(sp),r1
dec r1
sxt r0
div $2,r0
mov r0,-(sp)
jsr pc,lambda
add $2,sp
mov r0,r3
mov r1,r2
mov r3,r4
mul r2,r4
mov r5,r1
mov r3,r4
add r2,r4
mul r2,r4
add r5,r1
mul r3,r3
mov r3,r0
mul r2,r2
add r3,r0
rts pc
even:
mov 2(sp),r1
sxt r0
div $2,r0
dec r0
mov r0,-(sp)
jsr pc,lambda
add $2,sp
mov r0,r3
mov r1,r2
mov r2,r4
mul r2,r4
mov r5,r1
mov r2,r4
add r3,r4
mul r4,r4
add r5,r1
mov r2,r4
add r3,r4
mul r2,r4
mov r5,r0
mul r2,r3
add r3,r0
rts pc
gotone:
mov $1,r0
mov $1,r1
rts pc
gottwo:
mov $1,r0
mov $2,r1
rts pc
.data
outtext:
.byte 62,63,162,144,40,106,151,142,157,156
.byte 141,143,143,151,40,156,165,155
.byte 142,145,162,40,151,163,40
.byte 60,60,60,60,60
outbyte:
.byte 12
