23

Сегодня ваша цель состоит в том, чтобы найти целые числа a и b, заданные неотрицательным целым числом n, такие, что:

(3 + sqrt (5)) ^ n = a + b * sqrt (5)

Вы должны написать программу или функцию, которая принимает параметр n и выводит a и b в выбранном вами формате.

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

Самый короткий код в байтах побеждает.

Пример ввода / вывода:

0 → 1, 0
1 → 3, 1
2 → 14, 6
3 → 72, 32
4 → 376, 168
5 → 1968, 880
6 → 10304, 4608
7 → 53952, 24128
8 → 282496, 126336
9 → 1479168, 661504

code-golf arithmetic orlp
источник

3

Дьялог АПЛ, 18 байт

((3∘×+5 1×⌽)⍣⎕)1 0

Это программа, которая принимает данные через ⎕.

 (         )         Monadic train:
  3∘×                3 times argument
     +               Plus
      5 1×⌽          (5 1) times the reverse
(           ⍣⎕)      Apply that function (input) times
               1 0   starting with (1 0)

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

Попробуй это здесь . Обратите внимание, что tryapl.org является ограниченным подмножеством Dyalog и не поддерживает ⎕.

lirtosiast
источник

16

Октава, 26 байт

[3 5;1 3]**input('')*[1;0]

Потому что ( a + b * sqrt (5)) * (3 + sqrt (5)) = ( 3a + 5b ) + ( a + 3b ) * sqrt (5),

умножение входного вектора

| 1 |    /* a = 1 */
| 0 |    /* b = 0 */

который обозначает 1 = (3 + sqrt (5)) ^ 0 по матрице

| 3 5 |
| 1 3 |

кажется естественным. Вместо того, чтобы зацикливать nвремя, мы скорее nувеличиваем матрицу до степени, а затем умножаем ее на входной вектор.

pawel.boczarski
источник

Вы продаете себя коротко, [3 5;1 3]**input('')*[1;0]это 26 байтов, а не 41.

orlp

3

@(n)[3 5;1 3]^n*[1;0](дескриптор функции) спасет вас пять символов, хорошая идея!

flawr

14

Python 2, 50

a=1;b=0
exec"a,b=3*a+5*b,3*b+a;"*input()
print a,b

Умножается на 3+sqrt(5)несколько раз его действием на (a,b)представление пары a+b*sqrt(5). Эквивалентно тому, чтобы начинать с вектора столбца [1,0]и умножать его влево nна матрицу [[3,5],[1,3]].

XNOR
источник

12

Юлия, 22 20 байт

n->[3 5;1 3]^n*[1;0]

Это создает лямбда-функцию, которая принимает одно целое число в качестве входных данных и возвращает 2-элементный вектор целых чисел, соответствующий решению [a, b]. Чтобы назвать его, дайте ему имя, например f=n->....

Начните с умножения

Начальное расширение

Затем мы можем перевести правую часть этого уравнения в матрицу из 2 столбцов, где первая соответствует коэффициенту a, а вторая - коэффициенту b :

матрица

Умножьте эту матрицу на себя n раз, затем умножьте вправо на вектор столбцов (1, 0), и POOF! Out выскакивает вектор решения.

Примеры:

julia> println(f(0))
[1,0]

julia> println(f(5))
[1968,880]

Алекс А.
источник

8

J, 20 байт

+/@:*(3 5,.1 3&)&1 0

Умножьте вектор [1 0]с [[3 5] [1 3]] nвременами матрицы .

2 байта сохранены благодаря @algorithmshark.

Использование и тестирование:

   (+/@:*(3 5,.1 3&)&1 0) 5
1968 880

   (+/@:*(3 5,.1 3&)&1 0) every i.6
   1   0
   3   1
  14   6
  72  32
 376 168
1968 880

randomra
источник

Вы можете получить до 20 за счетом использования молчаливого наречия разбора: +/ .*(3 5,:1 3&)&1 0.

алгоритмическая

@algorithmshark Спасибо, хотя почему (+/@:*&(3 5,.1 3)&1 0)работает а (+/@:*&1 0&(3 5,.1 3))не? Не должен ли второй связать правильно, а первый поменялся местами?

Рандомра

Понятно, они связываются, как я и ожидал, но внешнее &питание включается / зацикливается, поэтому вы изменяете вход левой стороны во время включения питания (в отличие от обычной модификации правой стороны).

Рандомра

7

Pyth, 20 байт

u,+*3sGyeG+sGyeGQ,1Z

