交番パワーフィボナッチシーケンス

Dennis 08/19/2017. 12 answers, 2.084 views
code-golf math sequence array-manipulation fibonacci

定義

交番パワーフィボナッチシーケンスは以下のように形成される。

  1. 空のシーケンスから始め、 n1設定します。

  2. n 番目の非負のフィボナッチ数 f nを繰り返して計算する。
    0が最初、 1が2番目と3番目、 2が4番目です。 他のすべてはシーケンスの前の2つの数値を合計することで得られます。したがって、 3 = 1 + 2が5番目、 5 = 2 + 3が6番目などです。

  3. nが奇数の場合、 f nの符号を変更します。

  4. f nの 2n-1コピーをシーケンスに追加します。

  5. nをインクリメントして、手順2に戻ります。

これらは、APFシーケンスの最初の100語です。

0  1  1 -1 -1 -1 -1  2  2  2  2  2  2  2  2 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3
-3 -3 -3 -3 -3 -3  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
 5  5  5  5  5  5  5  5  5  5  5  5  5 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
-8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 

仕事

正の整数nを入力とし、APFシーケンスのn 番目の項を出力または返す関数または完全なプログラムを記述します。

0ベースのインデックス作成を好む場合は、代わりに非負の整数nを取り、インデックスn APF番号を出力するか返すことができます。

これはです。 バイトで最短のコードが勝てるかもしれません!

テストケース(1ベース)

1 ->    0
    2 ->    1
    3 ->    1
    4 ->   -1
    7 ->   -1
    8 ->    2
  100 ->   -8
  250 ->   13
  500 ->  -21
 1000 ->   34
11111 ->  233
22222 -> -377
33333 ->  610 

テストケース(0ベース)

0 ->    0
    1 ->    1
    2 ->    1
    3 ->   -1
    6 ->   -1
    7 ->    2
   99 ->   -8
  249 ->   13
  499 ->  -21
  999 ->   34
11110 ->  233
22221 -> -377
33332 ->  610 
4 Comments
Okx 01/31/2017
n制約はありますか?
2 Dennis♦ 01/31/2017
あなたのアルゴリズムが任意に大きいn値に作用する限り、それはあなたのデータ型に合っていると推測できます。
1 Mindwin 02/01/2017
これはOEIS番号を持っていますか?
Dennis♦ 02/01/2017
@Mindwinそれはしません。

12 Answers


Jonathan Allan 01/31/2017.

ゼリー 、5 バイト

BLCÆḞ 

Try it online!

どうやって?

f(i) = f(i-2) + f(i-1)まだ成立するようにフィボナッチ系列を負のインデックスに戻す:

i   ...   -8  -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   4   5 ...
f(i)  ...  -21  13  -8   5  -3   2  -1   1   0   1   1   2   3   5   8 ... 

i=0から戻ってくる数字は2n-1回繰り返す必要があり、JellyのフィボナッチビルトインÆḞはこれらを計算します。

nビット長をとり、 1を引いて、必要な-i (正の数)を見つけることができます。

私たちはi (負の数)を必要とするので、代わりに1-bitLengthを実行することができ、Jellyは1-xC 、補数モナドのためのアトムを持ちます。

BLCÆḞ - Main link: n               e.g.  500
B     - convert n to a binary list      [1,1,1,1,1,0,1,0,0]
 L    - get the length                   9
  C   - complement                      -8
   ÆḞ - Fibonacci                       -21 
3 comments
miles 01/31/2017
私はそれより短い方法があることは知っていましたが、それだけではなく、 µを取り除く方法で7バイトになると思っていました
Jonathan Allan 01/31/2017
負のフィボナッチ値を想起させてゼリーのモナドに差し込もうとするまで、あなたの反復否定は賢明でした。マイナス1の力を見ていました。
4 ETHproductions 01/31/2017
正直なところ、私はJellyがバイナリの長さを得るために1バイトの組み込み関数を持っていないことに驚いています...

xnor 01/31/2017.

Python 2、30バイト

 f=lambda n:n<1or f(n/4)-f(n/2) 

オンラインで試してみてください!

1つのインデックス付き。

シーケンスはパズルのように感じました。デニスはそれを表現するための短い方法で生成しました。 2の累乗の繰返しは、ビットシフトによる再帰を示唆しています(2で床を分割する)。 交番符号フィボナッチ回帰f(n)=f(n-2)-f(n-1)は、減分の代わりにビットシフトに適合させることができる。 すべてがn=0至るので、ベースケースはうまく動作しn=0


martin 02/01/2017.

Mathematica、 43 36 24バイト

Fibonacci@-Floor@Log2@#& 

@GregMartinのおかげで7バイトが節約され、さらに@JungHwanMinのおかげでさらに12になりました。

2 comments
1 Greg Martin 01/31/2017
Floor@Log2@#でいくつかのバイトを保存し、 Fibonacci[t=...]書くことで(最後の指数のスペースを取り除くことによって)保存することができます。
1 JungHwan Min 02/01/2017
-12バイト: Fibonacci@-Floor@Log2@#& - Fibonacciは負の引数も取ることができます。

Luis Mendo 02/01/2017.

MATL19 17 16 11バイト

lOiB"yy-]x& 

入力は1から始まります。

オンラインで試してみてください! または、 すべてのテストケースを検証します

使い方

1ベースの入力nmn 2進展開の桁数とする。 出力シーケンスのn番目の項はフィボナッチシーケンスのm番目の項であり、記号が変更されている可能性があります。

