Мини-гольф по понедельникам: серия коротких соревнований по коду , публикуемых (надеюсь!) Каждый понедельник.

Последовательность, подобная Фибоначчи, получается с использованием того же метода, что и известная последовательность Фибоначчи ; то есть каждое число F (n) находится путем сложения двух предыдущих чисел в последовательности ( F (n) = F (n-1) + F (n-2) ) или путем вычитания следующих двух чисел ( F (n) = F (n + 2) - F (n + 1) ). Основное отличие состоит в том, что эти последовательности могут начинаться с любых двух чисел. Обнуление этих последовательностей является спорным, но сейчас мы собираемся использовать это правило:

• 0-е число в последовательности, подобной Фибоначчи, является последним числом, которое меньше предыдущего числа.

В качестве примера, последовательность Фибоначчи может быть записана как 1, 0, 1, 1, 2, 3, 5..., поэтому 0-е число в последовательности является единственным 0.

Вызов

Цель задачи - написать программу или функцию, которая принимает три целых числа в любом формате:

• A и B , два числа, с которых начинается генерация последовательности.
• N - длина полученной последовательности для вывода.

И выводит первые N чисел последовательности, начиная с 0-го.

Детали

• A , B и N могут быть взяты в любом порядке и формате, если они визуально разделены. Если вы используете другой порядок / формат, пожалуйста, укажите, что это такое.
• Вы можете предположить, что A , B и N всегда являются положительными целыми числами.
• Можно предположить, что N не более 100, и результирующая последовательность не будет содержать x >= 2^31.
• Если A больше, чем B , то B - это 0-е число в последовательности.
• Вывод должен быть разделен пробелами, запятыми и / или символами новой строки.
• Допускается завершающий пробел или символ новой строки, но не запятая.

Тест-кейсы

Пример 1:

8 13 10

Работая задом наперед, 8 13пока мы не найдем число больше предыдущего, мы получим 13 8 5 3 2 1 1 0 1. Таким образом, 0это 0-е число в этой последовательности. Работая над этим, мы распечатываем 0и следующие 9 участников:

0 1 1 2 3 5 8 13 21 34

Пример 2:

23 37 5

Снова работая в обратном направлении, чтобы найти 0-е число, мы находим 37 23 14 9 5 4 1 3. На этот раз 0-е число 1, поэтому мы распечатываем его вместе со следующими 4 членами:

1 4 5 9 14

Пример 3:

4 3 8

С этим нам не нужно работать в обратном направлении, чтобы найти 0-е число, потому что 3оно меньше, чем 4:

3 7 10 17 27 44 71 115

Пример 4:

29 47 11

Результат:

1 3 4 7 11 18 29 47 76 123 199

счет

Это код-гольф , поэтому выигрывает самый короткий действительный код в байтах. Tiebreaker переходит к ранее опубликованному представлению. Победитель будет выбран в следующий понедельник, 28 сентября. Удачи!

Изменить: Поздравляю вашего победителя, @Jakube, используя Pyth за удивительные 23 байта!

Pyth, 23 байта

AQWgHGA,-HGG)VvwHA,H+GH

Попробуйте онлайн: демонстрация или тестовый набор

Довольно необычный стиль программирования Pyth. Иногда функциональное программирование имеет свои недостатки.

Объяснение:

AQWgHGA,-HGG)VvwHA,H+GH  Q = input list of the two starting numbers
AQ                       G, H = Q (unpacking Q)
  WgHG                   while H >= G:
      A,-HGG                G, H = [H - G, G]
            )            end while
              vw         read a number from input
             V           for N in range(^):
                H           print H
                 A,H+GH     G, H = [H, G + H]

Сетчатка , 65 54 байта

+`(1*),\1(1*)
$2,$1
+`(1*)(,1*);1\B
$1$2$2$1;
^1*,|;1
<empty>

Вот, <empty> представляет пустую завершающую строку. Запустите код как отдельный файл с -sфлагом.

Формат ввода

A,B;N

где числа представлены в одинарных . Вывод списка через запятую, также в унарном виде. Например:

8 13 10

было бы

11111111,1111111111111;1111111111

и дать

,1,1,11,111,11111,11111111,1111111111111,111111111111111111111,1111111111111111111111111111111111

объяснение

+`(1*),\1(1*)
$2,$1

Сначала сокращаем Aи Bдо 0-го и -1-го элемента. +Говорит Retina , чтобы повторять это регулярное выражение замены до тех пор , либо регулярное выражение не прекращает согласование или замена не изменяет строку. Регулярное выражение Aпопадает в группу 1 с (1*), а затем проверяет, что Bоно, по крайней мере , такое же большое, как и Aпри захвате B-Aс \1(1*)группой 2. Это гарантирует, что этот цикл завершится один раз A>B.

Замена просто превращается A,Bв B-A,Aустановку соответствия $2,$1.

+`(1*)(,1*);1\B
$1$2$2$1;

