Выведите первые n чисел последовательности Фибоначчи в одно выражение

Как насчет:

(lambda f: (4 << f * (3 + f)) // ((4 << 2 * f) - (2 << f) - 1) & ((2 << f) - 1))(n)

Он не запускает последовательность обычным образом:

0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, ...

Но как только вы пройдете 1, все в порядке. Вы найдете подробное объяснение в записи блога Целочисленная формула для чисел Фибоначчи вместе с множеством связанная информация.

В моей системе решение @ lehiester, основанное на золотом сечении, сходит с рельсов на F71, производя 308061521170130 вместо 308061521170129, и продолжает отклоняться от этого.

Вам нужно будет присвоить лямбду реальной переменной, а затем вызвать лямбда внутри лямбды:

>>> g = lambda f: f if f < 2 else g(f-1)+g(f-2)
>>> [g(n) for n in range(10)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

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

fib = (lambda n: (lambda fib: fib(fib, [], n, None))(lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))))

Просто чтобы немного это объяснить. Первая часть (lambda fib: fib(fib, [], n, None)) принимает лямбда-функцию в качестве параметра и затем вызывает ее с ожидаемыми параметрами. Этот трюк позволяет нам присвоить имя лямбда-функции и передать это имя самой себе ... в этом вся магия.

Вместо второй части, основной функции, lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))) используется другой трюк для реализации динамического решения. Первый параметр fib является ссылкой на себя, второй параметр arr - это массив, содержащий наше решение, и он заполняется слева направо, вызывая рекурсивно fib ровно n раз. Рекурсия заканчивается, когда третий параметр i становится равным 0. Четвертый параметр - уродливая уловка: он не используется функцией, но используется для вызова метода добавления arr.

Это абсолютно менее элегантное решение, но оно также и самое быстрое. Я сообщаю время N=500 ниже.

Наивное решение невозможно, но здесь вы можете найти код для вычисления одного элемента за раз в серии (вероятно, это то, что вы хотели смешать с лямбда-функцией и рекурсией):

(lambda n: ((lambda fib: fib(fib,n+1))(lambda fib, i: (1 if i <= 2 else fib(fib,i-2) + fib(fib,i-1)))))(N)

Решение, предложенное @cdlane:

%timeit [0, 1] + [(4<<n*(3+n)) // ((4<<2*n)-(2<<n)-1) & ((2<<n)-1) for n in range(N)][1:]
10 loops, best of 3: 88.3 ms per loop

Решение, предложенное @lehiester:

%timeit [int(round((lambda n: ((1+5**0.5)**n-(1-5**0.5)**n)/(2**n*5**0.5))(x))) for x in range(N)]
1000 loops, best of 3: 1.49 ms per loop

Мое уродливое решение:

%timeit (lambda n: (lambda fib: fib(fib, [], n, None))(lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))))(N)
1000 loops, best of 3: 434 us per loop

Еще одно уродливое и более быстрое решение, которое не использует рекурсию:

%timeit (lambda n: (lambda arr, fib_supp: [arr] +  [fib_supp(arr) for i in xrange(n)])([], (lambda arr: arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2])))[0])(N)
1000 loops, best of 3: 346 us per loop

ОБНОВИТЬ

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

%timeit (lambda n: (lambda arr, fib_supp: any(fib_supp(i, arr) for i in xrange(2,n)) or arr)([1] * n, (lambda i, arr: arr.__setitem__(i,(arr[i-1]+arr[i-2])))))(N)
1000 loops, best of 3: 385 us per loop

лямбда-исчисление через Python

Поскольку это помечено тегом лямбда-исчисление, вместо того, чтобы писать ответ, основанный на умных трюках или языковых функциях, характерных для python, я буду использовать только простые лямбда-выражения.

U = lambda f: f (f)

Y = U (lambda h: lambda f: f (lambda x: h (h) (f) (x)))

loop = Y (lambda recur: lambda acc: lambda a: lambda b: lambda n:
  acc if n == 0 else
    recur (acc + [a]) (a + b) (a) (n - 1))

fibonacci = loop ([]) (0) (1)

print (fibonacci (10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Конечно, мы использовали четыре именованных лямбда U, Y, loop и fibonacci - поскольку каждая лямбда - это чистая функция, мы можем заменить любую ссылку на ее имя на ее значение.

# in Y, replace U with its definition
Y = (lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x)))

# in loop, replace Y with its definition
loop = (lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x))) (lambda recur: lambda acc: lambda a: lambda b: lambda n:
  acc if n == 0 else
    recur (acc + [a]) (a + b) (a) (n - 1))

