8

フィボナッチ文字列は次のように定義されます。

  • 最初のフィボナッチ文字列は「a」
  • 2 番目のフィボナッチ文字列は「bc」です
  • (n + 2) 番目のフィボナッチ文字列は、前の 2 つのフィボナッチ文字列を連結したものです。

たとえば、最初のいくつかのフィボナッチ文字列は次のとおりです。

a
bc
abc
bcabc
abcbcabc

目標は、行とオフセットを指定して、そのオフセットにある文字を判別することです。より正式には：

入力:スペースで区切られた 2 つの整数 - K と P(0 < K ≤ 10 9 )、( < P ≤ 10 9 )、ここで、K はフィボナッチ文字列の行番号、P は行の位置番号です。

出力:関連するテストに必要な文字: "a"、"b"、または "c"。P が k 行目よりも大きい場合 (K ≤ 10 9 )、«解なし» を導出する必要があります。

例：

入力: 18 58

出力:

問題を解決するためにこのコードを書きました：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int k, p;
    string s1 = "a";
    string s2 = "bc";
    vector < int >fib_numb;
    fib_numb.push_back(1);
    fib_numb.push_back(2);
    cin >> k >> p;
    k -= 1;
    p -= 1;
    while (fib_numb.back() < p) {
        fib_numb.push_back(fib_numb[fib_numb.size() - 1] + fib_numb[fib_numb.size() - 2]);
    }
    if (fib_numb[k] <= p) {
        cout << "No solution";
        return 0;
    }
    if ((k - fib_numb.size()) % 2 == 1)
        k = fib_numb.size() + 1;
    else
        k = fib_numb.size();
    while (k > 1) {
        if (fib_numb[k - 2] > p)
            k -= 2;
        else {
            p -= fib_numb[k - 2];
            k -= 1;
        }
    }
    if (k == 1)
        cout << s2[p];
    else
        cout << s1[0];
    return 0;
}

それが正しいか？どうしたらよかったの？

4

6 に答える 6

14

文字列を明示的に計算しなくてもこの問題を解決できます。これがおそらく問題を解決するための最良の方法です。結局のところ、50番目のフィボナッチ文字列を計算するように求められた場合、メモリが不足することはほぼ確実です。F（50）は12,586,269,025なので、それを保持するためだけに12GB以上のメモリが必要になります。

解決策の背後にある直感は、フィボナッチ文字列の各行が前の行の文字で構成されているため、（行、オフセット）ペアを別の（行'、オフセット'）ペアに変換できることです。常に最初の文字列よりも小さいフィボナッチ文字列の場合。これを十分な回数繰り返すと、最終的には行0または行1のいずれかのフィボナッチ文字列に戻ります。この場合、答えはすぐに読み取られます。

このアルゴリズムを機能させるには、いくつかの事実を確立する必要があります。まず、ゼロインデックスになるフィボナッチ数列を定義しましょう。つまり、シーケンスは

F(0)   = 0
F(1)   = 1
F(n+2) = F(n) + F(n + 1)

これを考えると、フィボナッチ文字列のn番目の行（1つのインデックス）には合計F（n + 1）文字が含まれていることがわかります。これは、誘導によってすばやく確認できます。

  • 行1の長さは1=F（2）= F（1 + 1）
  • 行2の長さは2=F（3）= F（2 + 1）です。
  • 一部の行n+2の場合、その行の長さはSize（n）+ Size（n + 1）= F（n + 1）+ F（n + 2）= F（n + 3）= F（ （n + 2）+ 1）

この知識を使用して、フィボナッチ文字列の7行目の7番目の文字を検索するとします。行7は行5と6の連結で構成されていることがわかっているため、文字列は次のようになります。

  R(7) = R(5) R(6)

行5にはF（5 + 1）= F（6）= 8文字が含まれています。これは、行7の最初の8文字がR（5）からのものであることを意味します。この行から7番目の文字が必要であり、7≤8であるため、この値を取得するには、行5の7番目の文字を調べる必要があることがわかります。行5は、行3と4の連結のように見えます。

  R(5) = R(3) R(4)

この行の7番目の文字を見つけたいと思います。ここで、R（3）にはF（4）= 3文字が含まれています。つまり、R（5）の7番目の文字を探している場合、R（5）ではなくR（4）の部分になります。 3）一部。この行の7番目の文字を探しているので、R（4）の7-F（4）= 7-3 = 4番目の文字を探していることを意味します。ここで、ここを探します。ここでも、R（4）は次のように定義されます。

 R(4) = R(2) R(3)