1つのアイデアは、フィボナッチシーケンスの項を計算するためにm回反復することです。 これは、バイナリ数字の配列を使用するfor eachループfor each a for each簡単です。 フィボナッチシーケンスが0で開始され、通常通り1あれば、 m回反復するとスタック上にm+2項が生じるため、上位2つの数値を削除する必要があります。 代わりに、 1 、次に0で初期化します 。 そのようにして生成される次の項は1,1,2、...であり、削除はoneだけ必要です。

この符号は、 m回の符号を変更するために別のループを使用することで処理できます。 しかし、それはコストがかかります。 2つのループを統合する方がいいです。これはフィボナッチ反復を追加するのではなく、単純にsubtractingして行います。

l       % Push 1
O       % Push 0
iB      % Input converted to binary array
"       % For each
  yy    %   Duplicate top two elements
  -     %   Subtract. This computes the new Fibonacci term with the sign changes
]       % End
x       % Delete top number
&       % Specify that implicit display should take only one input
        % Implicitly display the top of the stack 

ETHproductions 04/13/2017.

JavaScript(ES6)、33バイト

f=(n,p=1,c=0)=>n?-f(n>>1,c,p+c):p 

1-indexed。

xnorの答えのポートは23です:

f=n=>n<1||f(n/4)-f(n/2) 

ovs 02/18/2017.

Python 2、83 82 79バイト

 def f(n,a=0,b=1):
 l=bin(n)[2:]
 for _ in l:a,b=b,a+b
 return a*-(len(l)%2or-1) 

オンラインで試してみてください!

1 comments
TuukkaX 01/31/2017
空白はor -1不要です。

miles 01/31/2017.

ゼリー 、9バイト

BLµ’ÆḞN⁸¡ 

1ベースの索引付けを使用します。

オンラインで試してみてください!

説明

このメソッドは、フィボナッチ関数が負でない引数のみをサポートしている場合に機能します。

BLµ’ÆḞN⁸¡  Input: integer n
B          Binary digits of n
 L         Length. len(bin(2)) = floor(log2(n)))
  µ        Start new monadic chain on x = len(bin(2))
   ’       Decrement
    ÆḞ     Get Fibonacci(x-1)
       ⁸¡  Repeat x times on that
      N      Negate.
           Return Fibonacci(x-1) if x is even else -Fibonacci(x-1) 

ETHproductions 01/31/2017.

Japt 、6バイト

Mg1-¢l 

それをオンラインでテストしてください!

使い方

他の答えで述べたように、交代記号フィボナッチ系列の-n 番目の項は、正規系列の-n 番目の項と同じです。 nは、入力のビット長をとり、1を減算することによって求めることができる。 これを否定すると、1からビット長が減算されます。

Mg1-¢l
    ¢l  // Calculate the length of the input in binary.
  1-    // Subtract this from 1.
Mg      // Get the Fibonacci number at this index. 

Emigna 04/13/2017.

05AB1E11 10バイト

1ベースのインデックスを使用する

05AB1Eのフィボナッチ関数は、 nより小さい正の05AB1Eナンバーを返します。つまり、必要以上に生成し、正しいものをインデックスで取得してから符号を計算する必要があります。 だから私はその方法に基づいて反復的に数を計算するよりも短くなるだろうと疑う。

Luis MendoのMATLの答えに記述されているように、 n=1場合を扱うために1, 0逆にしてスタックを初期化できることを実感します

XÎbgG‚D«`- 

オンラインで試してみてください!

Explanation

X             # push 1
 Î            # push 0 and input
  b           # convert input to binary
   g          # get length of binary number
    G         # for N in [1...len(bin(input))-1] do:
     ‚        # pair the top 2 elements of the stack in a list
      D       # duplicate the list 
       «      # concatenate the 2 lists together
        `     # split into separate elements on the stack
         -    # subtract the top 2 elements 

smls 01/31/2017.

Perl 6,53バイト

 {flat(((0,1,*+*...*)Z*|<-1 1>xx*)Zxx(1,2,4...*))[$_]} 

シーケンスの直接的な実装、それが記述された方法。
ゼロベース。


Dennis 04/13/2017.

ジュリア0.5,19バイト

 !n=n<1||!(n/=4)-!2n 

オンラインで試してみてください!

使い方

これは@ xnorのPythonの解答と同じ公式を使います 。 再帰関係
g(n) = g(n-2) + g(n-1)は、フィボナッチ系列の負の項を生成する。 同じ番号の2 k回の繰り返しでどこからでも、 24インデックスを分けることで、 2 k-1の前回の実行と2 k- 2の前の繰り返しのいずれかを選ぶことができます。

単純ではなくむしろ

 f(n)=n<1||f(n÷4)-f(n÷2) # 25 bytes 

オペレータを私たちの目的のために再定義することができます。 また、 fは浮動小数点数でも問題なく動作するため、

 !n=n<1||!(n/4)-!(n/2)   # 21 bytes 

最後に、 n4で除算して更新すると、wweはn/22nと書くことができ、一対の括弧を省略することができ、この答えでは19バイトの関数定義につながります。


miles 02/05/2017.

J 、18バイト

(%>:-*:)t.@<:@#@#: 

1ベースの索引付けを使用します。 入力の整数n > 0をとり、そのバイナリ表現の長さを見つけることによってfloor(log2(n))を計算し、その値を1だけデクリメントします。 次に、負のインデックスを持つフィボナッチ値のgfである生成関数x /(1 + x - x 2 )のfloor(log2(n))-1 th係数を見つける。

オンラインで試してみてください!

説明

(%>:-*:)t.@<:@#@#:  Input: integer n
                #:  Binary
              #@    Length
           <:@      Decrement
(      )            The generating function x/(1+x-x^2)
  >:                  Increment x
     *:               Square x
    -                 Subtract
 %                    Divide x by previous
        t.          Get series coefficient at the index given by previous value 

Related questions

Hot questions

Language

Popular Tags