# in fibonacci, replace loop with its definition
fibonacci = (lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x))) (lambda recur: lambda acc: lambda a: lambda b: lambda n:
  acc if n == 0 else
    recur (acc + [a]) (a + b) (a) (n - 1)) ([]) (0) (1)

fibonacci теперь является единственным чистым выражением - мы могли бы вызвать лямбду прямо в операторе print ...

# in print, replace fibonacci with its definition
print ((lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x))) (lambda recur: lambda acc: lambda a: lambda b: lambda n:
  acc if n == 0 else
    recur (acc + [a]) (a + b) (a) (n - 1)) ([]) (0) (1) (10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

еще раз, используя другую программу

Я написал очень аналогичный ответ (также на Python), но в контексте другой программы - может быть полезно помочь увидеть универсальность методов

еще раз на другом языке

Мы сделаем все это снова, только на этот раз на JavaScript. JS лучше подходит для демонстрации этого упражнения, потому что мы можем показать код, работающий здесь, в браузере, а лямбда-синтаксис гораздо более либерален (с точки зрения форматирования кода) - в остальном вы обратите внимание, программы почти идентичны

const U = f =>
  f (f)

const Y =
  U (h => f => f (x => h (h) (f) (x)))

const loop = Y (recur => acc => a => b => n =>
  n === 0
    ? acc
    : recur (acc.concat ([a])) (a + b) (a) (n - 1))

const fibonacci =
  loop ([]) (0) (1)

console.log (fibonacci (10))
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

// in Y, replace U with its definition
Y = (f => f (f)) (h => f => f (x => h (h) (f) (x)))

// in loop, replace Y with its definition
loop = (f => f (f)) (h => f => f (x => h (h) (f) (x))) (recur => acc => a => b => n =>
  n === 0
    ? acc
    : recur (acc.concat ([a])) (a + b) (a) (n - 1))

// in fibonacci, replace loop with its definition
fibonacci = (f => f (f)) (h => f => f (x => h (h) (f) (x))) (recur => acc => a => b => n =>
  n === 0
    ? acc
    : recur (acc.concat ([a])) (a + b) (a) (n - 1)) ([]) (0) (1)

fibonacci теперь является единственным чистым выражением - мы могли бы вызвать лямбду прямо в операторе console.log ...

ох, и это тоже действительно быстро

console.time ('fibonacci (500)')
console.log ((f => f (f)) (h => f => f (x => h (h) (f) (x))) (recur => acc => a => b => n =>
  n === 0
    ? acc
    : recur (acc.concat ([a])) (a + b) (a) (n - 1)) ([]) (0) (1) (500))
console.timeEnd ('fibonacci (500)')
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 490 more items ]
// fibonacci (500): 3 ms

практика ведет к совершенству

Лямбда-исчисление было одной из моих любимых областей изучения. Используя только Y-комбинатор, я провел бесчисленные часы , исследуя его красоту и изысканность. Надеюсь, вы найдете эти исследования полезными. Если у вас есть другие вопросы по теме, не стесняйтесь спрашивать ^ _ ^

Вы должны каким-то образом присвоить ему имя, чтобы использовать рекурсивное определение - в противном случае рекурсивная лямбда-функция невозможна в Python, поскольку у нее нет специального рефлексивного ключевого слова, которое ссылается на нее.

Как упоминал @TerryA, вы можете использовать трюк в этом сообщении, чтобы сгенерировать последовательность x чисел Фибоначчи в одном выражении. с рекурсивным определением.

Или вы можете использовать закрытую форму, что будет намного быстрее:

[int(round((lambda n: ((1+5**0.5)**n-(1-5**0.5)**n)/(2**n*5**0.5))(x)))
 for x in range(10)]

Однако это предполагает, что x не очень велик, потому что арифметика с плавающей запятой будет переполняться вокруг x=600 и, вероятно, будет иметь большие ошибки округления до этой точки - как указывает @cdlane, это начинает расходиться с фактической последовательностью в x=71, то есть x in range(72).

РЕДАКТИРОВАТЬ: @cdlane поделился закрытой формой только с целочисленной арифметикой, которая теоретически должна работать для любого x. Я бы, вероятно, использовал это вместо приведенного выше выражения.

[0, 1] + [(4<<n*(3+n)) // ((4<<2*n)-(2<<n)-1) & ((2<<n)-1)
          for n in range(10)][1:]