R（2）にはF（3）= 2文字が含まれているため、行の4番目の文字を見つけるためにR（2）を調べたくありません。これはR（3）に含まれます。行の4番目の文字は、R（3）の2番目の文字でなければなりません。そこを見てみましょう。R（3）は次のように定義されます

 R(3) = R(1) R(2)

R（1）には1文字が含まれているため、この行の2番目の文字はR（1）の最初の文字である必要があるため、ここで確認します。しかし、私たちはそれを知っています

 R(2) = bc

したがって、この文字列の最初の文字はb、です。これが私たちの答えです。これが正しいかどうか見てみましょう。フィボナッチ文字列の最初の7行は

1 a
2 bc
3 abc
4 bcabc
5 abcbcabc
6 bcabcabcbcabc
7 abcbcabcbcabcabcbcabc

案の定、7番目の文字列の7番目の文字を見ると、それが確かにであることがわかりますb。これはうまくいくようです！

より正式には、関心のある漸化式は次のようになります。

char NthChar(int row, int index) {
    if (row == 1) return 'a';
    if (row == 2 && index == 1) return 'b';
    if (row == 2 && index == 2) return 'c';
    if (index < Fibonacci(row - 1)) return NthChar(row - 2, index);
    return NthChar(row - 1, index - Fibonacci(row - 1));
}

もちろん、ここに書かれているように、実装には問題があります。行インデックスの範囲は最大109Fibonacci(row)であるため、すべての場合に計算できるとは限りません。10億番目のフィボナッチ数は大きすぎて表現できません！

幸い、これを回避することができます。フィボナッチ数の表を見ると、F（45）= 1,134,903,170であり、これは10 9よりも大きいことがわかります（フィボナッチ数がこれよりも小さいことはありません）。さらに、関心のあるインデックスも10億を超えてはならないことがわかっているため、行46以上の場合は、常にフィボナッチ文字列の前半を見るブランチを使用します。これは、コードを次のように書き直すことができることを意味します

char NthChar(int row, int index) {
    if (row == 1) return 'a';
    if (row == 2 && index == 1) return 'b';
    if (row == 2 && index == 2) return 'c';

    /* Avoid integer overflow! */
    if (row >= 46) return NthChar(row - 2, index);

    if (index < Fibonacci(row - 1)) return NthChar(row - 2, index);
    return NthChar(row - 1, index - Fibonacci(row - 1));
}

この時点で、私たちは解決策に非常に近づいています。対処すべき問題がまだいくつかあります。まず、上記のコードは、コンパイラが末尾再帰を使用してすべてのスタックフレームを削除するのに十分でない限り、ほぼ確実にスタックを吹き飛ばします。一部のコンパイラ（gccなど）はこれを検出できますが、これに依存するのはおそらく良い考えではないため、この再帰関数を繰り返し書き直す必要があります。考えられる実装の1つは次のとおりです。

char NthChar(int row, int index) {
    while (true) {
       if (row == 1) return 'a';
       if (row == 2 && index == 1) return 'b';
       if (row == 2 && index == 2) return 'c';

       /* Avoid integer overflow! */
       if (row >= 46 || index < Fibonacci(row - 1)) {
           row -= 2;
       } else {
           index -= Fibonacci(row - 1);
           row --;
       }
    }
}

しかしもちろん、これよりもはるかにうまくいくことができます。特に、驚くほど大きな行番号（たとえば、10億）が与えられた場合、46未満になるまで、行から2を引いて何度もループし続けるのは、本当にばかげています。すべての減算を行った後、最終的にどのような値になるかを決定するだけです。しかし、これは非常に簡単に行うことができます。少なくとも46の偶数行がある場合は、44になるまで2を減算することになります。少なくとも46の奇数行がある場合は、45になるまで2を減算することになります。上記のコードを書き直して、このケースを明示的に処理できます。

char NthChar(int row, int index) {
    /* Preprocess the row to make it a small value. */
    if (row >= 46) {
        if (row % 2 == 0)
            row = 45;
        else
            row = 44;
    }

    while (true) {
       if (row == 1) return 'a';
       if (row == 2 && index == 1) return 'b';
       if (row == 2 && index == 2) return 'c';

       if (index < Fibonacci(row - 1)) {
           row -= 2;
       } else {
           index -= Fibonacci(row - 1);
           row --;
       }
    }
}