Теперь у нас уже есть первый номер требуемого вывода в строке (а также номер перед ним, от которого мы должны избавиться позже). Эта замена теперь добавляет еще одно число в качестве суммы последних двух чисел при получении 1от N. Поскольку у нас уже есть один номер, мы хотим, чтобы это произошло только N-1. Мы делаем это, гарантируя, \Bчто по крайней мере ;11в конце строки есть. Если мы назовем последние два значения последовательности Cи D, то регулярное выражение захватит Cгруппу 1 и ,Dгруппу два. Мы пишем их обратно с $1$2. Затем мы также пишем, $2$1что переводится как ,D+C. Обратите внимание, что мы не записываем сингл, в котором 1мы соответствовалиNтем самым уменьшая его.

^1*,|;1
<empty>

Наконец, мы должны избавиться от -1st элемента последовательности, а оставшаяся ;1от N, которую мы просто путем сопоставления либо из тех , и заменить его с пустой строкой.

Python 2, 93 87 67 61 60 байт

i,j,l=input()
while j/i:i,j=j-i,i
exec"i,j=j,i+j;print i;"*l

Получает входные данные (в виде буквенного списка питонов [8,10,13])

Вырабатывает 0 семестр

Затем распечатывает последовательность дополнений, пока длина не будет достигнута

CJam, 26 23 байта

Спасибо Деннису за сохранение 3 байта.

q~{_@\-_g)}g\@{_@+_p}*t

Принимает ввод по порядку N B A(разделенный пробелами любого вида). Печатает результат как разделенный новой строкой список и завершается с ошибкой .

Проверьте это здесь.

объяснение

Это идет на шаг дальше при поиске 0-го элемента. То есть он завершается, когда одно из значений является отрицательным.

q~      e# Read and evaluate input, pushing N, B and A on the stack.
{       e# do while...
  _@\-  e#   B, A = A, B-A
  _W>   e#   Check if A is still non-negative.
}g
\@      e# Reorder N B A into A B N.
{       e# Run the following N times...
  _@+   e#   A, B = B, A+B
  _p    e#   Print B.
}*
t       e# The last A, B are still on the stack. We remove them by trying to
        e# execute a ternary operator: it pops the first two values but then
        e# terminates the program with an error, because there is no third value.

Лабиринт , 58 54 49 46 44 байта

Спасибо Sp3000 за предложение использовать побитовое отрицание, которое сэкономило два байта.

??#"{=
  ;  -
@"~~:}
~""
?
"}}:=
(   +
{{\!:

Формат ввода есть B A N. Выводом является разделенный новой строкой список.

объяснение

(Немного устарела. Основная идея все та же, но схема кода теперь другая.)

Это использует ту же идею, что и мой ответ CJam (поэтому кредиты по-прежнему отправляются Деннису): при возврате последовательности мы не останавливаемся до тех пор, пока не получим отрицательное значение (что оставляет нас с -1-м и -2-м элементом последовательности). Затем мы начинаем добавлять их перед печатью первого значения.

Это использует пару изящных лабиринт трюки в гольф. Давайте рассмотрим код в разделах:

?"
}

IP начинается с движения ?вправо (что читает A). На "(без операции) он заходит в тупик, поэтому он поворачивается, выполняя ?снова (чтение B). Наконец, }переходит Bна вспомогательный стек. Тупик сохраняет байт над наивным

?
?
}

Теперь цикл, который находит начало последовательности:

)(:{
"  -
" "`?...
=}""

)((Прирост декремент) является не-оп, но это необходимо для того, чтобы верхняя часть стека положительна на стыке (например , что IP поворачивает на восток). :дублирует A, {перемещает Bобратно в основной стек, -вычисляет A-B. Что мы действительно хотим B-A, так это `отрицает ценность.

Теперь это четырехсторонний перекресток. Для получения отрицательных результатов IP поворачивает влево ?, читая Nи переходя к следующей части программы. Если результат равен нулю, IP продолжает двигаться на юг, поворачивает в углу и остается в цикле. Если результат положительный, IP поворачивает направо (запад), поворачивает в углу и делает еще один поворот направо (снова на запад), поэтому он также остается в цикле. Я думаю, что это может стать распространенным шаблоном, позволяющим отличать отрицательные от неотрицательных (или положительных от не положительных) значений:

                v
                "
               """>negative
non-negative <"""

По крайней мере, мне пока не удалось найти более компактный / полезный макет для этого случая.

В любом случае, пока Aнеотрицательный, цикл продолжается, }перемещается Aво вспомогательный стек и =переставляет Aи B.

После того, Aкак отрицательный, ?читает Nи мы переходим во второй цикл:

 }:=+:
 }   !