uкоторый в общем случае сокращается, используется здесь как цикл многократного применения. Функция обновления G-> ,+*3sGyeG+sGyeG, где G2 кортежа. Эта функция переводится как 3*sum(G) + 2*G[1], sum(G) + 2*G[1]. sесть sum, yесть *2.

isaacg
источник

Я выбрал ответ @ randomra вместо вашего, потому что его / ее был опубликован 16 минутами ранее, извините.

orlp

5

APL (22)

{⍵+.×⍨2 2⍴3 5 1}⍣⎕⍨2↑1

Объяснение:

{... }⍣⎕⍨2↑1: прочитать число и запустить следующую функцию много раз, используя [1,0]в качестве начального ввода.
- 2 2⍴3 5 1: матрица [[3,5],[1,3]]
- ⍵+.×⍨: умножьте первое число в ⍵ на 3, второе на 5 и сложите их, это новое первое число; затем умножьте первое число в ⍵ на 1, второе на 3 и сложите те, которые являются новым вторым числом.

Мэринус
источник

1

Awww Yiss, APL.

Нит

5

Желе , 13 байт

5W×U++Ḥ
2BÇ³¡

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

Как это работает

5W×U++Ḥ    Helper link. Argument: [a, b]

5W         Yield [5].
  ×U       Multiply it by the reverse of [a, b]. This yields [5b, a].
    +      Hook; add the argument to the result. This yields [a + 5b, a + b].
     +Ḥ    Fork; add the doubled argument ([2a, 2b]) to the result.
           This yields [3a + 5b, a + 3b].

2BÇ³¡      Main link. Argument: n

2B         Convert 2 to binary, yielding [1, 0].
    ¡      Repeat:
  Ç            Apply the helper link...
   ³           n times.

Деннис
источник

Нет, я почти уверен, что до создания интернета у Джелли было много времени: P

Конор О'Брайен,

1

@ Doᴡɴɢᴏᴀᴛ Для неконкурентных ответов я предпочитаю вести подсчет байтов во второй строке. Это удерживает ответ от поднятия на вершину в списках лидеров и пользовательских скриптов, что кажется несправедливым.

Деннис

3

Математика, 31