最後に処理することが1つあります。それは、キャラクターが範囲外にあるために問題の解決策がない場合に発生することです。しかし、これは簡単に修正できます。

string NthChar(int row, int index) {
    /* Preprocess the row to make it a small value. */
    if (row >= 46) {
        if (row % 2 == 0)
            row = 45;
        else
            row = 44;
    }

    while (true) {
       if (row == 1 && index == 1) return "a"
       if (row == 2 && index == 1) return "b";
       if (row == 2 && index == 2) return "c";

       /* Bounds-checking. */
       if (row == 1) return "no solution";
       if (row == 2) return "no solution";

       if (index < Fibonacci(row - 1)) {
           row -= 2;
       } else {
           index -= Fibonacci(row - 1);
           row --;
       }
    }
}

そして、実用的なソリューションがあります。

さらに最適化する方法の1つは、必要なすべてのフィボナッチ数を事前に計算し、それらを巨大な配列に格納することです。F（2）からF（44）までのフィボナッチ値のみが必要なので、次のようなことができます。

const int kFibonacciNumbers[45] = {
    0, 1, 1, 2, 3, 5, 
    8, 13, 21, 34, 55, 89,
    144, 233, 377, 610,
    987, 1597, 2584, 4181,
    6765, 10946, 17711, 28657,
    46368, 75025, 121393, 196418,
    317811, 514229, 832040,
    1346269, 2178309, 3524578,
    5702887, 9227465, 14930352,
    24157817, 39088169, 63245986,
    102334155, 165580141, 267914296,
    433494437, 701408733
};

この事前計算された配列を使用すると、コードの最終バージョンは次のようになります。

string NthChar(int row, int index) {
    /* Preprocess the row to make it a small value. */
    if (row >= 46) {
        if (row % 2 == 0)
            row = 45;
        else
            row = 44;
    }

    while (true) {
       if (row == 1 && index == 1) return "a"
       if (row == 2 && index == 1) return "b";
       if (row == 2 && index == 2) return "c";

       /* Bounds-checking. */
       if (row == 1) return "no solution";
       if (row == 2) return "no solution";

       if (index < kFibonacciNumbers[row - 1]) {
           row -= 2;
       } else {
           index -= kFibonacciNumbers[row - 1];
           row --;
       }
    }
}

私はまだこれをテストしていません。ドン・クヌースを言い換えると、私はそれが正しいことを証明しただけです。:-)しかし、これがあなたの質問に答えるのに役立つことを願っています。私はこの問題が本当に好きでした！

于 2011-08-30T20:41:14.973 に答える
1

あなたの一般的な考えは大丈夫だと思いますが、Kの値が大きくなるとコードがどのように処理されるかわかりません。数値がすぐに膨大になり、大きな整数ライブラリでもフィボナッチの計算に実質的に永遠にかかる可能性があるためです。 （10 ^ 9）正確に。

幸い、最初の10^9文字についてのみ質問されます。文字列は、すでに44行目にあるその数の文字に到達します（f（44）= 1134903170）。

そして、私が間違っていなければ、そこから最初の10 ^ 9文字は、44行目と45行目のプレフィックスの間で単純に交互になります。したがって、擬似コードでは次のようになります。

def solution(K, P):
   if K > 45:
       if K % 2 == 0:
           return solution(44, P)
       else:
           return solution(45, P)
   #solution for smaller values of K here
于 2011-02-04T15:46:54.057 に答える
0

K 番目のフィボナッチ文字列を計算してから、その P 番目の文字を取得します。そんな感じ：

#include <iostream>
#include <string>
#include <vector>

std::string FibonacciString(unsigned int k)
{
    std::vector<char> buffer;
    buffer.push_back('a');
    buffer.push_back('b');
    buffer.push_back('c');

    unsigned int curr = 1;
    unsigned int next = 2;

    while (k --)
    {
        buffer.insert(
            buffer.end(),
            buffer.begin(),
            buffer.end());

        buffer.erase(
            buffer.begin(),
            buffer.begin() + curr);

        unsigned int prev = curr;
        curr = next;
        next = prev + next;
    }

    return std::string(
        buffer.begin(),
        buffer.begin() + curr);
}

int main(int argc, char** argv)
{
    unsigned int k, p;
    std::cin >> k >> p;

    -- p;
    -- k;

    std::string fiboK = FibonacciString(k);
    if (p > fiboK.size())
        std::cout << "No solution";
    else
        std::cout << fiboK[p];
    std::cout << std::endl;
    return 0;
}

