7

整数 n を取得し、Stern の Diatomic Sequence で最初に出現するインデックスを見つける必要があります。

シーケンスは次のように定義されます。

a[0]     = 0
a[1]     = 1
a[2*i]   = a[i]
a[2*i+1] = a[i] + a[i+1]

MathWorldを参照してください。

n は最大 400000 になる可能性があるため、特に時間制限が 4000 ミリ秒であるため、力ずくで攻撃することはお勧めできません。

順序はかなり奇妙です: 8 の最初の発生は 21 ですが、6 の最初の発生は 33 です。

これを解決する方法はありますか？

たぶんこれが役立つかもしれません：OEIS

4

2 に答える 2

2

この関数を計算する別の方法を説明しているDijkstra からのこの手紙を読むことをお勧めします。

n, a, b := N, 1, 0;
do n ≠ 0 and even(n) → a, n:= a + b, n/2
             odd(n) → b, n:= b + a, (n-1)/2
od {b = fusc(N)}

これは a,b=1,0 で始まり、N の連続するビット (最下位から最上位へ) を効果的に使用して a と b を増やし、最終結果は b の値になります。

したがって、b の特定の値の最初の出現のインデックスは、この反復によって b の値が得られる最小の n を見つけることによって計算できます。

この最小の n を見つける 1 つの方法は、コストが n の値であるA* 検索を使用することです。アルゴリズムの効率は、ヒューリスティックの選択によって決まります。

ヒューリスティックについては、次のことに注意することをお勧めします。

  1. 最終値は常に gcd(a,b) の倍数になります (これは、ターゲットを生成できないノードを除外するために使用できます)
  2. b 常に増加する
  3. b が増加できる最大 (指数関数的) レートがあります (レートは a の現在の値に依存します)

編集

A* アプローチを説明する Python コードの例を次に示します。

from heapq import *

def gcd(a,b):
    while a:
        a,b=b%a,a
    return b

def heuristic(node,goal):
    """Estimate least n required to make b==goal"""
    n,a,b,k = node
    if b==goal: return n
    # Otherwise needs to have at least one more bit set
    # Improve this heuristic to make the algorithm faster
    return n+(1<<k)

def diatomic(goal):
    """Return index of first appearance of n in Stern's Diatomic sequence"""
    start=0,1,0,0
    f_score=[] # This is used as a heap
    heappush(f_score, (0,start) )
    while 1:
        s,node = heappop(f_score)
        n,a,b,k = node
        if b==goal:
            return n
        for node in [ (n,a+b,b,k+1),(n+(1<<k),a,b+a,k+1) ]:
            n2,a2,b2,k2 = node
            if b2<=goal and (goal%gcd(a2,b2))==0:
                heappush(f_score,(heuristic(node,goal),node))

print [diatomic(n) for n in xrange(1,10)]
于 2013-05-04T19:22:24.730 に答える