?"({{\

Мы знаем, что Nэто положительно, поэтому мы можем рассчитывать на то, что IP повернет налево (на север). Тело цикла теперь просто:

}}:=+:!\{{(

На словах: перемещает Nи Aна вспомогательный стек. Дублируйте B, поменяйте местами копию Aи добавьте Aк другой копии B. Дублируйте это снова, чтобы напечатать текущее значение B. Распечатать новую строку. Переместитесь Bи Nвернитесь к основному стеку и уменьшите его N.

В то время Nкак положительный, IP будет поворачивать направо (север), продолжая цикл. Достигнув Nнуля, код завершается довольно причудливо:

IP продолжает двигаться прямо (запад). В ?пытается прочитать другое целое число, но мы уже достигли EOF, так что на самом деле толкает 0вместо этого. `пытается отрицать это, но это все равно ноль. Таким образом, IP все еще движется на запад, поворачивает в углу, а затем продолжает двигаться вниз на тот, @который завершает программу.

Интересно, смогу ли я поместить их @в еще более дешевую позицию (в настоящее время она стоит 3 пробельных символа), превратив три "из них `в составные no-ops (вроде )(), но я пока не смог сделать эту работу.

C 105 102 100 байт

main(a,b,n,t){for(scanf("%d%d%d",&a,&b,&n);t=b-a,t>=0;a=t)b=a;for(;n--;b=t)t=a+b,printf("%d ",a=b);}

Спасибо @ C0deH4cker за вывод 2 байта!

Попробуйте онлайн на Ideone .

Matlab / Octave, 115 125 байт

function x=f(x,n)
while x(2)>=x(1)
x=[abs(x(1)-x(2)) x];end
x=x([2 1]);for k=1:n-1
x=[x(1)+x(2) x];end
x=x(n:-1:1);

Функция должна называться как f([8 13],10).

Пример (Matlab):

>> f([8 13],10)
ans =
     0     1     1     2     3     5     8    13    21    34

Или попробуйте онлайн (октава) .

Haskell, 67 65 56 байт

a#b|a>b=b:scanl(+)(a+b)(a#b)|1>0=(b-a)#a
n%a=take n.(a#)

Спасибо @nimi за предложения

Это определяет троичную инфиксную функцию %, которая вызывается в формате (n%a)b, например:

> (10%8)13
[0,1,1,2,3,5,8,13,21,34]

объяснение

Бинарная функция инфиксным #, определенная на первой линии, принимает два целых числа aи bвозвращает бесконечной Фибоначчи-подобные последовательности , где aи bпроисходят в следующих друг за другом элементов.

a#b                                       -- Define a#b:
   |a>b=                                  -- if a>b, then a#b is
        b:                                -- the sequence that starts with b and
          scanl(+)     (a#b)              -- continues with the sums of prefixes of a#b
                  (a+b)                   -- plus the additional term a+b;
                            |1>0=(b-a)#a  -- otherwise, it's (b-a)#a.

Функция %просто берет первые nэлементы a#b.

> <>, 33 31 + 1 для -v = 32 байта

&:{:@(?v:}-$&
-1;!?:&<$+{oan::$&

Входные данные должны быть помещены в стек с использованием -v, поскольку синтаксический анализ десятичных чисел является нетривиальным в> <>.

Пояснение:

Я буду представлять стек после каждой (группы) операций. Начинается с [F (n), F (n + 1), N]

Первые строки идут вниз по серии к 0-му сроку:

& removes N from the stack to put it into a register. [F(n), F(n+1)]
:{:@ move the stack and duplicate items to get [F(n+1), F(n), F(n+1), F(n)]
(?v compares the two top items of the stack and branch to the second line if F(n+1) < F(n) [F(n+1), F(n)]
:} move the stack and duplicate its top to get [F(n), F(n+1), F(n)]
- substracts the two top items and put the result on top of the stack [F(n), F(n+1) - F(n)]
$ switchs the top two values of the stack. [F(n+1) - F(n), F(n)]
& retrieve the value from the register. iteration complete, since [F(n+1) - F(n), F(n), N] can also be read as [F(n-1), F(n), N]

Вторая строка идет вверх по серии, пока не напечатает N терминов:

< changes the code pointer direction to the left [F(0), F(-1)]
& retrieves the stored value back from the stack [F(0), F(-1), N]
:?!; copies N to compare it to 0, stops if it is [F(0), F(-1), N]
1- decreases it [F(0), F(-1), N-1]
& stores it back [F(0), F(-1)]
$:: makes the stack [F(-1), F(0), F(0), F(0)]
n{ prints the top of the stack then left shifts it [F(0), F(0), F(-1)]
ao displays a line feed (ascii character 0x0a) [F(0), F(0), F(-1)]
+ adds the two top values [F(0), F(-1) + F(0)]
$ switch the two top values. iteration complete since [F(-1) + F(0), F(0)] which can be read as [F(1), F(0)]

Джава, 113 78 76 байт

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

(a,b,n)->{for(;a<=b;b-=a)a=b-a;for(;n-->0;b+=a,a=b-a)System.out.println(b);}

Попробуй здесь .

Объяснение:

(a,b,n)->{
    for (;a<=b;b=b-a)a=b-a;  //Compute previous terms while a <= b
    for (;n-->0;b=a+b,a=b-a) //Compute and print next terms while n > 0
    System.out.println(b);   //Print term
}

Оригинальный подход, 113 93 байта

Выглядит больше в гольфе;)

String a(int a,int b,int n){return n<0?a+" "+a(b,a+b,n+1):n>0?a>b?a(b,a+b,-n):a(b-a,a,n):"";}

Попробуйте это здесь .

Объяснение:

String a(int a, int b, int n){
    return 
    n < 0 ?                           //If n < 0
        a + " " + a(b, a + b, n + 1)  //Return a + next terms and increment n.
    :                                 //Else
        n > 0 ?                       //If n > 0
            a > b ?                   //If a > b
                a(b, a + b, -n)       //Negate n and return terms.
            :                         //If a <= b
                a(b - a, a, n)        //Generate previous term.
        :                             //If n == 0
            ""                        //Return nothing.
    ;
}

Javascript (ES6), 83 73 63 байта

Это могло бы быть в гольф по максимуму. Посмотрим.

(a,b,n)=>{while(a<=b)b-=a=b-a;for(;n--;console.log(a=b-a))b+=a}

Ungolfed:

function f(a,b,n) {
  // repeat until we find the 0th item...
  while (a <= b) {  // if a = 5, b = 8:
    a = b - a;      // a = (8 - 5) = 3
    b = b - a;      // b = (8 - 3) = 5
  }
  // repeat n times...
  while (n-- > 0) { // if a = 5, b = 8:
    b += a;         // b = (8 + 5) = 13
    a = b - a;      // a = (13 - 5) = 8
    console.log(a); // print out each item
  }
}

Mathematica 112

Будет ли это гольф в конце концов

z[a_, b_, n_] := (
  f[0] := Min[a, b];
  f[1] := Max[a, b];
  f[x_] := f[x - 1] + f[x - 2];
  f /@ Range[n]
  )

CJam, 40 байт

l~:A;{_@_@)<}{_@\-\}w\{A(:A0>}{_p_@+}w\;

Шаги малыша. Это моя первая CJam-программа, и я горжусь тем, что она работает.

Он принимает данные в той же форме, что и в примерах.

Теперь я видел, что могу уменьшить его до 33 байт, используя { ... }*конструкцию.

l~:A;{_@_@)<}{_@-z\}w\A{_p_@+}*;;

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

Рубин, 141 байт

def u a,b,n,z=""
n<1 ? z.chop : u(b,a+b,n-1,z+"#{a} ")
end 
def d a,b,z=0
a.abs>b ? z : d(b-a,a,[a,b]) 
end 
def f a,b,n
x,y=d a,b 
u x,y,n
end 

выполнение

Функция f выдает желаемый результат, имена аргументов совпадают с именами переменных из вопроса

f(8,13,10) # returns => "0 1 1 2 3 5 8 13 21 34"

Ничего умного

• Функция u ( вверх ) вычисляет n элементов в последовательности Фибоначчи, начиная с a, b, используя рекурсию
• Функция d ( down ) находит 0-й и 1-й элемент по двум конечным элементам, используя рекурсию
• Функция f ( Фибоначчи ) объединяет два

Mathematica, 59 байт

If[#>#2,LinearRecurrence[{1,1},#2+{0,#},#3],#0[#2-#,#,#3]]&

Руби, 81 75 73

a,b,n=23,37,5;while(c=b-a)<a;b,a=a,c;end;p a;[*2..n].map{b=c+a;c,a=a,b;p b}

Сокращается на 6 байт при замене цикла for на range.map

a,b,n=23,37,5;while(c=b-a)<a;b,a=a,c;end;p a;[*2..n].map{p b=c+a;c,a=a,b}

Сохранены еще 2 байта путем перемещения выписки

Пайк, 24 байта (неконкурирующий)

DA/IDA-],X_r)QVDsRe
R]);

Попробуй это здесь!

Желе , 14 байт

Ḋ;_/Ɗ>/¿+⁹С/Ṗ

Попробуйте онлайн!

Common Lisp, 91 байт

(lambda(a b n)(do((x a(- y x))(y b x))((> x y)(dotimes(k n)(print y)(psetf y(+ y x)x y)))))

Попробуйте онлайн!