毎回 N 番目と (N+1) 番目の両方のフィボナッチ文字列を格納する必要があるため、バージョンよりも多くのメモリを使用します。ただし、定義に非常に近いため、すべての値に対して機能します。

あなたのアルゴリズムは、が小さいときにkが大きい場合に問題があるようです。pテストfib_num[k] < pは、配列の範囲外の項目をk = 30andp = 1で逆参照しますね。

于 2011-02-04T12:50:29.427 に答える
0

私はこれを見つけました。チェックが成功した場合はとにかくそれを計算する必要があるため、事前チェック ( k-th fibo 文字列のサイズを取得して再テストする) は実行しませんでした。pもちろん、k大きくなるとすぐに、オーバーフローの問題が発生する可能性があります (フィボ文字列の長さはインデックスの指数関数nです...)。

#include <iostream>
#include <string>

using namespace std;

string fibo(unsigned int n)
{
    if (n == 0)
        return "a";
    else if (n == 1)
        return "bc";
    else
        return fibo(n - 2) + fibo(n - 1);

}

int main()
{
    unsigned int k, p;
    cin >> k >> p;
    --k;
    --p;
    string fiboK = fibo(k);
    if (p > fiboK.size())
        cout << "No solution" << endl;
    else
        cout << fiboK[p] << endl;
    return 0;
}

k編集:わかりました、私は今あなたのポイントを見ます、つまり、 -th 文字列のどの部分が存在するかを確認しpます(つまり、文字列k - 2またはk - 1、必要に応じて更新しpます)。もちろん、これは良い方法です。なぜなら、上記で述べたように、私の素朴な解決策は非常に急速に爆発するからです。

アルゴリズムの観点から見ると、あなたのやり方は正しいように見えます（メモリと複雑さを節約できます）。

于 2011-02-04T10:27:07.550 に答える
0

ウィキペディアからの引用、Fibonacci_word:

単語のn桁目は 2+[nφ]-[(n+1)φ] で、φ は黄金比です ...

(ウィキペディアのページで使用されている文字は 1 と 0 だけです。) ただし、ウィキペディアのページとクヌースの基本アルゴリズムの文字列は、上記の文字列とは逆の順序で構築されていることに注意してください。そこで文字列がリストされ、先頭部分が常に繰り返されると、無限に長いフィボナッチ文字列が 1 つだけ存在することが明らかになります。上記で使用した順序で生成された場合、繰り返し部分は文字列の末尾部分であるため、あまり明確ではありませんが、それほど真実ではありません。したがって、引用文の「単語」という用語は、「この行にはnが大きすぎますか?」という質問を除いて、行は重要ではありません。

残念ながら、この式をポスターの問題に適用するのは非常に困難です。なぜなら、この式では元の文字列が同じ長さであり、ポスターが "a" と "bc" で始まっているからです。

この J(ava)Script スクリプトは、投稿者が選択した文字に対してフィボナッチ文字列を生成しますが、順序は逆です。(これには、コマンドライン引数を取得して標準出力に出力するために使用される Microsoft オブジェクト WScript が含まれています。)

var u, v /*Fibonacci numbers*/, g, i, k, R;
v = 2;
u = 1;
k = 0;
g = +WScript.arguments.item(0); /*command-line argument for desired length of string*/
/*Two consecutiv Fibonacci numbers, with the greater no less than the
  Fibonacci string s length*/
while (v < g)
{   v += u;
    u = v - u;
    k = 1 - k;
}
i = u - k;
while (g-- > 0)
{   /*In this operation, i += u with i -= v when i >= v (carry),
      since the Fibonacci numbers are relativly prime, i takes on
      every value from 0 up to v. Furthermore, there are u carries,
      and, therefore, u instances of character 'cb', and v-u instances
      of 'a' (no-carry). The characters are spread as evenly as can be.*/
    if ((i += u) < v)
    {   R = 'a'; // WScript.StdOut.write('a'); /* no-carry */
    } else
    {   i -= v; /* carry */
        R = 'cb'; // WScript.StdOut.write('cb')
    }
}
/*result is in R*/ // WScript.StdOut.writeLine()

実際に文字列を出力する必要がないため、お勧めします。必要な長さで停止し、最後に出力されるものを表示するだけです。(出力用のコードは「//」でコメントアウトされています)。もちろん、これを使用して位置nの文字を見つけると、コストはnに比例します。上部の式ははるかに安価です。

于 2021-11-14T01:47:41.420 に答える