Nest[{{3,5},{1,3}}.#&,{1,0},#]&

alephalpha
источник

3

CJam, 21 байт

0X{_2$3*+@5*@3*+}li*p

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

Как это работает

0X       " Stack: [ 0 1 ]                                ";
li{      " Do int(input()) times:                        ";
  _2$    " Stack: [ a b ] -> [ a b b a ]                 ";
  3*+    " Stack: [ a b b a ] -> [ a b (b+3a) ]          ";
  @5*@3* " Stack: [ a b (b+3a) ] -> [ (b+3a) 5a 3b ]     ";
  +      " Stack: [ (b+3a) 5a 3b ] -> [ (b+3a) (5a+3b) ] ";
}*       "                                               ";
p        " Print topmost stack item plus linefeed.       ";
         " Print remaining stack item (implicit).        ";

Деннис
источник

3

Javascript, 63 61 байт

Я использую рекурсивную оценку бинома: (x + y) ^ n = (x + y) (x + y) ^ {n-1}

Новый (спасибо @ edc65)

F=n=>{for(i=y=0,x=1;i++<n;)[x,y]=[3*x+5*y,x+3*y];return[x,y]}

старый

F=n=>{for(i=y=0,x=1;i<n;i++)[x,y]=[3*x+5*y,x+3*y];return [x,y]}

flawr
источник

1

Возможно, стоит рассмотреть возможность редактирования вашей формулы. У нас больше нет MathJax.

Алекс А.

Я думал, что это было только введено несколько дней назад?

flawr

Да, но он испортил фрагменты стека, поэтому его пришлось отключить.

Алекс А.

Я считаю 63 как есть, и могу быть сокращен до 61F=n=>{for(i=y=0,x=1;i++<n;)[x,y]=[3*x+5*y,x+3*y];return[x,y]}

edc65

n=>[...Array(n)].map(_=>[x,y]=[3*x+5*y,x+3*y],y=0,x=1)[n-1]той же длины

l4m2

2

C, 114 байтов

g(n){int i,a[2]={1,0},b[2];for(i=0;i<n;i++)*b=*a*3+5*a[1],b[1]=*a+3*b[1],*a=*b,a[1]=b[1];printf("%d,%d",*a,a[1]);}

Это реализует умножение матриц скучным способом. Для большего удовольствия (цитата: «потрясающе ужасно») 238-байтовое решение, не смотрите дальше!

f(n){int p[2][n+3],i,j,k=0,a[2]={0};for(j=0;j<n+3;j++)p[0][j]=0;*p[1]=0;(*p)[1]=1;for(j=0;j<n;j++,k=!k)for(i=1;i<n+3;i++)p[!k][i]=p[k][i-1]+p[k][i];for(i=1;i<n+2;i++)a[!(i%2)]+=p[k][i]*pow(3,n+1-i)*pow(5,(i-1)/2);printf("%d,%d",*a,a[1]);}

разгадали:

g(n){
    int i,a[2]={1,0},b[2];
    for(i=0;i<n;i++)
        *b=3**a+5*a[1],b[1]=*a+3*b[1],*a=*b,a[1]=b[1];
    printf("%d,%d",*a,a[1]);
}

Это, вероятно, может быть немного сокращено. Попробуйте тестовую программу онлайн !

BrainSteel
источник

1

Это использует довольно сложный алгоритм: P

orlp

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

BrainSteel

1

Upvote, потому что это ужасно ужасно.

kirbyfan64sos

2

к2 - 22 символа

Функция принимает один аргумент.

_mul[(3 5;1 3)]/[;1 0]

_mulявляется умножением матрицы, поэтому мы каррируем ее с матрицей, (3 5;1 3)а затем нажимаем на нее наречие функциональной мощности: f/[n;x]применяется fк x, nраз. Снова мы его карри, на этот раз с начальным вектором 1 0.

  _mul[2 2#3 5 1]/[;1 0] 5
1968 880
  f:_mul[2 2#3 5 1]/[;1 0]
  f'!8  /each result from 0 to 7 inclusive
(1 0
 3 1
 14 6
 72 32
 376 168
 1968 880
 10304 4608
 53952 24128)

Это не будет работать в Kona, потому что по какой-то причине f/[n;x]не реализовано правильно. n f/xРаботает только синтаксис, поэтому самое короткое исправление - {x _mul[(3 5;1 3)]/1 0}23 символа.

algorithmshark
источник

Вау. Такое использование карри настолько умно, что я чувствую, что мой ответ на K глуп. Во всяком случае, я поднял проблему, которую вы нашли в Kona на их баг-трекере .

kirbyfan64sos

К вашему сведению, это было недавно исправлено в Коне .

kirbyfan64sos

2

ised, 25 байтов (20 символов)

({:{2,4}·x±Σx:}$1)∘1

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

Ожидается, что вход будет в слоте $ 1, так что это работает:

ised '@1{9};' '({:{2,4}·x±Σx:}$1)∘1'

При n = 0 ноль пропускается (выводится 1 вместо 1 0). Если это проблема, замените финал 1на ~[2].

Орион
источник

2

Серьезно, 32 байта, не конкурирующие

,╗43/12`╜";)@4*≈(6*-"£n.X4ì±0`n

Шестнадцатеричный дамп:

2cbb34332f313260bd223b2940342af728362a2d229c6e2e58348df130606e7f

Попробуй Onlline

Очевидно, не претендент на самый короткий, но, по крайней мере, метод является оригинальным. (Отмечая, что такая проблема обязательно указывает последовательность Лукаса, как упомянуто в описании, эта программа генерирует последовательные члены последовательностей, используя рекуррентное соотношение

a_n = 6 * a_ {n-1} - 4 * a_ {n-2}.)

quintopia
источник

1

Haskell, 41 байт

(iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!)

Пример использования: (iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!) 8-> (282496,126336).

Ними
источник

1

C / C ++ 89 байт

void g(int n,long&a,long&b){if(n){long j,k;g(n-1,j,k);a=3*j+5*k;b=j+3*k;}else{a=1;b=0;}}

отформатирован:

    void g(int n, long&a, long&b) {
if (n) {
    long j, k;
    g(n - 1, j, k);
    a = 3 * j + 5 * k;
    b = j + 3 * k;
} else {
    a = 1;
    b = 0;
}}

Та же концепция:

void get(int n, long &a, long& b) {
    if (n == 0) {
        a = 1;
        b = 0;
        return;
    }
    long j, k;
    get(n - 1, j, k);
    a = 3 * j + 5 * k;
    b = j + 3 * k;
}

Испытательный стенд:

#include <iostream>
using namespace std;    
int main() {
    long a, b;
    for (int i = 0; i < 55; i++) {
        g(i, a, b);
        cout << i << "-> " << a << ' ' << b << endl;
    }
    return 0;
}

Выход:

0-> 1 0
1-> 3 1
2-> 14 6
3-> 72 32
4-> 376 168
5-> 1968 880
6-> 10304 4608
7-> 53952 24128
8-> 282496 126336
9-> 1479168 661504
10-> 7745024 3463680
11-> 40553472 18136064
12-> 212340736 94961664
13-> 1111830528 497225728
14-> 5821620224 2603507712
15-> 30482399232 13632143360
16-> 159607914496 71378829312
17-> 835717890048 373744402432
18-> 4375875682304 1956951097344
19-> 22912382533632 10246728974336
20-> 119970792472576 53652569456640
21-> 628175224700928 280928500842496
22-> 3289168178315264 1470960727228416
23-> 17222308171087872 7702050360000512
24-> 90177176313266176 40328459251089408
25-> 472173825195245568 211162554066534400
26-> 2472334245918408704 1105661487394848768

philn
источник

Добро пожаловать на сайт и приятного первого ответа!

DJMcMayhem

0

К, 37 байт

f:{:[x;*(1;0)*_mul/x#,2 2#3 1 5;1 0]}

или

f:{:[x;*(1;0)*_mul/x#,(3 1;5 3);1 0]}

Они оба одно и то же.

kirbyfan64sos
источник

0

Python 3, 49 байт

w=5**0.5;a=(3+w)**int(input())//2+1;print(a,a//w)

хотя на моей машине это дает только правильный ответ для входных данных в диапазоне 0 <= n <= 18.

Это реализует формулу закрытой формы

w = 5 ** 0.5
u = 3 + w
v = 3 - w
a = (u ** n + v ** n) / 2
b = (u ** n - v ** n) / (2 * w)

и использует тот факт, что v ** nдеталь небольшая и может быть вычислена путем округления, а не прямого вычисления.

источник

1

Это недопустимое решение (вы должны поддерживать любое n ), но, поскольку вы далеко не самое короткое, я не вижу причин для понижения. Это классное решение.

orlp

0

Схема, 97 байт

(define(r n)(let s([n n][a 1][b 0])(if(= 0 n)(cons a b)(s(- n 1)(+(* a 3)(* b 5))(+ a(* b 3))))))

Penguino
источник

0

C 71 байт (60 с предварительно инициализированными переменными)

Возможности для игры в гольф пока нет, но только для того, чтобы доказать, что C не должен быть «ужасно ужасным».

f(int n,int*a){for(*a=1,a[1]=0;n--;a[1]=*a+3*a[1],*a=(5*a[1]+4**a)/3);}

Если значения в a инициализированы в {1,0}, мы делаем лучше.

f(int n,int*a){for(;n--;a[1]=*a+3*a[1],*a=(5*a[1]+4**a)/3);}

Это итеративно использует отображения a-> 3a + 5b, b-> a + 3b, но избегает временной переменной, вычисляя вместо этого новое значение b.

Alchymist
источник

Ваше решение переполняет целые числа для больших входов :)

orlp

@orlp - Это C для тебя. Конечно, это решение дает сбой раньше, чем другие из-за промежуточного вычисления в скобках, но в любом случае оно будет обрабатывать только пару дополнительных шагов, если я не изменю тип данных. Стоит ли явно менять вопрос, чтобы указать диапазон, который вы ожидаете поддержать? Возможно, уже слишком поздно.

Алхимик

Там нет диапазона для поддержки, правильное решение должно работать для любого входа. В C это означает, что вам нужно реализовать произвольные целые числа ширины, извините = /

orlp

Предложить a[*a=1]=0вместо*a=1,a[1]=0

потолок кошка

0

(неконкурентный) желе, 10 байт

31,53Dæ*³Ḣ

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

Использует матрицу. Вычисляет ([[3,1], [5,3]] ** input ()) [0].

Дрянная Монахиня
источник

Расчет (3 + sqrt (5)) ^ n точно

Ответы:

Дьялог АПЛ, 18 байт

Октава, 26 байт

Python 2, 50

Юлия, 22 20 байт

J, 20 байт

Pyth, 20 байт

APL (22)

Желе , 13 байт

Как это работает

Математика, 31

CJam, 21 байт

Как это работает

Javascript, 63 61 байт

C, 114 байтов

к2 - 22 символа

ised, 25 байтов (20 символов)

Серьезно, 32 байта, не конкурирующие

Haskell, 41 байт

К, 37 байт

Python 3, 49 байт

Схема, 97 байт

(неконкурентный) желе, 10 байт