0

したがって、テンプレート構造関数があるとしますfib<i>::value。実行時に n 番目のフィボナッチ数を取得したい。このために、配列を作成しますfibs[] = { fib<0>::value, ... , fib<maxN>::value }。残念ながら、一部の関数maxNは非常に大きくなる可能性があり、手だけでは埋めることができません。そこで、タスクを簡単にするためにいくつかのプリプロセッサ ディレクティブを作成しました。

#define fib(x) (fib<(x)>::value)
#define fibLine_level_0(x) fib(5*(x) + 0), fib(5*(x) + 1), fib(5*(x) + 2), fib(5*(x) + 3), fib(5*(x) + 4)
#define fibLine_level_1(x) fibLine_level_0(2*(x) + 0), fibLine_level_0(2*(x) + 1)
#define fibLine_level_2(x) fibLine_level_1(2*(x) + 0), fibLine_level_1(2*(x) + 1)
#define fibLine_level_3(x) fibLine_level_2(2*(x) + 0), fibLine_level_2(2*(x) + 1)

#define cAarrSize(x) (sizeof(x) / sizeof(x[0]))

そして、私はそれを次のように使用します：

int fibs[] = { fibLine_level_3(0) };

for (int i = 0; i < cAarrSize(fibs); i++)
    cout << "fib(" << i << ") = " << fibs[i] << endl;

必要なコード:

template<int i>
struct fibPair{
    static const int fst = fibPair<i-1>::snd;
    static const int snd = fibPair<i-1>::fst + fibPair<i-1>::snd;
};

template<>
struct fibPair<0> {
    static const int fst = 0;
    static const int snd = 1;
};

template<int i>
struct fib {
    static const int value = fibPair<i>::fst;
};

しかし、このコードは本当に醜いです。もっと綺麗にするにはどうしたらいいですか？

制約: このコードはスポーツ プログラミングで使用する必要があります。つまり、サードパーティのライブラリはなく、場合によっては C++11 もありません (ただし、そうなる可能性があります)。

4

2 に答える 2

3

Fib構造は次のように書き換えることができます。

template <size_t i>
struct fib
{
    static const size_t value = fib<i - 1>::value + fib<i - 2>::value;
};

template <>
struct fib<0>
{
    static const size_t value = 0;
};

template <>
struct fib<1>
{
    static const size_t value = 1;
};

フィボナッチ数のコンパイル時の配列は、C++11 を使用して計算できます。

編集 1 (fib値のタイプを変更)。

編集2：

フィボナッチ数配列のコンパイル時生成 (この回答に基づく)。

template<unsigned... args> struct ArrayHolder
{
    static const unsigned data[sizeof...(args)];
};

template<unsigned... args>
const unsigned ArrayHolder<args...>::data[sizeof...(args)] = { args... };

template<size_t N, template<size_t> class F, unsigned... args>
struct generate_array_impl
{
    typedef typename generate_array_impl<N-1, F, F<N>::value, args...>::result result;
};

template<template<size_t> class F, unsigned... args>
struct generate_array_impl<0, F, args...>
{
    typedef ArrayHolder<F<0>::value, args...> result;
};

template<size_t N, template<size_t> class F>
struct generate_array
{
    typedef typename generate_array_impl<N-1, F>::result result;
};

int main()
{
    const size_t count = 10;
    typedef generate_array<count, fib>::result fibs;

    for(size_t i = 0; i < count; ++i)
        std::cout << fibs::data[i] << std::endl;
}

必要なのはgenerate_array、生成 «関数» (fib構造体) を提供することだけです。

于 2013-01-26T23:30:17.320 に答える
0

質問へのリンクを提供してくれた@namelessに感謝します。@MichaelAndersonによる単純なc ++（新機能なし）の回答が見つかりました。私はそれを使用し、自分のニーズに合わせて拡張しました。

だから、コンセプトは単純ですが、少し奇妙です。再帰的なテンプレート化された構造を作成する必要があります。ここで、最初のフィールドは、他の引数を持つこの同じテンプレート化された構造です。

template<size_t N>
struct FibList {
    FibList<N-1> previous;
    size_t value;
    FibList<N>() : value(fib<N>::value) {}
};

少し拡張してみましょう (コンパイラが何を生成するかを確認するためです):

template<size_t N>
struct FibList {
    FibList<N-3> previous;
    size_t value_N_minus_2;
    size_t value_N_minus_1;
    size_t value_N;
};

したがって、FibList は配列であると考えてキャストすることができます (これは私のソリューションの弱点です - 今は証明できません)。

static const size_t maxN = 2000;
FibList<maxN> fibList;
size_t *fibArray = &fibList.value - maxN;

または別の方法で：

size_t *fibArray = reinterpret_cast<size_t*>(&fibList);

重要: 配列のサイズは maxN+1 ですが、配列サイズを取得するための標準的な方法 ( sizeof(array) / sizeof(array[0]) は失敗します。それをかなり正確にしてください。

ここで、再帰を停止する必要があります。

// start point
template<>
struct FibList<0> {
    size_t value;
    FibList<0>() : value(0) {}
};

// start point
template<>
struct FibList<1> {
    FibList<0> previous;
    size_t value;
    FibList<1>() : value(1) {}
};

との場所を入れ替えるFibList<1>とFibList<0>、コンパイラでスタック オーバーフローが発生することに注意してください。

そして、別の問題を解決する必要があります - テンプレートの再帰には深さが限られています (コンパイラやオプションに依存します)。しかし、幸いなことに、コンパイラには深度制限しかなく、テンプレートのメモリ制限はありません (メモリ制限は深度制限よりも大きいです)。したがって、明らかな醜い解決策がfib<N>あります-深さ制限に等しいステップで連続して呼び出します-そして、テンプレートの深さ制限については決してキャッチしませんfib<N>。fib<500>::valueしかし、実行時以外に書くことはできません。FibList<N>だから私たちは解決策を得ました - を使用して特殊化するマクロを書きますfib<N>::value:

#define SetOptimizePointForFib(N) template<>\
struct FibList<N> {\
    FibList<(N)-1> previous;\
    size_t value;\
    FibList<N>() : value(fib<N>::value) {}\
};

そして、次のように書く必要があります。

SetOptimizePointForFib(500);
SetOptimizePointForFib(1000);
SetOptimizePointForFib(1500);
SetOptimizePointForFib(2300);

そのため、実際にコンパイル時に事前計算を行い、素晴らしい長さの静的配列を埋めました。

于 2013-01-27T02:36:47.883 に答える